#13仅用时3.04s
<https://www.luogu.com.cn/record/100764140>
```cpp
//P6136 【模板】普通平衡树（加强版）96分TLE#13
#include<bits/stdc++.h>
#include<time.h>
using namespace std;
const int N=1100066,INF=INT_MAX;
inline int fread(){
int ans=0,d=1; char ch='\0';
while(!('0'<=ch&&ch<='9')) ch=='-'?d=-d:0,ch=getchar();
while('0'<=ch&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans*d;
}
typedef int Tp;
int n,q,tot=0,rt=0;
int val[N],siz[N],pr[N],cnt[N];//数据,节点数,优先级,副本数
//优先级大的靠上，0的优先级为0
int son[N][2];//左右孩子
inline int neww(Tp v)/*建点*/{
++tot;
val[tot]=v,siz[tot]=1,pr[tot]=rand()+1,cnt[tot]=1;
return tot;
}
inline void upd(int x)/*更新节点数*/{
siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];
}
inline void build()/*初始化*/{
rt=neww(INF);
son[rt][0]=neww(-INF),upd(rt);
}
void rotate(int &x,int d)/*左旋0/右旋1*/ {
int y=son[x][d^1];
son[x][d^1]=son[y][d];
son[y][d]=x;
upd(x),upd(y);
x=y;
}
void insert(int &x,Tp v)/*插入*/{
if(x==0){x=neww(v); return;}
if(v==val[x]) cnt[x]++;
else{
int d=v<val[x]?0:1;//插入左/右
insert(son[x][d],v);
if(pr[x]<pr[son[x][d]]) rotate(x,d^1); //与插入的交换
}
upd(x);
}
void remove(int &x,Tp v)/*删除*/{
if(x==0) return;//找不到
if(v==val[x])/*检索到*/{
if(cnt[x]>1){cnt[x]--,upd(x); return;}//有副本
if(son[x][0]==0&&son[x][1]==0){x=0;return;}//叶子节点
if(son[x][1]==0||pr[son[x][0]>pr[son[x][1]]])
rotate(x,1),remove(son[x][1],v);//与左孩子交换
else
rotate(x,0),remove(son[x][0],v);//与右孩子交换
}else{
int d=v<val[x]?0:1;//删除左/右
remove(son[x][d],v);
} upd(x);
}
int grank(int x,Tp v){
if(x==0) return 1;//找不到,排名定义为比x小的数个数+1
if(v<val[x]) return grank(son[x][0],v);//左
else if(v==val[x]) return siz[son[x][0]]+1;//该点
else return siz[son[x][0]]+cnt[x]+grank(son[x][1],v);//右
}
int gval(int x,int rnk){
if(x==0) return INF;//向右找不到
if(rnk<=siz[son[x][0]]) return gval(son[x][0],rnk);//左
else if(rnk<=siz[son[x][0]]+cnt[x]) return val[x];//该点
else return gval(son[x][1],rnk-siz[son[x][0]]-cnt[x]);//右
}
inline Tp gpre(Tp v){
int x=rt; Tp pre;
while(x){
if(v>val[x]) pre=val[x],x=son[x][1];//右
else x=son[x][0];//左
}
return pre;
}
inline Tp gnxt(Tp v){
int x=rt; Tp nxt;
while(x){
if(v<val[x]) nxt=val[x],x=son[x][0];//左
else x=son[x][1];//右
}
return nxt;
}
int main(int argc,char* args[]){
srand(time(NULL)); build();
n=fread(),q=fread();
for(int i=1;i<=n;i++){
int ai=fread(); insert(rt,ai);
}
int lst=0,ans=0;
for(int i=1;i<=q;i++){
int t=fread(),x=fread();
x^=lst;
if(t==1) insert(rt,x);
if(t==2) remove(rt,x);
if(t==3) ans^=(lst=grank(rt,x)-1);//减去-INF节点
if(t==4) ans^=(lst=gval(rt,x+1));//加上-INF节点
if(t==5) ans^=(lst=gpre(x));
if(t==6) ans^=(lst=gnxt(x));
if(t>=3) printf("{%d,%d}=%d\n",t,x,lst);
else printf("{%d,%d}\n",t,x);
}
printf("%d",ans);
return 0;
}
```
by wkjfive @ 2023-01-30 09:49:04
换个算法？用splay或fhq？
by 小明小红 @ 2023-01-30 09:50:19
@[wkjfive](/user/374495) 你这代码好坑啊，数组删小点就过了，
```cpp
const int N=1100006,INF=INT_MAX;
typedef int Tp;
int n,q,tot,rt,lst,ans;
int val[N],siz[N],pr[N],cnt[N];//数据,节点数,优先级,副本数
```
by Loser_Syx @ 2023-01-30 09:56:48
过不了
by wkjfive @ 2023-01-30 10:22:50
好像有时能过有时过不了
by wkjfive @ 2023-01-30 10:49:32
巨佬orz太强力
by Ming_Yu @ 2023-01-30 16:30:38