【基于归并排序的分治】统计问题

题目是这样的：给你一个N*N的矩阵，可以完成两个操作

      1.修改某个格子的权值；2.查询某个矩形的权值。

 

看到题目以后很快想到的是二维树状数组，但是N<500000;Q<200000;空间上显然承受不了，第二个选择就是二维动态线段树，弊端是编程复杂度大，常数大，估计写出来是不可能的了。。。

 

不过既然有这种题目，那么就一定是有解决办法的，在线算法不行，可以考虑离线算法，这个离线算法应该怎么做呢？

深入考虑这道题，发现他相当于是要满足在3个偏序集的基础上进行统计---时间、x坐标、y坐标，怎样才可以满足条件呢？对于2个偏序集，我们常用的方法是对其中某一个偏序集进行排序使其成为全序集，再用数据结构统计另一个偏序集。3个应该怎么办？

 

（看了题解后）应该还记得经典的统计逆序对的算法吧-有两种做法，基于算法的归并排序，基于数据结构的树状数组，逆序对就是2个偏序集，如果归并排序加上树状数组能不能维护3个偏序集呢？答案是肯定的！

 

根据刚才的思想我们便设计出了一个非常漂亮的算法，对于一段区间[l,r](时间)上的操作，我递归成[l,m],[m+1,r]那么现在我们现在还没有统计的就是[l,m]中的1操作对[m+1,r]中的2操作的影响，我们便把它们单独拿出来算一遍就可以了（按x排好序，对y用树状数组统计）。

 

复杂度为O(QlogQlogN)，归并排序和树状数组都属于常数非常小的算法，所以500000的数据只要1S，总之这是个非常漂亮的算法！

 

编程复杂度极低：

 

program ex2; var q,a,b,x,c,s,o,d,u,z,ans:array[0..500000] of longint; i,n,t,task:longint; procedure ins(i,j:longint); begin s[i]:=s[i]*ord(q[i]=t)+j;q[i]:=t end; function get(i:longint):longint; begin s[i]:=s[i]*ord(q[i]=t);q[i]:=t;get:=s[i] end; function ask(i:longint):longint; begin ask:=0; while i>0 do begin inc(ask,get(i)); i:=i-i and (-i); end; end; procedure work(l,r:longint);var i,j,k,i1,i2,m:longint; begin if l>=r then exit; m:=(l+r)>>1; work(l,m);work(m+1,r); i1:=l;i2:=m+1;inc(t); for i:=l to r do begin if ((x[u[i1]]<=x[u[i2]])or(i2>r))and not(i1>m) then begin k:=i1;inc(i1); end else begin k:=i2;inc(i2); end; j:=u[k]; if (o[j]=1)and(k<=m) then begin k:=a[j]; while k<=n do begin ins(k,b[j]);k:=k+k and (-k); end; end else if (o[j]=2)and(k>m) then inc(ans[d[j]],c[j]*(ask(b[j])-ask(a[j]-1))); z[i]:=j; end; for i:=l to r do u[i]:=z[i]; end; begin assign(input,'easyii.in');reset(input); assign(output,'easyii.out');rewrite(output); read(n,o[1]);i:=1;task:=0; while o[i]<>3 do begin if o[i]=1 then read(x[i],a[i],b[i]) else begin inc(task); read(x[i],a[i],x[i+1],b[i]); c[i]:=-1;d[i]:=task;inc(i); a[i]:=a[i-1];b[i]:=b[i-1]; o[i]:=2;dec(x[i-1]); c[i]:=1;d[i]:=task; end; inc(i);read(o[i]); end; for i:=1 to i-1 do u[i]:=i; work(1,i); for i:=1 to task do writeln(ans[i]); close(input);close(output); end.