【BZOJ4066】简单题
Description
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
命令 | 参数限制 | 内容 |
1 x y A | 1<=x,y<=N，A是正整数 | 将格子x,y里的数字加上A |
2 x y x y | 1<=x<= x<=N 1<=y<= y<=N | 输出x y x y这个矩形内的数字和 |
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范围内并且解码之后数据仍合法。
题解：想了一上午KDtree为什么不能旋转，发现显然不能啊~（但听说能搞成替罪的？蒟蒻表示不懂~）
依旧是改一改估价函数就行了，这题需要每加入一些点就暴力重构整棵树
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define rep for(int i=0;i<=1;i++)
using namespace std;
struct kd
{
int sm[2],sn[2],v[2],sum,s,ls,rs;
kd (int a,int b,int c) {ls=rs=0,sm[0]=sn[0]=v[0]=a,sm[1]=sn[1]=v[1]=b,s=sum=c;}
kd (){}
};
kd t[200010],p[200010];
int n,m,A,B,C,D,root,ans;
bool cmp(kd a,kd b)
{
return (a.v[D]==b.v[D])?(a.v[D^1]<b.v[D^1]):(a.v[D]<b.v[D]);
}
void pushup(int x,int y)
{
rep t[x].sm[i]=max(t[x].sm[i],t[y].sm[i]),t[x].sn[i]=min(t[x].sn[i],t[y].sn[i]);
t[x].sum+=t[y].sum;
}
int build(int l,int r,int d)
{
if(l>r) return 0;
int mid=l+r>>1;
D=d;
nth_element(p+l,p+mid,p+r+1,cmp);
t[mid]=p[mid];
t[mid].ls=build(l,mid-1,d^1),t[mid].rs=build(mid+1,r,d^1);
if(t[mid].ls) pushup(mid,t[mid].ls);
if(t[mid].rs) pushup(mid,t[mid].rs);
return mid;
}
void ins(int y)
{
int x=root,d=0;
while(x!=y)
{
pushup(x,y);
if(t[y].v[0]==t[x].v[0]&&t[y].v[1]==t[x].v[1])
{
t[x].s+=t[y].s,n--;
return ;
}
if(t[y].v[d]<t[x].v[d]) t[x].ls=(!t[x].ls)?y:t[x].ls,x=t[x].ls;
else t[x].rs=(!t[x].rs)?y:t[x].rs,x=t[x].rs;
d^=1;
}
}
int query(int x)
{
if(!x||t[x].sm[0]<A||t[x].sn[0]>C||t[x].sm[1]<B||t[x].sn[1]>D) return 0;
if(t[x].sm[0]<=C&&t[x].sn[0]>=A&&t[x].sm[1]<=D&&t[x].sn[1]>=B) return t[x].sum;
int ret=0;
if(t[x].v[0]>=A&&t[x].v[0]<=C&&t[x].v[1]>=B&&t[x].v[1]<=D) ret+=t[x].s;
ret+=query(t[x].ls)+query(t[x].rs);
return ret;
}
int rd()
{
int ret=0; char gc=getchar();
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
int main()
{
rd();
int i,j,e;
root=1,m=10000;
while(1)
{
e=rd();
if(e==3) break;
if(e==1)
{
A=rd()^ans,B=rd()^ans,C=rd()^ans;
t[++n]=kd(A,B,C),ins(n);
if(n==m)
{
for(i=1;i<=n;i++) p[i]=kd(t[i].v[0],t[i].v[1],t[i].s);
root=build(1,n,0),m+=10000;
}
}
else
{
A=rd()^ans,B=rd()^ans,C=rd()^ans,D=rd()^ans;
ans=query(root);
printf("%d\n",ans);
}
}
return 0;
}