P2650 题解

liuyi0905 · 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;
}