思路：\(k-d\ tree\)
提交：2次
错因：整棵树重构时的严重错误：没有维护父子关系（之前写的是假重构所以没有维护父子关系）
题解：
遇到一个新的点就插进去，如果之前出现过就把权值加上。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ull unsigned long long
#define ll long long
#define R register int
using namespace std;
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[1<<15],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}
inline void gs(char* s) {
register char ch; while(isempty(ch=getchar()));
do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs;
namespace Luitaryi {
const int N=200010; const double A=0.707;
int n,top,tot,cnt,D,T,ans,rt;
struct P{int d[2],w;
inline bool operator <(const P& that) const {return d[D]<that.d[D];}
}p[N];
struct node {
int mx[2],mn[2],fa,sz,dim,sum,lson,rson; P p;
#define ls (t[tr].lson)
#define rs (t[tr].rson)
#define fa(tr) (t[tr].fa)
#define dim(tr) (t[tr].dim)
#define mx(tr,i) (t[tr].mx[i])
#define mn(tr,i) (t[tr].mn[i])
#define P(tr,i) (t[tr].p.d[i])
#define sum(tr) (t[tr].sum)
#define sz(tr) (t[tr].sz)
#define vl(tr) (t[tr].p.w)
}t[N];
int buff[N];
inline void upd(int tr,int dim) {
for(R i=0;i<=1;++i) {
mn(tr,i)=mx(tr,i)=P(tr,i);
if(ls) mx(tr,i)=max(mx(tr,i),mx(ls,i)),mn(tr,i)=min(mn(tr,i),mn(ls,i)),fa(ls)=tr;
if(rs) mx(tr,i)=max(mx(tr,i),mx(rs,i)),mn(tr,i)=min(mn(tr,i),mn(rs,i)),fa(rs)=tr;
} sz(tr)=sz(ls)+sz(rs)+1; sum(tr)=sum(ls)+sum(rs)+vl(tr); dim(tr)=dim;
}
inline void flat(int tr) {
if(ls) flat(ls);
p[++cnt]=t[tr].p,buff[++top]=tr;
if(rs) flat(rs);
}
inline int cre() {return top?buff[top--]:++tot;}
inline int build(int l,int r,int dim) {
if(l>r) return 0; R tr=cre(),md=l+r>>1;
D=dim,nth_element(p+l,p+md,p+r+1);
t[tr].p=p[md]; ls=build(l,md-1,dim^1),rs=build(md+1,r,dim^1);
upd(tr,dim); return tr;
}
inline void ins(int& tr,int fa,int dim,const P& tmp) {
if(!tr) {tr=cre(),t[tr].p=tmp,ls=rs=0,upd(tr,dim); return ;}
if(P(tr,0)==tmp.d[0]&&P(tr,1)==tmp.d[1]) vl(tr)+=tmp.w;
else P(tr,dim)>tmp.d[dim]?ins(ls,tr,dim^1,tmp):ins(rs,tr,dim^1,tmp);
upd(tr,dim); if(sz(tr)*A<max(sz(ls),sz(rs))) T=tr;
}
inline bool in(const node& ran,const node& dst) {
return ran.mn[0]>=dst.mn[0]&&ran.mx[0]<=dst.mx[0]
&&ran.mn[1]>=dst.mn[1]&&ran.mx[1]<=dst.mx[1];
}
inline bool out(const node& ran,const node& dst) {
return ran.mn[0]>dst.mx[0]||ran.mn[1]>dst.mx[1]
||ran.mx[0]<dst.mn[0]||ran.mx[1]<dst.mn[1];
}
inline int query(int tr,const node& dst) {
if(!tr||out(t[tr],dst)) return 0;
if(in(t[tr],dst)) return t[tr].sum;
R ret=1; for(R i=0;i<=1;++i) ret=ret&&(P(tr,i)<=dst.mx[i]&&P(tr,i)>=dst.mn[i]);
return ret*vl(tr)+query(ls,dst)+query(rs,dst);
}
inline void main() {
n=g(); while(1) { R op=g();
if(op==1) { register P tmp;
tmp.d[0]=g()^ans,tmp.d[1]=g()^ans,tmp.w=g()^ans;
ins(rt,rt,0,tmp); if(T) { flat(T);
if(T==rt) rt=build(1,cnt,0);
else t[fa(T)].rson==T?t[fa(T)].rson=build(1,cnt,dim(T)):t[fa(T)].lson=build(1,cnt,dim(T));
T=cnt=0;
}
} if(op==2) { register node tmp;
tmp.mn[0]=g()^ans,tmp.mn[1]=g()^ans,tmp.mx[0]=g()^ans,tmp.mx[1]=g()^ans;
printf("%d\n",ans=query(rt,tmp));
} if(op==3) break;
}
}
}
signed main() {
Luitaryi::main(); return 0;
}
2019.07.25