思路

一开始写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<<"\n";
        } else
        if(s[0]=='Q') {
            int a=read();
            cout<<k_th(a)<<"\n";
        }
    }
    return 0;
}