一道平衡树裸题，但要注意细节。pos数组定位该元素的权重。

#include
     
      #define N 80009using namespace std;#define sight(c) ('0'<=c&&c<='9')#define RR NULL#define dwl  writel inline void read(int &x){    static char c;static int b;    for (b=1,c=getchar();!sight(c);c=getchar())if (c=='-') b=-1;    for (x=0;sight(c);c=getchar())x=x*10+c-48;x*=b;}void write(int x){
   if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); }inline void writel(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }struct Node{    int val,key;    Node() {}    Node(int V,int K):val(V),key(K){}    inline bool operator <(const Node& A)const{ return val
      
       >17,x^=x<<5;}struct Treap{    Node key;int val,siz;Treap* son[2];    Treap() { val=rod(); siz=1; son[0]=son[1]=RR;}    Treap(int V,int K) {        key.key=K; key.val=V; val=rod(); siz=1; son[0]=son[1]=RR;    }    inline void rob(){        siz=1;        if (son[0]) siz+=son[0]->siz;        if (son[1]) siz+=son[1]->siz;    }    inline int ask(){        return son[0]?son[0]->siz+1:1;    }};int find(int x,Treap *now){    if (!now) return 0;    if (now->key.val
       
        ask()+find(x,now->son[1]);    return find(x,now->son[0]);}void spilt(Treap *now,int k,Treap *&x,Treap *&y){    if (!now) {x=y=RR;return;}    int cmp=now->ask();    if (k>=cmp) x=now,spilt(x->son[1],k-cmp,x->son[1],y);     else  y=now,spilt(y->son[0],k,x,y->son[0]);    now->rob();}Treap* merge(Treap *x,Treap *y){    if (!x) return y; if (!y) return x;    if (x->val
        
         val) {x->son[1]=merge(x->son[1],y);x->rob();return x;}    y->son[0]=merge(x,y->son[0]); y->rob(); return y;}void dfs(Treap* x){    if (!x) return;    if (x->son[0]) dfs(x->son[0]);    dwl(x->key.key);    if (x->son[1]) dfs(x->son[1]);    x->rob();}int n,m,pos[N],a[N],x,l,r,k,op;char ch[1707];#define Mid (l+r>>1)void build (Treap* &now,int l,int r){    if (l>r) return;    now=new Treap(Mid,a[Mid]);    build(now->son[0],l,Mid-1); build(now->son[1],Mid+1,r);    now->rob();}Treap *root,*xr,*yr,*zr,*tr;int main () {//   freopen("a.in","r",stdin);//   freopen("a.out","w",stdout);   read(n); read(m);//   for (int i=1;i<=n;i++)//    read(a[i]),pos[a[i]]=i;//   build(root,1,n);   for(int i=1;i<=n;i++) {        read(x); pos[x]=i;      root=merge(root,new Treap(i,x));   } //   dfs(root); putchar('\n');   l=1; r=n;   while (m--) {        scanf("%s",ch);        switch (ch[0]) {             case 'T':                 read(x); k=find(pos[x],root);                 spilt(root,k,xr,yr); spilt(yr,1,tr,yr);                 pos[x]=--l; root=merge(new Treap(pos[x],x),merge(xr,yr));                 break;             case 'B':                 read(x); k=find(pos[x],root);                 spilt(root,k,xr,yr); spilt(yr,1,tr,yr);                 pos[x]=++r; root=merge(merge(xr,yr),new Treap(pos[x],x));                break;             case 'I':                 read(x); read(op);                 if (op==1) {                     k=find(pos[x],root);                     spilt(root,k,xr,yr); spilt(yr,2,tr,yr); spilt(tr,1,tr,zr);                     swap(pos[tr->key.key],pos[zr->key.key]);                     swap(tr->key.val,zr->key.val);                     root=merge(merge(xr,zr),merge(tr,yr));                     }            if (op==-1) {                k=find(pos[x],root);                     spilt(root,k-1,xr,yr); spilt(yr,2,tr,yr); spilt(tr,1,tr,zr);                     swap(pos[tr->key.key],pos[zr->key.key]);                     swap(tr->key.val,zr->key.val);                root=merge(merge(xr,zr),merge(tr,yr));            }                  break;             case 'A':                 read(x); writeln(find(pos[x],root));                 break;             case 'Q':                 read(k); spilt(root,k-1,xr,yr); spilt(yr,1,yr,zr);                 writeln(yr->key.key);                 root=merge(merge(xr,yr),zr);                 break;       }    } return 0;}