Time Limit: 50 Sec Memory Limit: 20 MB
Submit: 2185 Solved: 581
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
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
Sample Output
3
5
5
HINT
数据规模和约定
1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。
样例解释见OJ2683
新加数据一组，但未重测----2015.05.24
Source
同Bzoj2683。
嘛，真是简单题啊，才调了两天就过了。
由于强制在线，所以不能像2683那样各种方法乱搞，只能老实写K-Dtree（好像还有块链之类的解法）
K-Dtree定期重构，强行维护数据。常数写不好的话会T飞。
之前把47行的左右边界取错了，时间复杂度直接突破天际。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
const int mxn=;
LL read(){
LL x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct node{
int l,r;
int min[],max[];
int d[];
int w;
LL sum;
}t[mxn];
int root=,nowD;
int cmp(const node a,const node b){
return a.d[nowD]<b.d[nowD];
}
int n,cnt;
int lim=;
inline void pushup(int rt,int x){
t[rt].max[]=max(t[rt].max[],t[x].max[]);
t[rt].max[]=max(t[rt].max[],t[x].max[]);
t[rt].min[]=min(t[rt].min[],t[x].min[]);
t[rt].min[]=min(t[rt].min[],t[x].min[]);
return;
}
inline bool in(int x1,int y1,int x2,int y2,int k){
return (x1<=t[k].min[] && t[k].max[]<=x2 &&
y1<=t[k].min[] && t[k].max[]<=y2);
}
inline bool out(int x1,int y1,int x2,int y2,int k){
return (x1>t[k].max[] || x2<t[k].min[] || y1>t[k].max[] || y2<t[k].min[]);
}
int Build(int l,int r,int D){
if(l>r)return ;
nowD=D;int mid=(l+r)>>;
nth_element(t+l,t+mid,t+r+,cmp);///
t[mid].max[]=t[mid].min[]=t[mid].d[];
t[mid].max[]=t[mid].min[]=t[mid].d[];
t[mid].sum=t[mid].w;
//
t[mid].l=Build(l,mid-,D^);
if(t[mid].l)pushup(mid,t[mid].l);
t[mid].r=Build(mid+,r,D^);
if(t[mid].r)pushup(mid,t[mid].r);
//
t[mid].sum=t[mid].w+t[t[mid].l].sum+t[t[mid].r].sum;
return mid;
}
void insert(int &now,int x,int D){
if(!now){now=x;return;}
if(t[x].d[D]==t[now].d[D] && t[x].d[!D]==t[now].d[!D]){
t[now].w+=t[x].w;
t[now].sum+=t[x].w;
--cnt;
return;
}
if(t[x].d[D]<t[now].d[D]){
insert(t[now].l,x,D^);
pushup(now,t[now].l);
}
else{
insert(t[now].r,x,D^);
pushup(now,t[now].r);
}
t[now].sum=t[now].w+t[t[now].l].sum+t[t[now].r].sum;
return;
}
LL query(int rt,int x1,int y1,int x2,int y2){
if(!rt)return ;
LL res=;
if(in(x1,y1,x2,y2,rt)){return t[rt].sum;}
if(out(x1,y1,x2,y2,rt)){return ;}
if(x1<=t[rt].d[] && t[rt].d[]<=x2 &&
y1<=t[rt].d[] && t[rt].d[]<=y2) res+=t[rt].w;
res+=query(t[rt].l,x1,y1,x2,y2)+query(t[rt].r,x1,y1,x2,y2);
return res;
}
int main(){
int i,j,op,x,y,w;
n=read();lim=;
LL lans=;int X1,X2,Y1,Y2;
while(){
op=read();
if(op==)break;
if(op==){
t[++cnt].d[]=read()^lans;t[cnt].d[]=read()^lans;
t[cnt].w=read()^lans;t[cnt].sum=t[cnt].w;
t[cnt].max[]=t[cnt].min[]=t[cnt].d[];
t[cnt].max[]=t[cnt].min[]=t[cnt].d[];
insert(root,cnt,);
if(cnt==lim){
lim+=;
root=Build(,cnt,);
}
}
else{ X1=read()^lans;Y1=read()^lans;X2=read()^lans;Y2=read()^lans;
lans=query(root,X1,Y1,X2,Y2);
printf("%lld\n",lans);
}
}
return ;
}