BZOJ1176: [Balkan2007]Mokia
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1176
cdq分治。。
有两维。可以排序搞掉一维然后树状数组处理一维。用cdq分治对时间分治。
对于询问(l,r)，(l,mid)一定会对(mid+1,r)有贡献，每次扫一遍把贡献加上去，然后再删掉，把数组重新排一遍序(以保证下次分治的时候不会越界）
#include<cstring> #include<iostream> #include<algorithm> #include<cstdio> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) using namespace std; struct data{int x,y,val,id,pos,a; }q[200500],tmp[200500]; int t[2000500],ans[200500]; int n,s,m; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } void get(){ ans[0]++; int x1=read(),y1=read(),x2=read(),y2=read(); q[++m].x=x1-1; q[m].y=y1-1; q[m].val=1; q[m].id=m; q[m].pos=1; q[m].a=ans[0]; q[++m].x=x2; q[m].y=y2; q[m].val=1; q[m].id=m; q[m].pos=1; q[m].a=ans[0]; q[++m].x=x1-1; q[m].y=y2; q[m].val=-1; q[m].id=m; q[m].pos=1; q[m].a=ans[0]; q[++m].x=x2; q[m].y=y1-1; q[m].val=-1; q[m].id=m; q[m].pos=1; q[m].a=ans[0]; } bool cmp(data a,data b){ if (a.x==b.x&&a.y==b.y) return a.pos<b.pos; else if (a.x==b.x) return a.y<b.y; else return a.x<b.x; } int low(int x){ return (x&(-x)); } void add(int x,int y){ while (x<=n){ t[x]+=y; x+=low(x); } } int ask(int x){ int ans=0; while (x){ ans+=t[x]; x-=low(x); } return ans; } void cdq(int l,int r){ if (l==r) return; int mid=(l+r)/2,l1=l,l2=mid+1; rep(i,l,r) { if (q[i].id<=mid&&!q[i].pos) add(q[i].y,q[i].val); else if (q[i].id>mid&&q[i].pos) ans[q[i].a]+=q[i].val*ask(q[i].y); } rep(i,l,r) { if (q[i].id<=mid&&!q[i].pos) add(q[i].y,-q[i].val); } rep(i,l,r) { if (q[i].id<=mid) tmp[l1++]=q[i]; else tmp[l2++]=q[i]; } rep(i,l,r) q[i]=tmp[i]; cdq(l,mid); cdq(mid+1,r); } int main(){ s=read(); n=read(); while (1){ int op=read(); if (op==1) {q[++m].x=read(); q[m].y=read(); q[m].val=read(); q[m].id=m; q[m].pos=0;} if (op==2) get(); if (op==3) break; } sort(q+1,q+1+m,cmp); cdq(1,m); rep(i,1,ans[0]) printf("%d ",ans[i]+s); return 0; }