1 #include<cstdio>  2 #include<cmath>  3 #include<algorithm>  4 using namespace std;  5 int n,sz,sum,x,y,l[501],r[501],Min,Max,sumv[501],num[250001],m,v[250001],p[250001];  6 bool b[250001];  7 char op[6],c;  8 int Num,CH[12],f;  9 inline void R(int &x){ 10     c=0;f=1; 11     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1; 12     for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘); 13     x*=f; 14 } 15 inline void P(int x) 16 { 17     if(!x){putchar(‘0‘);puts("");return;} 18     if(x<0){putchar(‘-‘);x=-x;}Num=0; 19     while(x>0)CH[++Num]=x%10,x/=10; 20     while(Num)putchar(CH[Num--]+48);puts(""); 21 } 22 void makeblock(const int &LIMIT) 23 { 24     sz=sqrt((double)LIMIT*0.9); if(!sz) sz=1; 25     for(sum=1;sum*sz<LIMIT;++sum) 26       { 27         l[sum]=r[sum-1]+1; 28         r[sum]=sum*sz; 29         for(int i=l[sum];i<=r[sum];++i) num[i]=sum; 30       } 31     l[sum]=r[sum-1]+1; 32     r[sum]=LIMIT; 33     for(int i=l[sum];i<=r[sum];++i) num[i]=sum; 34 } 35 inline void Insert(const int &x){b[x]=1; ++sumv[num[x]];} 36 inline void Delete(const int &x){b[x]=0; --sumv[num[x]];} 37 inline int Next(const int &x) 38 { 39     for(int i=x+1;i<=r[num[x]];++i) if(b[i]) return i; 40     for(int i=num[x]+1;;++i) if(sumv[i]) 41       for(int j=l[i];;++j) 42         if(b[j]) return j; 43 } 44 inline int Pre(const int &x) 45 { 46     for(int i=x-1;i>=l[num[x]];--i) if(b[i]) return i; 47     for(int i=num[x]-1;;--i) if(sumv[i]) 48       for(int j=r[i];;--j) 49         if(b[j]) return j; 50 } 51 inline int Rank(const int &x) 52 { 53     int cnt=0; 54     for(int i=num[Min];i<num[x];++i) cnt+=sumv[i]; 55     for(int i=l[num[x]];i<x;++i) cnt+=b[i]; 56     return cnt; 57 } 58 inline int Kth(const int &x) 59 { 60     int cnt=0; 61     for(int i=num[Min];;++i) 62       { 63         cnt+=sumv[i]; 64         if(cnt>=x) 65           { 66             cnt-=sumv[i]; 67             for(int j=l[i];;++j) 68             {cnt+=b[j]; if(cnt==x) return j;} 69           } 70       } 71 } 72 int main() 73 { 74     R(n); R(m); makeblock(n+(m<<1)); 75     for(int i=1;i<=n;++i) 76       { 77         R(v[i+m]); 78         Insert(p[v[i+m]]=i+m); 79       } Min=1+m; Max=n+m; 80     for(int i=1;i<=m;++i) 81       { 82         scanf("%s",op); R(x); 83         if(op[0]==‘T‘) 84           { 85             Delete(p[x]); 86             v[p[x]=--Min]=x; 87             Insert(Min); 88           } 89         else if(op[0]==‘B‘) 90           { 91             Delete(p[x]); 92             v[p[x]=++Max]=x; 93             Insert(Max); 94           } 95         else if(op[0]==‘I‘) 96           { 97             R(y); if(y==-1) 98               { 99                 swap(v[p[x]],v[Pre(p[x])]);100                 swap(p[x],p[v[p[x]]]);101               }102             else if(y==1)103               {104                 swap(v[p[x]],v[Next(p[x])]);105                 swap(p[x],p[v[p[x]]]);106               }107           }108         else if(op[0]==‘A‘) P(Rank(p[x]));109         else P(v[Kth(x)]);110       }111     return 0;112 }