自动搬运

查看原文

来自洛谷，原作者为

	liuyi0905 同学或橙名及以上且不fake私信互关

搬运于2025-08-24 21:40:02，当前版本为作者最后更新于2023-08-12 07:30:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2650 solution:

题目传送门

这道题其实很简单，可以将每个弹幕的左端点放到右端点后面，最后询问的时候，只需要二分查找一下，用左端点查找到的答案去减去右端点查找的答案，就是可见弹幕的数量了。佩服楼下用主席树写的大佬

题目中还有一句话：

• 注意：查询区间为左闭右闭，弹幕出现区间为左开右开。

所以将弹幕左端点移到右边时，别忘了减 $1$，在询问时，则不需要减。

还有一点，$0\le ,y,a,b\le2^{31}-1$，别看这些数在 int 范围内，但 INT_MAX + INT_MAX 可就超出了 int 的范围，所以一定要开 long long。

代码如下：

#include <bits/stdc++.h>
#define int long long//会将程序了所有int转换成long long
#define N 100005
using namespace std;
int n,m,l[N],r[N],lt,rt;
signed main(){//因为main的返回值必须用int，所以这里写成了signed
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>l[i]>>r[i],r[i]+=l[i]-1;//记住这里还要减一
    sort(l+1,l+n+1),sort(r+1,r+n+1);//必须满足单调性才能二分
    while(m--){
        cin>>lt>>rt,rt+=lt;//询问时也要将左端点移到右端点后面
        cout<<signed(lower_bound(l+1,l+n+1,rt)-l)-signed(lower_bound(r+1,r+n+1,lt)-r)<<"\n";
        //这里偷个懒，直接用库函数解决二分，STL大法好~
    }
    return 0;
}