题目传送门
简单的KD-Tree+重构的应用。
查询的话和线段树一样查询。记sum表示子树和，如果当前区域完全被所求区域包含就直接返回sum，否则递归子树。
当插入超过一定次数时就重构（其实直接build就好了），注意把信息清零。
代码：
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define N 200005 #define F inline using namespace std; typedef long long LL; struct tree{ int to[2],mx[2],mn[2],d[2],x; LL sum; }t[N],now; int n,m,x,rt; LL lst; F char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF; return *l++; } F int _read(){ int x=0,f=1; char ch=readc(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=readc(); } while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc(); return x*f; } F void writec(int x){ if (x>9) writec(x/10); putchar(x%10+48); } F void _write(int x){ writec(x),putchar('\n'); } F bool cmp(tree a,tree b){ return a.d[x]==b.d[x]?a.d[x^1]<b.d[x^1]:a.d[x]<b.d[x]; } #define Max(a,b,f) (a[f]=max(a[f],b[f])) #define Min(a,b,f) (a[f]=min(a[f],b[f])) F void updt(tree &x){ for (int i=0;i<2;i++) for (int j=0;j<2;j++) if (x.to[j]) Max(x.mx,t[x.to[j]].mx,i),Min(x.mn,t[x.to[j]].mn,i); x.sum=x.x+t[x.to[0]].sum+t[x.to[1]].sum; } int build(int l,int r,int d){ int m=l+r>>1; x=d,nth_element(t+l+1,t+m+1,t+r+1,cmp); t[m].to[0]=l<m?build(l,m-1,d^1):0; t[m].to[1]=m<r?build(m+1,r,d^1):0; for (int i=0;i<2;i++) t[m].mx[i]=t[m].mn[i]=t[m].d[i]; return updt(t[m]),m; } void nsrt(int &x,int d){ if (!x) { t[x=++n]=now,m++; return; } if (t[x].d[0]==now.d[0]&&t[x].d[1]==now.d[1]){ t[x].x+=now.x,t[x].sum+=now.x; return; } nsrt(t[x].to[now.d[d]>=t[x].d[d]],d^1),updt(t[x]); } #define isin(x,y,xx,yy,X,Y,XX,YY) (x<=X&&y<=Y&&xx>=XX&&yy>=YY) #define ntin(x,y,xx,yy,X,Y,XX,YY) (x>XX||y>YY||xx<X||yy<Y) int srch(int x,int xx,int yy,int XX,int YY){ int mn0=t[x].mn[0],mn1=t[x].mn[1],mx0=t[x].mx[0],mx1=t[x].mx[1]; if (!x||ntin(xx,yy,XX,YY,mn0,mn1,mx0,mx1)) return 0; if (isin(xx,yy,XX,YY,mn0,mn1,mx0,mx1)) return t[x].sum; int nx=t[x].d[0],ny=t[x].d[1],ret=0; if (isin(xx,yy,XX,YY,nx,ny,nx,ny)) ret+=t[x].x; for (int i=0;i<2;i++) ret+=srch(t[x].to[i],xx,yy,XX,YY); return ret; } int main(){ _read(); int f,x,y,xx,yy,w,pd=10000; while ((f=_read())!=3){ x=_read()^lst,y=_read()^lst; if (f==1){ w=_read()^lst,now.d[0]=x,now.d[1]=y; for (int i=0;i<2;i++) now.mx[i]=now.mn[i]=now.d[i]; now.x=now.sum=w,nsrt(rt,0); } else{ xx=_read()^lst,yy=_read()^lst; lst=srch(rt,x,y,xx,yy),_write(lst); } if (m>pd) rt=build(1,n,0),m=0; } }