每个输入文件有多行。
第一行，一个数n，表示鼹鼠的范围。
以后每一行开头都有一个数m，表示不同的操作：
m=1，那么后面跟着3个数x,y,k(0<=x,y<n)，表示在点(x,y)处新出现了k只鼹鼠；
m=2，那么后面跟着4个数x1,y1,x2,y2(0<=x1<=x2<n,0<=y1<=y2<n)，表示询问矩形(x1,y1)-(x2,y2)内的鼹鼠数量；
m=3，表示老师来了，不能玩了。保证这个数会在输入的最后一行。
询问数不会超过10000，鼹鼠数不会超过maxlongint。n<=1024
测试数据 #1: Accepted, time=0ms, mem=98806KB, score=10
测试数据 #2: Accepted, time=124ms, mem=98806KB, score=10
测试数据 #3: Accepted, time=15ms, mem=98806KB, score=10
测试数据 #4: Accepted, time=15ms, mem=98806KB, score=10
测试数据 #5: Accepted, time=109ms, mem=98806KB, score=10
测试数据 #6: Accepted, time=0ms, mem=98806KB, score=10
测试数据 #7: Accepted, time=62ms, mem=98806KB, score=10
测试数据 #8: Accepted, time=31ms, mem=98806KB, score=10
测试数据 #9: Accepted, time=15ms, mem=98802KB, score=10
测试数据 #10: Accepted, time=140ms, mem=98806KB, score=10
Time = 511ms Mem = 98806KB Score= 100
这道题虽然是单点，但我写的是区间。（其实用树状数组做更快……只是用来试模板= =）
二维线段树注意以下几个方面：
- X树更新时时要到底到叶节点（因为X树不能lazy），但查询时不用查到叶节点（= =因此tle了若干次）。
- y树可以lazy，方法和普通线段树一样。
- 二维线段树的内存占用= =
- mid取得是xl xr，而不是要查询的区间x1、x2
Code
program segtree2D;
//Accepted
type
rec=record
xl,xr,yl,yr:integer;
add,sum:longint;
end;
Var
f:array[0..3100,0..3100] of rec;
n,m,i,j,x,y,k,x1,x2,y1,y2,op,top:longint;
Function mmin(a,b:longint):longint;inline;begin if a<b then exit(a);exit(b); end;
Function mmax(a,b:longint):longint;inline;begin if a>b then exit(a);exit(b); end;
Procedure buildY(p,q:longint);
var
mid:longint;
begin
if q>top then top:=q;
if f[p,q].yl=f[p,q].yr then exit;
mid:=(f[p,q].yl+f[p,q].yr) div 2;
with f[p,q*2] do
begin
xl:=f[p,q].xl;
xr:=f[p,q].xr;
yl:=f[p,q].yl;
yr:=mid;
end;
buildy(p,q*2);
with f[p,q*2+1] do
begin
xl:=f[p,q].xl;
xr:=f[p,q].xr;
yl:=mid+1;
yr:=f[p,q].yr;
end;
buildY(p,q*2+1);
end;
Procedure buildx(P:longint);
var
mid:longint;
begin
f[p,1].yl:=0;f[p,1].yr:=n-1;
buildy(p,1);
if f[p,1].xl=f[p,1].xr then exit;
mid:=(f[p,1].xl+f[p,1].xr) div 2;
with f[p*2,1] do
begin
xl:=f[p,1].xl;
xr:=mid;
end;
buildx(p*2);
with f[p*2+1,1] do
begin
xl:=mid+1;
xr:=f[p,1].xr;
end;
buildx(p*2+1);
end;
Procedure pushdown(p,q:longint);
begin
if p>top then exit;
//writeln('push down ',p,' ',q,' #:',f[p,q].add);
if q*2<=top then begin
inc(f[p,q*2].sum,(f[p,q*2].yr-f[p,q*2].yl+1)*f[p,q].add);
inc(f[p,q*2].add,f[p,q].add); end;
if q*2+1<=top then begin
inc(f[p,q*2+1].sum,(f[p,q*2+1].yr-f[p,q*2+1].yl+1)*f[p,q].add);
inc(f[p,q*2+1].add,f[p,q].add); end;
f[p,q].add:=0;
end;
Procedure addy(p,q,x1,x2,y1,y2,k:longint);
var
mid:longint;
begin
pushdown(p,q);
with f[p,q] do
begin
if (yl=y1) and (yr=y2) then
begin
inc(sum,(yr-yl+1)*(x2-x1+1)*k);
inc(add,k*(x2-x1+1));
exit;
end;
mid:=(yl+yr) shr 1;
if y1<=mid then addy(p,q*2,x1,x2,y1,mmin(y2,mid),k);
if y2>mid then addy(p,q*2+1,x1,x2,mmax(y1,mid+1),y2,k);
f[p,q].sum:=f[p,q*2].sum+f[p,q*2+1].sum;
end;
end;
Procedure Addx(P,x1,y1,x2,y2,k:longint);
var
mid:longint;
begin
Addy(p,1,x1,x2,y1,y2,k);
if (f[p,1].xr=f[p,1].xl) then exit;
with f[p,1] do mid:=(xl+xr) div 2;
if x1<=mid then Addx(p*2,x1,y1,mmin(x2,mid),y2,k);
if x2>mid then Addx(p*2+1,mmax(mid+1,x1),y1,x2,y2,k);
end;
Function getsumy(p,q,x1,x2,y1,y2:longint):longint;
var
mid:longint;
begin
pushdown(p,q); getsumy:=0;
with f[p,q] do
if (yl=y1) and (yr=y2) then
begin
//writeln('straight got!',yl,' ',yr,' ',f[p,q].sum);
exit(f[p,q].sum)
end
else
begin
mid:=(yl+yr) shr 1;
if y1<=mid then inc(getsumy,getsumy(p,q*2,x1,x2,y1,mmin(y2,mid)));
if y2>mid then inc(getsumy,getsumy(p,q*2+1,x1,x2,mmax(y1,mid+1),y2));
end;
//writeln('getsumY',p,' ',x1,',',y1,' | ',x2,',',y2,' =',getsumy);
end;
Function getsumX(p,x1,y1,x2,y2:longint):longint;
var
mid:longint;
begin
getsumx:=0;
with f[p,1] do
if (xl=x1) and (xr=x2) then
inc(getsumx,getsumy(p,1,x1,x2,y1,y2))
else
begin
mid:=(xl+xr) shr 1;
if x1<=mid then inc(getsumx,getsumx(p*2,x1,y1,mmin(x2,mid),y2));
if x2>mid then inc(getsumx,getsumx(p*2+1,mmax(mid+1,x1),y1,x2,y2));
end;
//writeln('getsumX',p,' ',x1,',',y1,' | ',x2,',',y2,' =',getsumx);
end;
Procedure init(N:longint);
begin
with f[1,1] do
begin
xl:=0;
xr:=n-1;
end;
Buildx(1);
end;
begin
readln(n);
init(n);
top:=0;
while true do
begin
read(op);
case op of
1:
begin
readln(x,y,k);
AddX(1,x,y,x,y,k);
end;
2:
begin
readln(x1,y1,x2,y2);
writeln(getsumX(1,x1,y1,x2,y2));
end;
3:
halt;
end;
end;
end.