一道平衡树裸题，但要注意细节。pos数组定位该元素的权重。
#include<bits/stdc++.h> #define N 80009 using 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(' '); } 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<A.val;} }; inline int rod() { static int x=23333; return x^=x<<13,x^=x>>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<x) return now->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<y->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(' '); 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; }