题意

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作： 1 x y A将格子x,y里的数字加上A 2 x1 y1 x2 y2输出x1 y1 x2 y2这个矩形内的数字和 3 终止程序 n<=500000，操作数<=200000，强制在线，空间限制为20M。

分析

如果没有空间限制和强制在线的话，就可以直接离线cdq分治或二维线段树。现在要求强制在线，就只能用KDtree。由于还要支持插入，所以就要像替罪羊树一样暴力重构来维护深度。 剩下的就是模板了。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=200005; int n,sz,rt,DD,top,stack[N],R; struct tree{int d[2],mn[2],mx[2],s,size,dir,fa,l,r,val;}t[N]; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void upd(int x,int y) { t[x].mn[0]=min(t[x].mn[0],t[y].mn[0]); t[x].mx[0]=max(t[x].mx[0],t[y].mx[0]); t[x].mn[1]=min(t[x].mn[1],t[y].mn[1]); t[x].mx[1]=max(t[x].mx[1],t[y].mx[1]); } void updata(int d) { t[d].s=t[t[d].l].s+t[t[d].r].s+t[d].val; t[d].size=t[t[d].l].size+t[t[d].r].size+1; t[d].mn[0]=t[d].mx[0]=t[d].d[0]; t[d].mn[1]=t[d].mx[1]=t[d].d[1]; if (t[d].l) upd(d,t[d].l); if (t[d].r) upd(d,t[d].r); } void dfs(int x) { if (t[x].l) dfs(t[x].l); stack[++top]=x; if (t[x].r) dfs(t[x].r); } bool cmp(int x,int y) { return t[x].d[DD]<t[y].d[DD]||t[x].d[DD]==t[y].d[DD]&&t[x].d[DD^1]<t[y].d[DD^1]; } void build(int &d,int l,int r,int D) { if (l>r) {d=0;return;} int mid=(l+r)/2; DD=D;nth_element(stack+l,stack+mid,stack+r+1,cmp); d=stack[mid];t[d].dir=D; build(t[d].l,l,mid-1,D^1);if (t[d].l) t[t[d].l].fa=d; build(t[d].r,mid+1,r,D^1);if (t[d].r) t[t[d].r].fa=d; updata(d); } void rebuild(int d) { int tmp=t[d].fa,op=(d==t[tmp].l?0:1); top=0;dfs(d);build(d,1,top,t[d].dir); if (!tmp) rt=d,t[d].fa=0; else if (!op) t[tmp].l=d; else t[tmp].r=d; } void ins(int &d,int x,int y,int z,int D) { if (!d) { d=++sz;t[d].dir=D; t[d].mn[0]=t[d].mx[0]=t[d].d[0]=x; t[d].mn[1]=t[d].mx[1]=t[d].d[1]=y; t[d].val=t[d].s=z;t[d].size=1; return; } if (t[d].d[0]==x&&t[d].d[1]==y) {t[d].val+=z;t[d].s+=z;return;} if (!D) if (x<t[d].d[0]||x==t[d].d[0]&&y<t[d].d[1]) ins(t[d].l,x,y,z,D^1),t[t[d].l].fa=d; else ins(t[d].r,x,y,z,D^1),t[t[d].r].fa=d; else if (y<t[d].d[1]||y==t[d].d[1]&&x<t[d].d[0]) ins(t[d].l,x,y,z,D^1),t[t[d].l].fa=d; else ins(t[d].r,x,y,z,D^1),t[t[d].r].fa=d; updata(d); if (t[d].size*0.75<max(t[t[d].l].size,t[t[d].r].size)) R=d; } bool in(int x1,int x2,int y1,int y2,int x3,int x4,int y3,int y4) { return x1>=x3&&x2<=x4&&y1>=y3&&y2<=y4; } bool out(int x1,int x2,int y1,int y2,int x3,int x4,int y3,int y4) { return x2<x3||x1>x4||y2<y3||y1>y4; } int query(int d,int x1,int x2,int y1,int y2) { if (!d||out(x1,x2,y1,y2,t[d].mn[0],t[d].mx[0],t[d].mn[1],t[d].mx[1])) return 0; if (in(t[d].mn[0],t[d].mx[0],t[d].mn[1],t[d].mx[1],x1,x2,y1,y2)) return t[d].s; int ans=0; if (t[d].d[0]>=x1&&t[d].d[0]<=x2&&t[d].d[1]>=y1&&t[d].d[1]<=y2) ans+=t[d].val; return ans+query(t[d].l,x1,x2,y1,y2)+query(t[d].r,x1,x2,y1,y2); } int main() { n=read(); int ans=0; while (1) { int op=read(); if (op==1) { int x=read()^ans,y=read()^ans,z=read()^ans; ins(rt,x,y,z,0); if (R) rebuild(R),R=0; } else if (op==2) { int x1=read()^ans,y1=read()^ans,x2=read()^ans,y2=read()^ans; printf("%d\n",ans=query(rt,x1,x2,y1,y2)); } else break; } return 0; }