学步园

题目是这样的：给你一个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;<br /> var<br /> q,a,b,x,c,s,o,d,u,z,ans:array[0..500000] of longint;<br /> i,n,t,task:longint;</p> <p>procedure ins(i,j:longint);<br /> begin s[i]:=s[i]*ord(q[i]=t)+j;q[i]:=t end;<br /> function get(i:longint):longint;<br /> begin s[i]:=s[i]*ord(q[i]=t);q[i]:=t;get:=s[i] end;</p> <p>function ask(i:longint):longint;<br /> begin<br /> ask:=0;<br /> while i>0 do begin<br /> inc(ask,get(i));<br /> i:=i-i and (-i);<br /> end;<br /> end;</p> <p>procedure work(l,r:longint);var i,j,k,i1,i2,m:longint;<br /> begin<br /> if l>=r then exit;<br /> m:=(l+r)>>1;<br /> work(l,m);work(m+1,r);<br /> i1:=l;i2:=m+1;inc(t);<br /> for i:=l to r do begin<br /> if ((x[u[i1]]<=x[u[i2]])or(i2>r))and not(i1>m)<br /> then begin<br /> k:=i1;inc(i1);<br /> end else begin<br /> k:=i2;inc(i2);<br /> end;<br /> j:=u[k];<br /> if (o[j]=1)and(k<=m) then begin<br /> k:=a[j];<br /> while k<=n do begin<br /> ins(k,b[j]);k:=k+k and (-k);<br /> end;<br /> end else<br /> if (o[j]=2)and(k>m) then<br /> inc(ans[d[j]],c[j]*(ask(b[j])-ask(a[j]-1)));<br /> z[i]:=j;<br /> end;<br /> for i:=l to r do u[i]:=z[i];<br /> end;</p> <p>begin<br /> assign(input,'easyii.in');reset(input);<br /> assign(output,'easyii.out');rewrite(output);<br /> read(n,o[1]);i:=1;task:=0;<br /> while o[i]<>3 do begin<br /> if o[i]=1 then read(x[i],a[i],b[i])<br /> else begin<br /> inc(task);<br /> read(x[i],a[i],x[i+1],b[i]);<br /> c[i]:=-1;d[i]:=task;inc(i);<br /> a[i]:=a[i-1];b[i]:=b[i-1];<br /> o[i]:=2;dec(x[i-1]);<br /> c[i]:=1;d[i]:=task;<br /> end;<br /> inc(i);read(o[i]);<br /> end;<br /> for i:=1 to i-1 do u[i]:=i;<br /> work(1,i);<br /> for i:=1 to task do writeln(ans[i]);<br /> close(input);close(output);<br /> end.