这题可以用cdq分治套树状数组，递归的每一层只考虑左半部分的修改对右半部分的询问所出产生的影响，至于左半部分的询问和右半部分修改对右半部分的询问的影响则递归下去处理，这样就没有顺序的影响，变成只考虑先插入后修改的情况。这种情况把每个询问拆成两个子询问:查询矩形(x1,1,x2,y1-1)和(x1,1,x2,y2)的值，把后者减去前者就是矩形(x1,y1,x2,y2)的价值，把询问和修改一起按y坐标排序，然后按顺序用树状数组维护修改和查询。
代码
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cstring> 5 #include<vector> 6 #include<string> 7 #define N 500010 8 #define M 1010 9 #define P 1000000007 10 using namespace std; 11 int n,typ,m,i,j,tot,x,y,z,b[N],flag[N],ans[N],c[N]; 12 int x1,y1,x2,y2; 13 struct g 14 { 15 int l,r,typ,v,idx,y,ridx; 16 }a[N]; 17 bool cmp(g a,g b) 18 { 19 if (a.y!=b.y) return a.y<b.y; 20 return a.ridx<b.ridx; 21 } 22 int lowbit(int x) 23 { 24 return x&-x; 25 } 26 void cc(int x,int w) 27 { 28 while (x<=tot) 29 { 30 c[x]=c[x]+w; 31 x=x+lowbit(x); 32 } 33 } 34 int sum(int x) 35 { 36 int ans=0; 37 while (x) 38 { 39 ans=ans+c[x]; 40 x=x-lowbit(x); 41 } 42 return ans; 43 } 44 int ef(int x) 45 { 46 int l,r,m; 47 l=1;r=tot; 48 while (l<=r) 49 { 50 m=(l+r)>>1; 51 if (b[m]>=x) r=m-1;else l=m+1; 52 } 53 return l; 54 } 55 void cdq(int l,int r) 56 { 57 int m,i; 58 m=(l+r)>>1; 59 if (l==r) return; 60 cdq(l,m); 61 cdq(m+1,r); 62 sort(a+l,a+r+1,cmp); 63 for (i=l;i<=r;i++) 64 { 65 if ((a[i].ridx<=m)&&(!a[i].typ)) cc(a[i].l,a[i].v); 66 if ((a[i].ridx>m)&&(a[i].typ)) ans[a[i].idx]+=((sum(a[i].r)-sum(a[i].l-1))*a[i].typ); 67 } 68 for (i=l;i<=r;i++) 69 if ((a[i].ridx<=m)&&(!a[i].typ)) cc(a[i].l,-a[i].v); 70 } 71 int main() 72 { 73 scanf("%d",&n); 74 n=0; 75 while (1) 76 { 77 scanf("%d",&typ); 78 m++; 79 if (typ==1) 80 { 81 scanf("%d%d%d",&x,&y,&z); 82 n++; 83 a[n].y=y;a[n].l=x;a[n].r=x; 84 a[n].typ=0;a[n].idx=m;a[n].v=z;a[n].ridx=n; 85 tot++;b[tot]=x; 86 } 87 else 88 if (typ==2) 89 { 90 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 91 n++; 92 a[n].y=y1-1;a[n].l=x1;a[n].r=x2;a[n].idx=m;a[n].typ=-1;a[n].ridx=n; 93 n++; 94 a[n].y=y2; a[n].l=x1;a[n].r=x2;a[n].idx=m;a[n].typ=1;a[n].ridx=n; 95 flag[m]=1; 96 tot++;b[tot]=x1; 97 tot++;b[tot]=x2; 98 } 99 else 100 break; 101 } 102 sort(b+1,b+1+tot); 103 for (i=1;i<=tot;i++) 104 if (b[i]!=b[i-1]) 105 { 106 j++;b[j]=b[i]; 107 } 108 tot=j; 109 for (i=1;i<=n;i++) 110 { 111 a[i].l=ef(a[i].l); 112 a[i].r=ef(a[i].r); 113 } 114 cdq(1,n); 115 for (i=1;i<=m;i++) 116 if (flag[i]) 117 printf("%d ",ans[i]); 118 }
这题还有一个强制在线的版本bzoj4066,可以用kdtree解决