权值分块……rank3……没什么好说的。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,sz,sum,x,y,l[],r[],Min,Max,sumv[],num[],m,v[],p[];
bool b[];
char op[],c;
int Num,CH[],f;
inline void R(int &x){
c=;f=;
for(;c<''||c>'';c=getchar())if(c=='-')f=-;
for(x=;c>=''&&c<='';c=getchar())(x*=)+=(c-'');
x*=f;
}
inline void P(int x)
{
if(!x){putchar('');puts("");return;}
if(x<){putchar('-');x=-x;}Num=;
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);puts("");
}
void makeblock(const int &LIMIT)
{
sz=sqrt((double)LIMIT*0.9); if(!sz) sz=;
for(sum=;sum*sz<LIMIT;++sum)
{
l[sum]=r[sum-]+;
r[sum]=sum*sz;
for(int i=l[sum];i<=r[sum];++i) num[i]=sum;
}
l[sum]=r[sum-]+;
r[sum]=LIMIT;
for(int i=l[sum];i<=r[sum];++i) num[i]=sum;
}
inline void Insert(const int &x){b[x]=; ++sumv[num[x]];}
inline void Delete(const int &x){b[x]=; --sumv[num[x]];}
inline int Next(const int &x)
{
for(int i=x+;i<=r[num[x]];++i) if(b[i]) return i;
for(int i=num[x]+;;++i) if(sumv[i])
for(int j=l[i];;++j)
if(b[j]) return j;
}
inline int Pre(const int &x)
{
for(int i=x-;i>=l[num[x]];--i) if(b[i]) return i;
for(int i=num[x]-;;--i) if(sumv[i])
for(int j=r[i];;--j)
if(b[j]) return j;
}
inline int Rank(const int &x)
{
int cnt=;
for(int i=num[Min];i<num[x];++i) cnt+=sumv[i];
for(int i=l[num[x]];i<x;++i) cnt+=b[i];
return cnt;
}
inline int Kth(const int &x)
{
int cnt=;
for(int i=num[Min];;++i)
{
cnt+=sumv[i];
if(cnt>=x)
{
cnt-=sumv[i];
for(int j=l[i];;++j)
{cnt+=b[j]; if(cnt==x) return j;}
}
}
}
int main()
{
R(n); R(m); makeblock(n+(m<<));
for(int i=;i<=n;++i)
{
R(v[i+m]);
Insert(p[v[i+m]]=i+m);
} Min=+m; Max=n+m;
for(int i=;i<=m;++i)
{
scanf("%s",op); R(x);
if(op[]=='T')
{
Delete(p[x]);
v[p[x]=--Min]=x;
Insert(Min);
}
else if(op[]=='B')
{
Delete(p[x]);
v[p[x]=++Max]=x;
Insert(Max);
}
else if(op[]=='I')
{
R(y); if(y==-)
{
swap(v[p[x]],v[Pre(p[x])]);
swap(p[x],p[v[p[x]]]);
}
else if(y==)
{
swap(v[p[x]],v[Next(p[x])]);
swap(p[x],p[v[p[x]]]);
}
}
else if(op[]=='A') P(Rank(p[x]));
else P(v[Kth(x)]);
}
return ;
}