4066: 简单题
Time Limit: 50 Sec Memory Limit: 20 MB
Description
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
| 命令 | 参数限制 | 内容 |
|---|---|---|
| 1 x y A | 1<=x,y<=N，A是正整数 | 将格子x,y里的数字加上A |
| 2 x1 y1 x2 y2 | 1<=x1<= x2<=N,1<=y1<= y2<=N | 输出x1 y1 x2 y2这个矩形内的数字和 |
| 3 | 无 | 终止程序 |
Input
输入文件第一行一个正整数N。
接下来每行一个操作。每条命令除第一个数字之外，
均要异或上一次输出的答案last_ans，初始时last_ans=0。
Output
对于每个2操作，输出一个对应的答案。
Sample Input
4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
Sample Output
3
5
HINT
数据规模和约定
1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。
样例解释见OJ2683
新加数据一组，但未重测—-2015.05.24
代码如下
//BZOJ 4066
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const double fac=0.65;
int Turn,x,y,_x,_y,Ans=0,tot,rt;
int read(){
int ret=0;char ch=getchar();bool f=1;
for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
return f?ret:-ret;
}
struct T{
int D[2],Son[2],P[2][2],W,Sum,Siz,ty;
void setup(int x,int y,int w){Son[0]=Son[1]=0,P[0][0]=P[0][1]=D[0]=x;P[1][0]=P[1][1]=D[1]=y,Sum=W=w,Siz=1;}
void clr(){P[0][0]=P[0][1]=D[0],P[1][0]=P[1][1]=D[1];Son[0]=Son[1]=0,Sum=W,Siz=1;}
int &operator [](const int b){return Son[b];}
}Tre[200005];
bool cmp(int x,int y){return Tre[x].D[Turn]<Tre[y].D[Turn];}
int Random(){
static int Sed=703;
return Sed=int(Sed*48271LL%2147483647);
}
struct KDTree{
int a[200005],pt;
void Pushup(int Now,int s){
Tre[Now].Sum+=Tre[s].Sum;Tre[Now].Siz+=Tre[s].Siz;
Tre[Now].P[0][0]=min(Tre[Now].P[0][0],Tre[s].P[0][0]);
Tre[Now].P[1][0]=min(Tre[Now].P[1][0],Tre[s].P[1][0]);
Tre[Now].P[0][1]=max(Tre[Now].P[0][1],Tre[s].P[0][1]);
Tre[Now].P[1][1]=max(Tre[Now].P[1][1],Tre[s].P[1][1]);
}
int Updata(int L,int R,int d){
int mid=(R+L)>>1,Now=0;Turn=d;
nth_element(a+L,a+mid,a+R+1,cmp);Now=a[mid];
Tre[Now].clr();Tre[Now].ty=d;
if(L<mid) Tre[Now][0]=Updata(L,mid-1,d^1),Pushup(Now,Tre[Now][0]);
if(mid<R) Tre[Now][1]=Updata(mid+1,R,d^1),Pushup(Now,Tre[Now][1]);
return Now;
}
void DFS(int Now){
a[++pt]=Now;
if(Tre[Now][0]) DFS(Tre[Now][0]);
if(Tre[Now][1]) DFS(Tre[Now][1]);
}
int Insert(int p,int Now){
if(!p) return Tre[Now].ty=Random()&1,Now;
Pushup(p,Now);Turn=Tre[p].ty;int &nx=Tre[p][Tre[Now].D[Turn]>=Tre[p].D[Turn]];
if(Tre[nx].Siz>Tre[p].Siz*fac) return a[pt=1]=Now,DFS(p),(p==rt)?rt=Updata(1,pt,Tre[p].ty):Updata(1,pt,Tre[p].ty);
nx=Insert(nx,Now);return p;
}
bool Check(T Now){return Now.P[0][0]<=_x&&x<=Now.P[0][1]&&Now.P[1][0]<=_y&&y<=Now.P[1][1];}
void query(int Now){
if(x<=Tre[Now].P[0][0]&&Tre[Now].P[0][1]<=_x&&y<=Tre[Now].P[1][0]&&Tre[Now].P[1][1]<=_y){Ans+=Tre[Now].Sum;return;}
if(x<=Tre[Now].D[0]&&Tre[Now].D[0]<=_x&&y<=Tre[Now].D[1]&&Tre[Now].D[1]<=_y) Ans+=Tre[Now].W;
if(Tre[Now][0]&&Check(Tre[Tre[Now][0]])) query(Tre[Now][0]);
if(Tre[Now][1]&&Check(Tre[Tre[Now][1]])) query(Tre[Now][1]);
}
}KDT;
int main(){
#ifndef ONLINE_JUDGE
freopen("prob.in","r",stdin);
freopen("prob.out","w",stdout);
#endif
int X,Y,opt;X=Y=read()/2;Tre[tot=rt=1].setup(X,Y,0);
while(opt=read(),opt^3){
if(opt==1){
X=read()^Ans,Y=read()^Ans;Tre[++tot].setup(X,Y,read()^Ans);
KDT.Insert(rt,tot);
}else{
x=read()^Ans,y=read()^Ans,_x=read()^Ans,_y=read()^Ans;
Ans=0,KDT.query(rt),printf("%d\n",Ans);
}
}
// printf("%.3lf\n",((double)sizeof(Tre))/1024/1024);
return 0;
}