简单题 bzoj-4066
题目大意：n*n的棋盘，开始为均为0，支持：单点加权值，查询矩阵权值和，强制在线。
注释：$1\le n\le 5\cdot 10^5$，$1\le m \le 2\cdot 10^5$。
想法：KD-Tree裸题。
所谓KD-Tree，就是一个看起来贼牛逼实际上我觉着也贼牛逼的暴力... ...
算了，网上讲解一摞摞，不赘述。
这里我们只需要在KD-Tree上维护子树和即可。单点加的话往上更新呗，或者换成删除+插入也能过。
最后，附上丑陋的代码... ...
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500010
using namespace std;
struct data
{
int p[2],maxn[2],minn[2],c[2],w,sum;
}a[N];
int d,root;
inline bool cmp(const data &a,const data &b)
{
return a.p[d]==b.p[d]?a.p[d^1]<b.p[d^1]:a.p[d]<b.p[d];
}
inline void pushup(int k,int s)
{
a[k].maxn[0]=max(a[k].maxn[0],a[s].maxn[0]);
a[k].minn[0]=min(a[k].minn[0],a[s].minn[0]);
a[k].maxn[1]=max(a[k].maxn[1],a[s].maxn[1]);
a[k].minn[1]=min(a[k].minn[1],a[s].minn[1]);
a[k].sum+=a[s].sum;
}
int build(int l,int r,int now)
{
int mid=(l+r)>>1;
d=now,nth_element(a+l,a+mid,a+r+1,cmp);
a[mid].maxn[0]=a[mid].minn[0]=a[mid].p[0];
a[mid].maxn[1]=a[mid].minn[1]=a[mid].p[1];
a[mid].sum=a[mid].w;
a[mid].c[0]=a[mid].c[1]=0;
if(l<mid)a[mid].c[0]=build(l,mid-1,now^1),pushup(mid,a[mid].c[0]);
if(r>mid)a[mid].c[1]=build(mid+1,r,now^1),pushup(mid,a[mid].c[1]);
return mid;
}
void ins(int x)
{
int *t=&root;
d=0;
while(*t)pushup(*t,x),t=&a[*t].c[a[x].p[d]>a[*t].p[d]],d^=1;
*t=x;
}
int query(int k,int x1,int y1,int x2,int y2)
{
if(!k||a[k].maxn[0]<x1||a[k].maxn[1]<y1||a[k].minn[0]>x2||a[k].minn[1]>y2)return 0;
if(a[k].maxn[0]<=x2&&a[k].maxn[1]<=y2&&a[k].minn[0]>=x1&&a[k].minn[1]>=y1)return a[k].sum;
int ans=0;
if(a[k].p[0]>=x1&&a[k].p[0]<=x2&&a[k].p[1]>=y1&&a[k].p[1]<=y2)ans+=a[k].w;
ans+=query(a[k].c[0],x1,y1,x2,y2)+query(a[k].c[1],x1,y1,x2,y2);
return ans;
}
int main()
{
int opt,x1,y1,x2,y2,last=0,tot=0;
scanf("%*d");
while(scanf("%d",&opt)!=EOF&&opt!=3)
{
if(opt==1)
{
tot++,scanf("%d%d%d",&a[tot].p[0],&a[tot].p[1],&a[tot].w);
a[tot].p[0]^=last,a[tot].p[1]^=last,a[tot].w^=last,a[tot].sum=a[tot].w;
a[tot].maxn[0]=a[tot].minn[0]=a[tot].p[0];
a[tot].maxn[1]=a[tot].minn[1]=a[tot].p[1];
ins(tot);
if(tot%10000==0)root=build(1,tot,0);
}
else scanf("%d%d%d%d",&x1,&y1,&x2,&y2),x1^=last,y1^=last,x2^=last,y2^=last,printf("%d\n",last=query(root,x1,y1,x2,y2));
}
return 0;
}
小结：KD-Tree更好玩... ...