题解 P2650 【弹幕考察】

zhrrrr · 2018-07-07 23:57:36 · 题解

“在线主席树，离线树状树。”

这道题没有强制在线，直接使用树状数组统计答案。

注意到数据范围，读入时先进行离散化。

然后从后往前维护树状数组，统计答案。

丑陋代码：

#include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x){
    char c=getchar();x=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
}
const int N=1e6+7;
int n,m,ans[N],tr[N],tot,a[N];
struct OO{int l,r;}x[N];
struct DD{int l,r,id;}q[N];
bool cmp(OO a,OO b){return a.r>b.r;}
bool cmp2(DD a,DD b){return a.l>b.l;}
inline int lb(int x){return x&(-x);}
inline void ad(int x){for(int i=x;i<=N;i+=lb(i))tr[i]++;}
inline int que(int x){int an=0;for(int i=x;i;i-=lb(i))an+=tr[i];return an;}
int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(x[i].l),x[i].l++,read(x[i].r),x[i].r+=x[i].l;
        a[++tot]=x[i].l;a[++tot]=x[i].r;
    }sort(x+1,x+n+1,cmp);
    for(int i=1;i<=m;i++){
        read(q[i].l),q[i].l++,read(q[i].r),q[i].r+=q[i].l,q[i].id=i;
        a[++tot]=q[i].l;a[++tot]=q[i].r;
    }sort(q+1,q+m+1,cmp2);
    sort(a+1,a+tot+1);tot=unique(a+1,a+tot+1)-a-1;
    for(int i=1;i<=n;i++){
        x[i].l=lower_bound(a+1,a+tot+1,x[i].l)-a;
        x[i].r=lower_bound(a+1,a+tot+1,x[i].r)-a;
    }
    for(int i=1;i<=m;i++){
        q[i].l=lower_bound(a+1,a+tot+1,q[i].l)-a;
        q[i].r=lower_bound(a+1,a+tot+1,q[i].r)-a;
    }
    int j=1;
    for(int i=1;i<=m;i++){
        while(x[j].r>q[i].l)ad(x[j++].l);
        ans[q[i].id]=que(q[i].r-1);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
    return 0;
}