solution-code2023

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define inf 0x3F3F3F3F
6
using namespace std;
7
int n,m,a[80005],ch[80005][2],fa[80005],siz[80005],val[80005],pos[80005],rt;
8
inline void pushup(int x)
9
{
10
  int L=ch[x][0],R=ch[x][1];
11
  siz[x]=siz[L]+siz[R]+1;
12
  return;
13
}
14
inline void Rot(int x,int& f)
15
{
16
  int y=fa[x],z=fa[y],L=(ch[y][0]!=x),R=L^1;
17
  if(y==f)f=x;
18
  else
19
  {
20
    if(ch[z][0]==y)ch[z][0]=x;
21
    else ch[z][1]=x;
22
  }
23
  fa[ch[x][R]]=y;
24
  fa[y]=x;fa[x]=z;
25
  ch[y][L]=ch[x][R];
26
  ch[x][R]=y;
27
  pushup(y);
28
  pushup(x);
29
  return;
30
}
31
inline void Splay(int x,int& f)
32
{
33
  while(x!=f)
34
  {
35
    int y=fa[x],z=fa[y];
36
    if(y!=f)
37
    {
38
      if(ch[y][0]==x^ch[z][0]==y)Rot(x,f);
39
      else Rot(y,f);
40
    }
41
    Rot(x,f);
42
  }
43
  return;
44
}
45
inline void Build(int L,int R,int f)
46
{
47
  if(L>R)return;
48
  int now=L,lst=f;
49
  if(L==R)
50
  {
51
    val[now]=a[L];
52
    siz[now]=1;
53
    fa[now]=lst;
54
    ch[lst][L>=f]=now;
55
    return;
56
  }
57
  int mid=(L+R)>>1;now=mid;
58
  Build(L,mid-1,mid);
59
  Build(mid+1,R,mid);
60
  val[now]=a[mid];
61
  fa[now]=lst;
62
  pushup(now);
63
  ch[lst][mid>=f]=now;
64
  return;
65
}
66
inline int Find(int x,int k)
67
{
68
  int L=ch[x][0],R=ch[x][1];
69
  if(siz[L]+1==k)return x;
70
  if(siz[L]+1>k)return Find(L,k);
71
  return Find(R,k-siz[L]-1);
72
}
73
inline void Del(int k)
74
{
75
  int x=Find(rt,k-1),y=Find(rt,k+1);
76
  Splay(x,rt);
77
  Splay(y,ch[x][1]);
78
  fa[ch[y][0]]=siz[ch[y][0]]=0;
79
  ch[y][0]=0;
80
  pushup(y);
81
  pushup(x);
82
  return;
83
}
84
inline void Move(int k,int value)
85
{
86
  int x,y,z=pos[k],rnk;
87
  Splay(z,rt);rnk=siz[ch[z][0]]+1;
88
  Del(rnk);
89
  if(value==inf)x=Find(rt,n),y=Find(rt,n+1);
90
  else if(value==-inf)x=Find(rt,1),y=Find(rt,2);
91
  else x=Find(rt,rnk+value-1),y=Find(rt,rnk+value);
92
  Splay(x,rt);
93
  Splay(y,ch[x][1]);
94
  siz[z]=1;fa[z]=y;
95
  ch[y][0]=z;
96
  pushup(y);
97
  pushup(x);
98
  return;
99
}
100
char cmd[10];
101
int main(void)
102
{
103
  int i,x,y;
104
  scanf("%d%d",&n,&m);
105
  for(i=2;i<=n+1;++i)
106
  {
107
    scanf("%d",&a[i]);
108
    pos[a[i]]=i;
109
  }
110
  Build(1,n+2,0);
111
  rt=(n+3)>>1;
112
  for(i=1;i<=m;++i)
113
  {
114
    scanf("%s%d",cmd,&x);
115
    if(strcmp(cmd,"Top")==0)Move(x,-inf);
116
    if(strcmp(cmd,"Bottom")==0)Move(x,inf);
117
    if(strcmp(cmd,"Insert")==0)
118
    {
119
      scanf("%d",&y);
120
      Move(x,y);
121
    }
122
    if(strcmp(cmd,"Ask")==0)
123
    {
124
      Splay(pos[x],rt);
125
      printf("%d\n",siz[ch[pos[x]][0]]-1);
126
    }
127
    if(strcmp(cmd,"Query")==0)printf("%d\n",val[Find(rt,x+1)]);
128
  }
129
  return 0;
130
}