cogs 577 蝗灾 CDQ分治

第一道CDQ，抄了下helenkeller的代码，感觉和归并排序差不多。。。
因为左半边的修改肯定在右半边的询问之前，所以就不用管时间的限制了，可以直接x轴排序树状数组处理y轴。。。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 int w,n;
  8 const int maxn=200005;
  9 inline int read()
 10 {
 11     int p=0;char c=getchar();
 12     while(c<'0'||c>'9')c=getchar();
 13     while(c>='0'&&c<='9')p=p*10+c-'0',c=getchar();
 14     return p;
 15 }
 16 struct node
 17 {
 18     int x1,y1,x2,y2,op,k,num;
 19     int ans;
 20 }p[maxn],cc[maxn<<1];
 21 int c[500005];
 22 bool cmp(const node&a,const node&b)
 23 {
 24     if(a.x1==b.x1)return a.op<b.op;
 25     return a.x1<b.x1;
 26 }
 27 int tot=0;
 28 void add(int x,int y)
 29 {
 30     for(int i=x;i<=w;i+=(i&(-i)))
 31     {
 32         c[i]+=y;
 33     }
 34 }
 35 int sum(int x)
 36 {
 37     int q=0;
 38     for(int i=x;i;i-=(i&(-i)))
 39     {
 40         q+=c[i];
 41     }
 42     return q;
 43 }
 44 void solve(int l,int r)
 45 {
 46     if(l==r)return ;
 47     int mid=(l+r)>>1;int cnt=0;
 48     for(int i=l;i<=mid;i++)
 49     {
 50         if(p[i].op==1)cc[cnt++]=p[i];
 51     }
 52     for(int i=mid+1;i<=r;i++)
 53     {
 54         if(p[i].op==2)
 55         {
 56             cc[cnt++]=p[i];
 57             cc[cnt++]=p[i];
 58             cc[cnt-2].x1--;
 59             cc[cnt-1].x1=p[i].x2;
 60             cc[cnt-1].op=3;
 61         }
 62     }
 63     sort(cc,cc+cnt,cmp);
 64     for(int i=0;i<cnt;i++)
 65     {
 66         if(cc[i].op==1)
 67         {
 68             add(cc[i].y1,cc[i].k);
 69         }
 70         else if(cc[i].op==2)
 71         {
 72             p[cc[i].num].ans-=sum(cc[i].y2)-sum(cc[i].y1-1);
 73         }
 74         else 
 75         {
 76             p[cc[i].num].ans+=sum(cc[i].y2)-sum(cc[i].y1-1);
 77         }
 78     }
 79     for(int i=0;i<cnt;i++)
 80     {
 81         if(cc[i].op==1)
 82         {
 83             add(cc[i].y1,-cc[i].k);
 84         }
 85     }
 86     solve(l,mid);
 87     solve(mid+1,r);
 88     return ;
 89 }
 90 int main()
 91 {
 92     freopen("locust.in","r",stdin);
 93     freopen("locust.out","w",stdout);
 94     scanf("%d%d",&w,&n);
 95     int flag,a,b,c,d;
 96     for(int i=1;i<=n;i++)
 97     {
 98         flag=read();
 99         if(flag==1)
100         {
101             a=read();b=read();c=read();
102             p[i].op=1;
103             p[i].x1=a;
104             p[i].y1=b;
105             p[i].k=c;
106         }
107         else 
108         {
109             a=read();b=read();c=read();d=read();
110             p[i].op=2;
111             p[i].x1=min(a,c);p[i].x2=max(a,c);
112             p[i].y1=min(b,d);p[i].y2=max(b,d);
113         }
114         p[i].num=i;
115     }
116     solve(1,n);
117     for(int i=1;i<=n;i++)
118     {
119         if(p[i].op==2)printf("%d
",p[i].ans);
120     }
121     return 0;
122 }