题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4066
https://www.lydsy.com/JudgeOnline/problem.php?id=2683
高仿：https://www.cnblogs.com/Narh/p/9605505.html
注意细节...
AC 300 ～
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const xn=2e5+5;
double const alpha=0.75;
int n,cnt,sta[xn],top,rt,dm,c[xn][2],qx1,qx2,qy1,qy2;
int R,fa,son,num;
ll ans;
struct N{
int x[2],y[2],p[2],siz;
ll sum,ys;
}t[xn],a[xn];
int rd()
{
int ret=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return f?ret:-ret;
}
ll Abs(ll x){return x>0?x:-x;}
ll Min(ll x,ll y){return x<y?x:y;}
ll Max(ll x,ll y){return x<y?y:x;}
bool cmp(N x,N y){return x.p[dm]<y.p[dm];}
int node(){if(top)return sta[top--]; else return ++cnt;}
void turn(int x,N v)
{
for(int i=0;i<2;i++)t[x].x[i]=t[x].y[i]=t[x].p[i]=v.p[i];
t[x].ys=t[x].sum=v.ys; t[x].siz=1; c[x][0]=0; c[x][1]=0;//ys //c //v.ys!!!
}
void pushup(int x)
{
int ls=c[x][0],rs=c[x][1];
for(int i=0;i<2;i++)
{
if(ls)t[x].x[i]=Min(t[x].x[i],t[ls].x[i]),t[x].y[i]=Max(t[x].y[i],t[ls].y[i]);
if(rs)t[x].x[i]=Min(t[x].x[i],t[rs].x[i]),t[x].y[i]=Max(t[x].y[i],t[rs].y[i]);
}
t[x].sum=t[x].ys+(ls?t[ls].sum:0)+(rs?t[rs].sum:0);
t[x].siz=1+(ls?t[ls].siz:0)+(rs?t[rs].siz:0);
}
bool ck(int x)
{
int ls=c[x][0],rs=c[x][1];
return (ls&&t[ls].siz>t[x].siz*alpha)||(rs&&t[rs].siz>t[x].siz*alpha);
}
void ins(int &x,N v,int nw)
{
if(!x){x=node(); turn(x,v); return;}
if(v.p[nw]<=t[x].p[nw])ins(c[x][0],v,nw^1);
else ins(c[x][1],v,nw^1);
pushup(x);
if(ck(x))R=x,dm=nw;
if(R==c[x][0])fa=x,son=0; if(R==c[x][1])fa=x,son=1;
}
bool can(int x)
{return t[x].p[0]>=qx1&&t[x].p[0]<=qx2&&t[x].p[1]>=qy1&&t[x].p[1]<=qy2;}
bool in(int x)
{return t[x].x[0]>=qx1&&t[x].y[0]<=qx2&&t[x].x[1]>=qy1&&t[x].y[1]<=qy2;}
bool out(int x)
{return t[x].x[0]>qx2||t[x].y[0]<qx1||t[x].x[1]>qy2||t[x].y[1]<qy1;}
ll query(int x)
{
if(can(x))ans+=t[x].ys;//ys
int ls=c[x][0],rs=c[x][1];
if(ls)
{
if(in(ls))ans+=t[ls].sum;
else if(!out(ls))query(ls);
}
if(rs)
{
if(in(rs))ans+=t[rs].sum;
else if(!out(rs))query(rs);
}
}
void kill(int x)
{
sta[++top]=x; a[++num]=t[x];
if(c[x][0])kill(c[x][0]);
if(c[x][1])kill(c[x][1]);
}
void build(int &x,int l,int r,int nw)
{
x=node(); dm=nw; int mid=((l+r)>>1);
nth_element(a+l,a+mid,a+r+1,cmp);
turn(x,a[mid]);
if(mid>l)build(c[x][0],l,mid-1,nw^1);
if(mid<r)build(c[x][1],mid+1,r,nw^1);
pushup(x);
}
void rbuild(int x)
{
num=0; kill(x); int mid=((1+num)>>1);
nth_element(a+1,a+mid,a+num+1,cmp);
int p=node(); turn(p,a[mid]);
if(fa)c[fa][son]=p; else rt=p;//
if(mid>1)build(c[p][0],1,mid-1,dm^1);
if(mid<num)build(c[p][1],mid+1,num,dm^1);
pushup(p);
}
int main()
{
n=rd(); N tmp;
while((n=rd())!=3)
{
if(n==1)
{
//tmp.p[0]=(rd()^ans); tmp.p[1]=(rd()^ans); tmp.ys=(rd()^ans);
tmp.p[0]=rd(); tmp.p[1]=rd(); tmp.ys=rd();
fa=0; ins(rt,tmp,0);//fa
}
else
{
//qx1=(rd()^ans); qy1=(rd()^ans);
//qx2=(rd()^ans); qy2=(rd()^ans);
qx1=rd(); qy1=rd(); qx2=rd(); qy2=rd();
ans=0; query(rt); printf("%lld\n",ans);
}
if(R){if(R==rt)fa=0; rbuild(R); R=0;}
}
return 0;
}