```cpp
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
inline void output(int x)
{
if(x/10) output(x/10);
putchar(x%10+'0');
return;
}
const int INF=1e9;
typedef long long ll;
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x>y?x:y;}
inline void Swap(int&x,int&y){x^=y;y^=x;x^=y;}
const int MAXN(2e5+10);
int n,m;
int ch[MAXN][2],val[MAXN],cnt[MAXN],siz[MAXN];
int pool,root;
inline void New(int&u,int v)
{
u=++pool;
cnt[u]=siz[u]=1;
val[u]=v;
return;
}
inline void push_up(int u)
{
siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+cnt[u];
return;
}
inline void zag(int&x)
{
int y=ch[x][1];
ch[x][1]=ch[y][0];
ch[y][0]=x;
siz[y]=siz[x];
push_up(x);
x=y;
return;
}
inline void zig(int&x)
{
int y=ch[x][0];
ch[x][0]=ch[y][1];
ch[y][1]=x;
siz[y]=siz[x];
push_up(x);
x=y;
return;
}
inline void splay(int x,int&y)
{
if(x==y) return;
int&ls=ch[y][0],&rs=ch[y][1];
if(x==ls) zig(y);
else if(x==rs) zag(y);
else
{
if(val[x]<val[y])
{
if(val[x]<val[ls]) splay(x,ch[ls][0]),zig(y),zig(y);
else splay(x,ch[ls][1]),zag(ls),zig(y);
}
else
{
if(val[x]>val[rs]) splay(x,ch[rs][1]),zag(y),zag(y);
else splay(x,ch[rs][0]),zig(rs),zag(y);
}
}
return;
}
inline void ins(int&u,int v)
{
if(!u) New(u,v),splay(u,root);
else if(val[u]==v) ++cnt[u],++siz[u],splay(u,root);
else if(val[u]<v) ins(ch[u][1],v);
else ins(ch[u][0],v);
return;
}
inline void fnode(int u,int v,int&p)
{
if(val[u]==v){p=u;return;}
if(val[u]<v) fnode(ch[u][1],v,p);
else fnode(ch[u][0],v,p);
}
inline int findkth(int&u,int k)
{
if(!siz[u]) return 0;
if(siz[ch[u][0]]>=k) return findkth(ch[u][0],k);
else if(siz[ch[u][0]]+cnt[u]>=k)
{
splay(u,root);
return val[root];
}
return findkth(ch[u][1],k-siz[ch[u][0]]-cnt[u]);
}
inline void del(int&v)
{
int u;
fnode(root,v,u);
splay(u,root);
if(cnt[u]>1) --siz[u],--cnt[u];
else if(!siz[ch[u][1]]) root=ch[u][0];
else
{
int p=findkth(ch[u][1],1);
splay(p,ch[u][1]);
ch[ch[u][1]][0]=ch[u][0];
root=ch[u][1];
push_up(root);
}
}
inline int findrank(int&u,int v)
{
if(!siz[u]) return 0;
if(val[u]==v)
{
int now=siz[ch[u][0]]+1;
splay(u,root);
return now;
}
if(val[u]>v) return findrank(ch[u][0],v);
else return findrank(ch[u][1],v)+siz[ch[u][0]]+cnt[u];
}
inline int pre(int v)
{
int u(root),k(0),pos(0);
while(u)
{
if(val[u]<v) k=val[u],pos=u,u=ch[u][1];
else u=ch[u][0];
}
splay(pos,root);
return k;
}
inline int suf(int v)
{
int u(root),k(0),pos(0);
while(u)
{
if(val[u]<=v) u=ch[u][1];
else k=val[u],pos=u,u=ch[u][0];
}
splay(pos,root);
return k;
}
int main()
{
m=read();
for(register int i=1;i<=m;i++)
{
int opt=read(),x=read();
if(opt==1) ins(root,x);
else if(opt==2) del(x);
else if(opt==3) printf("%d\n",findrank(root,x));
else if(opt==4) printf("%d\n",findkth(root,x));
else if(opt==5) printf("%d\n",pre(x));
else if(opt==6) printf("%d\n",suf(x));
}
return 0;
}
```
by UperFicial @ 2021-07-19 08:51:52
建议学习rotate的版本。。。
ZigZag当时都写吐了。。。
by Prean @ 2021-07-20 08:01:22
@[UperFicial](/user/360511) 这玩意不行,你搞个链表或者栈
by Magnoliaの魔帝ぼ @ 2021-07-20 08:06:50
@[UperFicial](/user/360511) 还有以后就写这一个头文件就行,不用那么多
```cpp
#include<bits/stdc++.h>
```
by Magnoliaの魔帝ぼ @ 2021-07-20 08:09:29
@[UperFicial](/user/360511) 但是在这个头文件里你不要把变量定义为“y1”否则会WA
by Magnoliaの魔帝ぼ @ 2021-07-20 08:13:03
@[Magnoliaの魔帝ぼ](/user/541742) 只要他不使用
```
using namespace std
```
就行
并且我觉得lz应该知道万能头是啥
以及,这玩意儿看个人习惯的吧(
by Prean @ 2021-07-20 08:16:28
@[UperFicial](/user/360511) 您的suf操作写挂了吧。。。
感觉suf和pre并没有本质区别。。。
by Prean @ 2021-07-20 08:25:36
@[Prean](/user/160839) 关键现在是 #2 卡死/kk
by UperFicial @ 2021-07-20 08:50:49
@[UperFicial](/user/360511) 是TLE?
by Prean @ 2021-07-20 08:55:49
草是RE
顺便说一句,正常的平衡树题fhq完全够用。。。Splay是LCT专用辅助树(
by Prean @ 2021-07-20 08:57:16