一看题目就有一种平衡树的气息。
给每本书一个val 来维护相对位置
再用一个pos 数组记录下编号为x的位置1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using namespace std;
const int INF=1<<30,N=200050;
int rt=0,cnt=0,n,m,pos[N],w[N],L,R;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') {t=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*t;
}
struct node {int ch[2],fa,rec,val,sz;}t[N];
namespace Splay
{
void calc(int o) {t[o].sz=t[t[o].ch[0]].sz+t[t[o].ch[1]].sz+1;}
void maintain(int o) {pos[t[o].rec]=o;}
void rotate(int x)
{
int y=t[x].fa,z=t[y].fa,k=t[y].ch[1]==x;
t[z].ch[t[z].ch[1]==y]=x,t[x].fa=z;
t[y].ch[k]=t[x].ch[k^1],t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y,t[y].fa=x;
calc(y),calc(x);
}
void splay(int x,int to)
{
while (t[x].fa!=to)
{
int y=t[x].fa,z=t[y].fa;
if (z!=to) (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
rotate(x);
}
if (!to) rt=x;
}
void ins(int &o,int fa,int x,int idx)
{
if (!o)
{
o=++cnt;
t[o].val=x,t[o].fa=fa;
t[o].sz=1;
t[o].rec=idx;
pos[idx]=o;
splay(o,0);
return;
}
t[o].sz++;
ins(t[o].ch[x>t[o].val],o,x,idx);
}
void find(int x)
{
int o=rt;
while (t[o].ch[x>t[o].val]&&x!=t[o].val) o=t[o].ch[x>t[o].val];
splay(o,0);
}
int next(int x,int opt)
{
find(x);
if ((t[rt].val>x&&opt)||(t[rt].val<x&&!opt)) return rt;
int o=t[rt].ch[opt];
while (t[o].ch[opt^1]) o=t[o].ch[opt^1];
return o;
}
void del(int x)
{
int pre=next(x,0),nxt=next(x,1);
splay(pre,0),splay(nxt,pre);
int o=t[nxt].ch[0];
t[nxt].ch[0]=0;
calc(nxt);calc(pre);
}
int K_th(int o,int k)
{
if (!o) return 0;
if (k<=t[t[o].ch[0]].sz)
return K_th(t[o].ch[0],k);
else if (k>t[t[o].ch[0]].sz+1)
return K_th(t[o].ch[1],k-t[t[o].ch[0]].sz-1);
splay(o,0);
return t[o].rec;
}
};
using namespace Splay;
void insert(int x,int f)
{
if (!f) return;
if (f<0) f++;
int nxt=next(t[pos[x]].val,f);
swap(t[nxt].rec,t[pos[x]].rec);
maintain(pos[x]),maintain(nxt);
}
int main()
{
L=1,R=n=read(),m=read();
ins(rt,0,INF,0),ins(rt,0,-INF,0);
for(int i=1;i<=n;i++) ins(rt,0,i,read());
for(int i=1;i<=m;i++)
{
char str[20];
scanf("%s",str);
int x=read();
if (str[0]=='T') del(t[pos[x]].val),ins(rt,0,--L,x);
if (str[0]=='B') del(t[pos[x]].val),ins(rt,0,++R,x);
if (str[0]=='I') insert(x,read());
if (str[0]=='A') find(t[pos[x]].val),printf("%d\n",t[t[rt].ch[0]].sz-1);
if (str[0]=='Q') printf("%d\n",K_th(rt,x+1));
}
return 0;
}