我的第一道cdq分治题
清明做了一下cdq分治的几道题，感觉这个东西实在是太厉害了离线大法好！关于几个经典的非数据结构做法具体可以看xhr神犇2013年的论文应用cdq分治的前提条件是不强制在线，修改操作互不影响。什么是互相影响，比如在第i个数后面插入一个数，这就明显是会影响到后面的操作在这个前提条件下，我们可以按照操作序列的时间线（先后）划分成两个规模缩小一半的子问题显然后面的修改对前面无影响，而后半部分的修改对后半部分的询问、前半部分对前半部分的询问是子问题，可以递归解决所以下面我们只要解决前半部分的所有修改操作对后半部分询问答案的贡献即可注意这里其实就相当于给出初始值不断进行无修改询问也就是我们通过分治（1个log的代价，根据主定理可知），干掉了动态修改回到这题上来，由于矩阵很大，不能支持二维数据结构，并且满足前提条件，所以用cdq分治之后就变成了给定矩阵上一些值，求子矩阵和这样一个无修改的问题注意这里询问满足减法性质，于是可以拆成四个询问，很显然对x排序，对y维护树状数组即可具体做法间见程序注释（如果已经懂得了分治的框架写起来是非常轻松的）注意bzoj1176和2683空间和范围略有不同
1 type node=record 2 op,ch,w,x,y:longint; 3 end; 4 5 var c:array[0..2000010] of longint; 6 a,q:array[0..210010] of node; 7 ans:array[0..10010] of longint; 8 ch,pre,i,n,m,x,y,x1,y1,t:longint; 9 10 function lowbit(x:longint):longint; 11 begin 12 exit(x and (-x)); 13 end; 14 15 function cmp(a,b:node):boolean; //注意这里要三个关键字排序，x,y,修改优先，为什么要自己想想 16 begin 17 if a.xj) then 45 begin 46 swap(q[i],q[j]); 47 inc(i); 48 dec(j); 49 end; 50 until i>j; 51 if l 0 do 68 begin 69 ask:=ask+c[x]; 70 x:=x-lowbit(x); 71 end; 72 end; 73 74 procedure cdq(l,r:longint); 75 var m,i,l1,l2:longint; 76 begin 77 if l=r then exit; 78 m:=(l+r) shr 1; 79 for i:=l to r do 80 begin 81 if (q[i].ch<=m) and (q[i].op=-2) then add(q[i].y,q[i].w); //前半部分修改 82 if (q[i].ch>m) and (q[i].op<>-2) then inc(ans[q[i].w],ask(q[i].y)*q[i].op); //对后半部分查询影响 83 end; 84 for i:=l to r do //树状数组清0 85 if (q[i].ch<=m) and (q[i].op=-2) then add(q[i].y,-q[i].w); 86 l1:=l; l2:=m+1; 87 for i:=l to r do //按时间划分操作序列 88 if q[i].ch<=m then 89 begin 90 a[l1]:=q[i]; 91 inc(l1); 92 end 93 else begin 94 a[l2]:=q[i]; 95 inc(l2); 96 end; 97 98 for i:=l to r do 99 q[i]:=a[i];100 cdq(l,m);101 cdq(m+1,r);102 end;103 104 begin105 readln(pre,t);106 while true do107 begin108 read(ch);109 if ch=3 then break;110 if ch=1 then111 begin112 inc(m);113 q[m].ch:=m;114 readln(q[m].x,q[m].y,q[m].w);115 q[m].op:=-2;116 end117 else begin118 inc(n); inc(m);119 readln(x,y,x1,y1);120 q[m].w:=n; q[m].ch:=m; q[m].x:=x1; q[m].y:=y1; q[m].op:=1;121 inc(m);122 q[m].w:=n; q[m].ch:=m; q[m].x:=x-1; q[m].y:=y1; q[m].op:=-1;123 inc(m);124 q[m].w:=n; q[m].ch:=m; q[m].x:=x1; q[m].y:=y-1; q[m].op:=-1;125 inc(m);126 q[m].w:=n; q[m].ch:=m; q[m].x:=x-1; q[m].y:=y-1; q[m].op:=1;127 end;128 end;129 sort(1,m);130 cdq(1,m);131 for i:=1 to n do132 writeln(ans[i]);133 end.