【bzoj2422】 Times 前缀和

本来想练一下树状数组的，看到网上某人的blog后点了进来。

第一眼发现不会，出去上了个厕所发现离散化后不是一道简单前缀和题吗。

考虑到每一个人出现且仅出现一次，且出现的时间是在一个连续的区间内。

那么对于一组询问(l,r)，当这个人在时刻l前消失，或者再时刻l+r后出现，那么你才会看不到。

那么我们维护一个sum1[i]，表示在时刻i及之前，出现过并且已经消失的人的数量。

维护一个sum2[i]，表示在时刻i及之后才出现的人的数量。

答案显然是n-sum1[l-1]-sum2[l+r]。

然后就没了，空间记得开够！

 #include<bits/stdc++.h>

 #define M 200005

 using namespace std;

 int c[M*]={},cnt=;

 int a[M]={},b[M]={},l[M]={},r[M]={};

 int sum1[M*]={},sum2[M*]={};

 int main(){

     int n,m;

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         scanf("%d%d",a+i,b+i);

         b[i]+=a[i]-;

         c[++cnt]=a[i];

         c[++cnt]=b[i];

     }

     for(int i=;i<=m;i++){

         scanf("%d%d",l+i,r+i);

         r[i]+=l[i]-;

         c[++cnt]=l[i];

         c[++cnt]=r[i];

     }

     sort(c+,c+cnt+);

     for(int i=;i<=n;i++)

     a[i]=lower_bound(c+,c+cnt+,a[i])-c,

     b[i]=lower_bound(c+,c+cnt+,b[i])-c;

     for(int i=;i<=m;i++)

     l[i]=lower_bound(c+,c+cnt+,l[i])-c,

     r[i]=lower_bound(c+,c+cnt+,r[i])-c;

     for(int i=;i<=n;i++)

     sum1[b[i]]++,sum2[a[i]]++;

     for(int i=;i<=cnt;i++) sum1[i]+=sum1[i-];

     for(int i=cnt;i;i--) sum2[i]+=sum2[i+];

     for(int i=;i<=m;i++){

         printf("%d\n",n-sum1[l[i]-]-sum2[r[i]+]);

     }

 }