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函数就是这样的
procedure slove(l,r:longint);
var
mid:longint;
begin
if l=r then exit;
slove(l,mid);
slove(mid+,r);
merge(l,mid,mid+,r);
end;
基本上就是这样了
const
maxn=;
maxq=;
maxw=;
type
node=record
q:boolean;
x,l,r,k:longint;
ans:int64;
end; var
add,n,numq,m:longint;
a,b:array[..maxn*]of node;
ans:array[..maxq]of int64; procedure init;
var
k,x1,y1,x2,y2:longint;
begin
read(add,n);
while true do
begin
read(k);
if k= then exit;
if k= then
begin
inc(m);
with a[m] do
read(x,l,r);
end
else
begin
read(x1,y1,x2,y2);
inc(m);inc(numq);
with a[m] do
begin
k:=numq;
q:=true;
x:=x1-;
l:=y1;r:=y2;
end;
inc(m);inc(numq);
with a[m] do
begin
k:=numq;
q:=true;
x:=x2;
l:=y1;r:=y2;
end;
end;
end;
end; var
time:longint;
vis:array[..maxw]of longint;
c:array[..maxw]of int64; function lowbit(x:longint):longint;
begin
exit(x and -x);
end; procedure insert(x:longint;y:int64);
begin
while x<=n do
begin
if vis[x]<>time then
begin
vis[x]:=time;
c[x]:=;
end;
inc(c[x],y);
inc(x,lowbit(x));
end;
end; function sum(x:longint):int64;
begin
sum:=;
while x> do
begin
if vis[x]<>time then
begin
vis[x]:=time;
c[x]:=;
end;
inc(sum,c[x]);
dec(x,lowbit(x));
end;
end; procedure slove(l,r:longint);
var
mid,i,j,k,x:longint;
begin
if l=r then exit;
mid:=(l+r)>>;
slove(l,mid);
slove(mid+,r);
x:=l;
i:=l;
j:=mid+;
inc(time);
while (i<=mid) and (j<=r) do
begin
if a[i].x<=a[j].x then k:=i
else k:=j;
if (k<=mid) and (a[k].q=false) then insert(a[k].l,a[k].r);
if (k>mid) and (a[k].q) then inc(a[k].ans,sum(a[k].r)-sum(a[k].l-));
if k=i then inc(i)
else inc(j);
b[x]:=a[k];
inc(x);
end;
while i<=mid do
begin
b[x]:=a[i];
inc(i);
inc(x);
end;
while j<=r do
begin
if a[j].q then
inc(a[j].ans,sum(a[j].r)-sum(a[j].l-));
b[x]:=a[j];
inc(j);
inc(x);
end;
for i:=l to r do
a[i]:=b[i];
end; procedure work;
var
i:longint;
begin
slove(,m);
for i:= to m do
if a[i].q then
ans[a[i].k]:=a[i].ans+add*a[i].x*(a[i].r-a[i].l+);
for i:= to numq>> do
writeln(ans[i<<]-ans[i<<-]);
end; begin
init;
work;
end.
ACcode