题目描述：https://www.lydsy.com/JudgeOnline/problem.php?id=4066

题解

无脑KD树，但是它卡我常数啊啊啊啊啊啊啊！！！！！

写完一交TLE

2min later，找到了一个SB错误：比较大小比较反了。。。

然后就开始循环展开

又T了

然后就写了部分重构，调了个0.7的参数

又T了

然后把函数里面的数组开成全局变量

还是T了

自闭了。。。

于是就写了一个数据生成器，手造了一组最大数据

然后拿了一个标程来对拍

发现我一组数据要运行30s+，标程一组数据2s。。。。

然后在函数里面写了一个con来计数调用了多少次

发现自己一次询问要花90000~140000次调用

？？？

叫来Master.Yi大佬，他一眼就看出来我的0号点的初始范围开小了，应该开1000000+，然而我只开了100000。。。

改了之后就正常了，一次询问500~1400次调用，一组数据3s+

BUT，交上BZOJ

还是T了。。。。@……%&#……%@*&……%

然后就有了一个奇怪的想法：

insert4500次之后来一次大重构，

各个子树如果不满足平衡常数0.75就进行一次小重构。

测了一下，一组数据2s+

交上去

Running & Judging

感觉自己等了一千年

然后它终于Accepted了

٩(๑>◡<๑)۶٩(๑>◡<๑)۶٩(๑>◡<๑)۶

代码：（49680ms）

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int gi()
{char c;int num=0,flg=1;while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}return num*flg;
}
#define N 200005
#define lc ch[i][0]
#define rc ch[i][1]
int D;long long con;
int ch[N][2],rt,tot;
int siz[N],tmp[N],cnt;
int a[N][2],mi[N][2],mx[N][2];
int sum[N],val[N];
int zb[2],k,qmi[2],qmx[2];
inline void pushup(int i)
{//con++;mi[i][0]=min(min(mi[lc][0],mi[rc][0]),a[i][0]);mx[i][0]=max(max(mx[lc][0],mx[rc][0]),a[i][0]);mi[i][1]=min(min(mi[lc][1],mi[rc][1]),a[i][1]);mx[i][1]=max(max(mx[lc][1],mx[rc][1]),a[i][1]);siz[i]=siz[lc]+siz[rc]+1;sum[i]=sum[lc]+sum[rc]+val[i];
}
inline bool cmp(const int &x,const int &y){return a[x][D]<a[y][D];}
void build(int &i,int l,int r,int d)
{//con++;int mid=(l+r)>>1;D=d;nth_element(tmp+l,tmp+mid,tmp+r+1,cmp);i=tmp[mid];lc=rc=0;if(l<mid)build(lc,l,mid-1,d^1);if(r>mid)build(rc,mid+1,r,d^1);pushup(i);
}
void dfs(int i)
{if(!i) return;dfs(lc);tmp[++cnt]=i;dfs(rc);
}
void insert(int &i,int d)
{//con++;if(!i){i=++tot;sum[i]=val[i]=k;a[i][0]=mi[i][0]=mx[i][0]=zb[0];a[i][1]=mi[i][1]=mx[i][1]=zb[1];return;}bool flg=(a[i][d]<=zb[d]);insert(ch[i][flg],d^1);pushup(i);if(1.0*max(siz[lc],siz[rc])>0.75*siz[i]){cnt=0;dfs(i);build(i,1,cnt,d);}
}
int ans;
void query(int i)
{//con++;if(!i)return;if(mi[i][0]>qmx[0]||mx[i][0]<qmi[0]||mi[i][1]>qmx[1]||mx[i][1]<qmi[1])return;if(qmi[0]<=mi[i][0]&&mx[i][0]<=qmx[0]&&qmi[1]<=mi[i][1]&&mx[i][1]<=qmx[1]){ans+=sum[i];return;}if(qmi[0]<=a[i][0]&&a[i][0]<=qmx[0]&&qmi[1]<=a[i][1]&&a[i][1]<=qmx[1])ans+=val[i];query(lc);query(rc);
}
int main()
{mi[0][0]=mi[0][1]=10000000;mx[0][0]=mx[0][1]=0;//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);int n,op;n=gi();while(1){op=gi();if(op==3)break;if(op==1){zb[0]=gi();zb[1]=gi();k=gi();zb[0]^=ans;zb[1]^=ans;k^=ans;insert(rt,0);if(tot%4500==0){cnt=0;dfs(rt);build(rt,1,cnt,0);}}else{qmi[0]=gi();qmi[1]=gi();qmx[0]=gi();qmx[1]=gi();qmi[0]^=ans;qmi[1]^=ans;qmx[0]^=ans;qmx[1]^=ans;ans=0;query(rt);printf("%d\n",ans);}}//freopen("CON","w",stdout);//printf("%lld",con);
}

就当是锻炼了一下调试能力吧。。。