Description
维护一个W*W的矩阵，每次操作可以增加某格子的权值，或询问某子矩阵的总权值。 修改操作数M<=160000，询问数Q<=10000，W<=2000000。
Input
Output
Sample Input
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
3
5
HINT
Input file Output file Meaning
0 4 Table size is , filled with zeroes.
1 2 3 3 Add 3 customers at (2, 3).
2 1 1 3 3 Query sum of rectangle , .
3 Answer.
1 2 2 2 Add 2 customers at (2, 2).
2 2 2 3 4 Query sum of rectangle , .
5 Answer
3 Exit your program.
题目大意：给你一个矩阵，每次可以增加一个点的权值，或者询问一个子矩阵的和
cdq分治
先做一个预处理，把每一个询问(x1,y1)(x2,y2)变成(1,y1)(x,y2)的形式，其实只要拆成两个相减的形式就行了
把询问(x1,y1)(x2,y2)改成(1,y1)(x1-1,y2)和(1,y1)(x2,y2)两个询问，回答的时候只要做差就行了
考虑什么操作才会对询问做出贡献，当这个操作time比询问早，操作的x<=询问的x才会有贡献
所以我们先按time排序，其实都不用排了
保证只有前面的才会影响后面的，然后对这些操作和询问进行（按x为关键字）归并排序
每次合并的时候计算出左边区间对右边区间造成的影响
所以slove函数就是这样的
1 procedure slove(l,r:longint); 2 var 3 mid:longint; 4 begin 5 if l=r then exit; 6 slove(l,mid); 7 slove(mid+1,r); 8 merge(l,mid,mid+1,r); 9 end;
基本上就是这样了
1 const 2 maxn=200000; 3 maxq=20010; 4 maxw=2000010; 5 type 6 node=record 7 q:boolean; 8 x,l,r,k:longint; 9 ans:int64; 10 end; 11 12 var 13 add,n,numq,m:longint; 14 a,b:array[0..maxn*2]of node; 15 ans:array[0..maxq]of int64; 16 17 procedure init; 18 var 19 k,x1,y1,x2,y2:longint; 20 begin 21 read(add,n); 22 while true do 23 begin 24 read(k); 25 if k=3 then exit; 26 if k=1 then 27 begin 28 inc(m); 29 with a[m] do 30 read(x,l,r); 31 end 32 else 33 begin 34 read(x1,y1,x2,y2); 35 inc(m);inc(numq); 36 with a[m] do 37 begin 38 k:=numq; 39 q:=true; 40 x:=x1-1; 41 l:=y1;r:=y2; 42 end; 43 inc(m);inc(numq); 44 with a[m] do 45 begin 46 k:=numq; 47 q:=true; 48 x:=x2; 49 l:=y1;r:=y2; 50 end; 51 end; 52 end; 53 end; 54 55 var 56 time:longint; 57 vis:array[0..maxw]of longint; 58 c:array[0..maxw]of int64; 59 60 function lowbit(x:longint):longint; 61 begin 62 exit(x and -x); 63 end; 64 65 procedure insert(x:longint;y:int64); 66 begin 67 while x<=n do 68 begin 69 if vis[x]<>time then 70 begin 71 vis[x]:=time; 72 c[x]:=0; 73 end; 74 inc(c[x],y); 75 inc(x,lowbit(x)); 76 end; 77 end; 78 79 function sum(x:longint):int64; 80 begin 81 sum:=0; 82 while x>0 do 83 begin 84 if vis[x]<>time then 85 begin 86 vis[x]:=time; 87 c[x]:=0; 88 end; 89 inc(sum,c[x]); 90 dec(x,lowbit(x)); 91 end; 92 end; 93 94 procedure slove(l,r:longint); 95 var 96 mid,i,j,k,x:longint; 97 begin 98 if l=r then exit; 99 mid:=(l+r)>>1; 100 slove(l,mid); 101 slove(mid+1,r); 102 x:=l; 103 i:=l; 104 j:=mid+1; 105 inc(time); 106 while (i<=mid) and (j<=r) do 107 begin 108 if a[i].x<=a[j].x then k:=i 109 else k:=j; 110 if (k<=mid) and (a[k].q=false) then insert(a[k].l,a[k].r); 111 if (k>mid) and (a[k].q) then inc(a[k].ans,sum(a[k].r)-sum(a[k].l-1)); 112 if k=i then inc(i) 113 else inc(j); 114 b[x]:=a[k]; 115 inc(x); 116 end; 117 while i<=mid do 118 begin 119 b[x]:=a[i]; 120 inc(i); 121 inc(x); 122 end; 123 while j<=r do 124 begin 125 if a[j].q then 126 inc(a[j].ans,sum(a[j].r)-sum(a[j].l-1)); 127 b[x]:=a[j]; 128 inc(j); 129 inc(x); 130 end; 131 for i:=l to r do 132 a[i]:=b[i]; 133 end; 134 135 procedure work; 136 var 137 i:longint; 138 begin 139 slove(1,m); 140 for i:=1 to m do 141 if a[i].q then 142 ans[a[i].k]:=a[i].ans+add*a[i].x*(a[i].r-a[i].l+1); 143 for i:=1 to numq>>1 do 144 writeln(ans[i<<1]-ans[i<<1-1]); 145 end; 146 147 begin 148 init; 149 work; 150 end.