solution-code3179

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int a[200005],maxx[200005],ch[200005][2],fa[200005],siz[200005],val[200005],rt,cnt;
7
inline void pushup(int x)
8
{
9
  int L=ch[x][0],R=ch[x][1];
10
  maxx[x]=max(val[x],max(maxx[L],maxx[R]));
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[x]=z;fa[y]=x;
24
  fa[ch[x][R]]=y;
25
  ch[y][L]=ch[x][R];
26
  ch[x][R]=y;
27
  pushup(y);pushup(x);
28
  return;
29
}
30
inline void Splay(int x,int& f)
31
{
32
  while(x!=f)
33
  {
34
    int y=fa[x],z=fa[y];
35
    if(y!=f)
36
    {
37
      if(ch[y][0]==x^ch[z][0]==y)Rot(x,f);
38
      else Rot(y,f);
39
    }
40
    Rot(x,f);
41
  }
42
  return;
43
}
44
inline int Find(int x,int k)
45
{
46
  int L=ch[x][0],R=ch[x][1];
47
  if(siz[L]+1==k)return x;
48
  if(siz[L]+1>k)return Find(L,k);
49
  return Find(R,k-siz[L]-1);
50
}
51
inline void Build(int L,int R,int pre)
52
{
53
  if(L>R)return;
54
  int mid=(L+R)>>1;
55
  if(L==R)
56
  {
57
    maxx[mid]=a[mid-1];
58
    siz[mid]=1;
59
    ch[mid][0]=ch[mid][1]=0;
60
  }
61
  else
62
  {
63
    Build(L,mid-1,mid);
64
    Build(mid+1,R,mid);
65
  }
66
  val[mid]=a[mid-1];
67
  fa[mid]=pre;
68
  pushup(mid);
69
  ch[pre][mid>=pre]=mid;
70
  return;
71
}
72
inline int Delete(int x)
73
{
74
  int L=Find(rt,x),R=Find(rt,x+2);
75
  Splay(L,rt);
76
  Splay(R,ch[L][1]);
77
  int tmp=val[ch[R][0]];
78
  siz[ch[R][0]]=0;
79
  fa[ch[R][0]]=0;
80
  ch[R][0]=0;
81
  pushup(R);
82
  pushup(L);
83
  return tmp;
84
}
85
inline void Insert(int x,int value)
86
{
87
  int L=Find(rt,x+1),R=Find(rt,x+2);
88
  Splay(L,rt);
89
  Splay(R,ch[L][1]);
90
  fa[++cnt]=R;
91
  val[cnt]=maxx[cnt]=value;
92
  siz[cnt]=1;
93
  ch[R][0]=cnt;
94
  pushup(R);
95
  pushup(L);
96
  return;
97
}
98
inline int Ask(int x,int y)
99
{
100
  int L=Find(rt,x),R=Find(rt,y+2);
101
  Splay(L,rt);
102
  Splay(R,ch[L][1]);
103
  return maxx[ch[R][0]];
104
}
105
int main(void)
106
{
107
  int i,n,m,x,y;
108
  char dir;
109
  scanf("%d%d",&n,&m);
110
  for(i=1;i<=n;++i)scanf("%d",&a[i]);
111
  Build(1,n+2,0);
112
  rt=n+3>>1;
113
  cnt=n+2;
114
  for(i=1;i<=m;++i)
115
  {
116
    scanf("%d %c %d",&x,&dir,&y);
117
    if(dir=='L')printf("%d\n",Ask(x-y,x-1));
118
    if(dir=='D')printf("%d\n",Ask(x+1,x+y));
119
    int tmp=Delete(x);
120
    if(dir=='L')Insert(x-y-1,tmp);
121
    if(dir=='D')Insert(x+y-1,tmp);
122
  }
123
  return 0;
124
}