思路
一开始写fhq-treap
感觉越写越感觉splay好些，就去splay
然后维护序列
注意前驱后继的不存在的情况
但不用插入虚拟节点(那插入岂不太麻烦)
跑的真慢的一批，splay太多了
错误
好多错误
只好对拍
代码
//这个题用treap似乎小题大做了,所以我用splay
#include <iostream>
#include <cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=2e5+7;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m,a[maxn],rt,cnt,pos[maxn];
struct node {
int ch[2],fa,val,siz;
}e[maxn];
void pushup(int x) {
e[x].siz=e[e[x].ch[1]].siz+e[e[x].ch[0]].siz+1;
}
void rotate(int x) {
int y=e[x].fa,z=e[y].fa,k=(e[y].ch[1]==x);
e[z].ch[e[z].ch[1]==y]=x;
e[x].fa=z;
e[y].ch[k]=e[x].ch[k^1];
e[e[x].ch[k^1]].fa=y;
e[y].fa=x;
e[x].ch[k^1]=y;
pushup(x),pushup(y);
}
void splay(int x,int goal) {
while(e[x].fa!=goal) {
int y=e[x].fa,z=e[y].fa;
if(z!=goal) (e[y].ch[0]==x)^(e[z].ch[0]==y) ? rotate(x):rotate(y);
rotate(x);
}
if(goal==0) rt=x;
}
int k_th(int k) {
int now=rt;
while(233) {
if(e[e[now].ch[0]].siz+1==k) return e[now].val;
if(e[e[now].ch[0]].siz>=k) now=e[now].ch[0];
else k-=e[e[now].ch[0]].siz+1,now=e[now].ch[1];
}
splay(now,0);
}
int build(int l,int r,int f) {
if(l>r) return 0;
int mid=(l+r)>>1,p=(++cnt);
e[p].fa=f;
e[p].siz=1;
e[p].val=a[mid];
pos[a[mid]]=cnt;
e[p].ch[0]=build(l,mid-1,p);
e[p].ch[1]=build(mid+1,r,p);
pushup(p);
return p;
}
void dfs(int now) {
if(!now) return;
dfs(e[now].ch[0]);
cout<<e[now].val<<" ";
dfs(e[now].ch[1]);
}
int qq(int x) {
splay(x,0);
if(e[rt].val<e[x].val) return rt;
int now=e[rt].ch[0];
if(!now) return 0;
while(e[now].ch[1]) now=e[now].ch[1];
splay(now,0);
return now;
}
int hj(int x) {//x是pos
splay(x,0);
if(e[rt].val>e[x].val) return rt;
int now=e[rt].ch[1];
if(!now) return 0;
while(e[now].ch[0]) now=e[now].ch[0];
splay(now,0);
return now;
}
int p;
void delet(int x) {
int last=qq(x),nxt=hj(x);
if(last) splay(last,0);
if(nxt) splay(nxt,last);
if(nxt==0) {
p=e[last].ch[1];
e[last].ch[1]=0;
} else {
p=e[nxt].ch[0];
e[nxt].ch[0]=0;
if(nxt) splay(nxt,0);
}
}
void insert(int k) {
int now=rt;
while(e[now].ch[k]) now=e[now].ch[k];
e[now].ch[k]=p;
e[p].siz=1;
e[p].fa=now;
splay(p,0);
}
int main() {
n=read(),m=read();
FOR(i,1,n) a[i]=read();
rt=build(1,n,0);
char s[20];
FOR(i,1,m) {
cin>>s;
if(s[0]=='T') {
int a=read();
delet(pos[a]);
insert(0);
} else
if(s[0]=='B') {
int a=read();
delet(pos[a]);
insert(1);
} else
if(s[0]=='I') {
int a=read(),k=read(),b;
if(k==0) continue;
if(k==-1) b=qq(pos[a]);
else b=hj(pos[a]);
if(!b) continue;
int x=a,y=e[b].val;
swap(pos[x],pos[y]);
swap(e[pos[x]].val,e[pos[y]].val);
} else
if(s[0]=='A') {
int a=read();
splay(pos[a],0);
cout<<e[e[rt].ch[0]].siz<<"
";
} else
if(s[0]=='Q') {
int a=read();
cout<<k_th(a)<<"
";
}
}
return 0;
}