题目描述
输入格式
输出格式
样例
数据范围与提示
之前做过一道叫做移动电话的题，后来发现这道题数据加到二维树状数组开不出来。。。话说移动电话居然是IOI2001，这简直了，当时可能没有树状数组，可能也没有线段树，可能$n^{2}$是正解。。。我们说正题，如何用CDQdalao的离线分治解决呢。。。
首先这个题我们离线做，把所有操作打上时间戳，然后就有三维了。这样考虑一个查询，拆成4个矩形加加减减，我们就可以维护一个坐标与原点围成的矩形中点个数。而且一个修改对查询有影响，当且仅当x，y，t都小于它，标准三维偏序，CDQ套上就可以了
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N=200020,M=2000020; struct node { int a,b,t,f,w; int op; }a[N],t[N]; int b[M],n,ans[N],S,m,tt; int rd() { int s=0,w=1; char cc=getchar(); while(cc<'0'||cc>'9') {if(cc=='-') w=-1;cc=getchar();} while(cc>='0'&&cc<='9') s=(s<<1)+(s<<3)+cc-'0',cc=getchar(); return s*w; } void add(int x,int w) { for(int i=x;i<=m;i+=(i&-i)) b[i]+=w; } int sum(int x) { int ans=0; for(int i=x;i;i-=(i&-i)) ans+=b[i]; return ans; } bool cmp(node a,node b) { if(a.t!=b.t)return a.t<b.t; if(a.a!=b.a)return a.a<b.a; return a.b<b.b; } void CDQ(int l,int r) { if(l==r) return; int mid=(l+r)>>1; CDQ(l,mid);CDQ(mid+1,r); int p=l,q=mid+1,cnt=l-1; while(p<=mid&&q<=r) { //cout<<p<<" "<<q<<endl; if(a[p].a<=a[q].a) { if(a[p].op==0)add(a[p].b,a[p].w); t[++cnt]=a[p++]; } else { if(a[q].op>0)a[q].f+=sum(a[q].b); t[++cnt]=a[q++]; } } while(p<=mid) { if(a[p].op==0)add(a[p].b,a[p].w); t[++cnt]=a[p++]; } while(q<=r) { if(a[q].op>0) a[q].f+=sum(a[q].b); t[++cnt]=a[q++]; } for(int i=l;i<=mid;i++) if(a[i].op==0)add(a[i].b,-a[i].w); for(int i=l;i<=r;i++) a[i]=t[i]; } bool cmp2(node a,node b) { if(a.t==b.t) return a.op<b.op; return a.t<b.t; } void asd(int x,int y,int t,int op,int w) { //cout<<tt<<" "<<x<<" "<<y<<endl; a[++tt].a=x,a[tt].b=y;a[tt].t=t; a[tt].op=op;a[tt].w=w; } int main() { S=rd(),m=rd()+1; int cnt=0,xa,xb,ya,yb,x,w,y; for(int i=1;;i++) { int op=rd(); if(op==3) break; if(op==2) { cnt++; xa=rd()+1,ya=rd()+1; xb=rd()+1,yb=rd()+1; asd(xb,yb,i,1,0); asd(xa-1,yb,i,2,0); asd(xb,ya-1,i,3,0); asd(xa-1,ya-1,i,4,0); } if(op==1) { x=rd()+1,y=rd()+1,w=rd(); asd(x,y,i,0,w); } }//(xa,yb)-(xa,ya-1)-(xb-1,yb)+(xb-1,ya-1) sort(a+1,a+tt+1,cmp); CDQ(1,tt); for(int i=1;i<=tt;i++) { //cout<<i<<" "<<a[i].t<<endl; switch(a[i].op) { case 1: { ans[a[i].t]+=a[i].f+(a[i].a*a[i].b*S); break; } case 2: { ans[a[i].t]-=a[i].f+(a[i].a*a[i].b*S); break; } case 3: { ans[a[i].t]-=a[i].f+(a[i].a*a[i].b*S); break; } case 4: { ans[a[i].t]+=a[i].f+(a[i].a*a[i].b*S); break; } } } sort(a+1,a+tt+1,cmp2); for(int i=1;i<=tt;i++) { if(a[i].op==4) printf("%d ",ans[a[i].t]); } } /* g++ 1.cpp -o 1 ./1 0 4 1 2 3 3 2 1 1 3 3 1 2 2 2 2 2 2 3 4 3 */ /* g++ -g 1.cpp -o 1 gdb -q 1 b 42 r 0 4 1 2 3 3 2 1 1 3 3 1 2 2 2 2 2 2 3 4 3 */