1 #include<cstdio> 2 #include<ext/pb_ds/assoc_container.hpp> 3 #include<ext/pb_ds/tree_policy.hpp> 4 using namespace std; 5 using namespace __gnu_cxx; 6 using namespace __gnu_pbds; 7 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T; 8 typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>::iterator ITER; 9 //往bzoj上交时，请将null_type改成null_mapped_type10 int Pos[100001],Val[500001],a,x,n,m;11 char op[7];12 int main()13 {14     scanf("%d%d",&n,&m);15     for(int i=1;i<=n;i++)16       {17         scanf("%d",&Val[i+100000]);18         Pos[Val[i+100000]]=i+100000;19         T.insert(i+100000);20       }21     for(int i=1;i<=m;i++)22       {23         scanf("%s",op);24         if(op[0]==‘T‘)25           {26             scanf("%d",&a);27             int tmp=*T.find_by_order(0);28             T.erase(T.lower_bound(Pos[a]));29             Pos[a]=tmp-1;30             Val[tmp-1]=a;31             T.insert(tmp-1);32           }33         else if(op[0]==‘B‘)34           {35             scanf("%d",&a);36             int tmp=*T.find_by_order(n-1);37             T.erase(T.lower_bound(Pos[a]));38             Pos[a]=tmp+1;39             Val[tmp+1]=a;40             T.insert(tmp+1);41           }42         else if(op[0]==‘I‘)43           {44             scanf("%d%d",&a,&x);45             if(x==0)46               continue;47             ITER it=T.lower_bound(Pos[a]);48             ITER it_Beside=it;49             if(x==1)50               it_Beside++;51             else52               it_Beside--;53             swap(Val[*it],Val[*it_Beside]);54             swap(Pos[Val[*it]],Pos[Val[*it_Beside]]);55           }56         else if(op[0]==‘A‘)57           {58             scanf("%d",&a);59             printf("%d\n",T.order_of_key(Pos[a]));60           }61         else62           {63             scanf("%d",&a);64             printf("%d\n",Val[*T.find_by_order(a-1)]);65           }66       }67     return 0;68 }