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
114
115
116
117
118
119
120
121
122
123
124
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[200005],maxx[200005],ch[200005][2],fa[200005],siz[200005],val[200005],rt,cnt;
inline void pushup(int x)
{
int L=ch[x][0],R=ch[x][1];
maxx[x]=max(val[x],max(maxx[L],maxx[R]));
siz[x]=siz[L]+siz[R]+1;
return;
}
inline void Rot(int x,int& f)
{
int y=fa[x],z=fa[y],L=(ch[y][0]!=x),R=(L^1);
if(y==f)f=x;
else
{
if(ch[z][0]==y)ch[z][0]=x;
else ch[z][1]=x;
}
fa[x]=z;fa[y]=x;
fa[ch[x][R]]=y;
ch[y][L]=ch[x][R];
ch[x][R]=y;
pushup(y);pushup(x);
return;
}
inline void Splay(int x,int& f)
{
while(x!=f)
{
int y=fa[x],z=fa[y];
if(y!=f)
{
if(ch[y][0]==x^ch[z][0]==y)Rot(x,f);
else Rot(y,f);
}
Rot(x,f);
}
return;
}
inline int Find(int x,int k)
{
int L=ch[x][0],R=ch[x][1];
if(siz[L]+1==k)return x;
if(siz[L]+1>k)return Find(L,k);
return Find(R,k-siz[L]-1);
}
inline void Build(int L,int R,int pre)
{
if(L>R)return;
int mid=(L+R)>>1;
if(L==R)
{
maxx[mid]=a[mid-1];
siz[mid]=1;
ch[mid][0]=ch[mid][1]=0;
}
else
{
Build(L,mid-1,mid);
Build(mid+1,R,mid);
}
val[mid]=a[mid-1];
fa[mid]=pre;
pushup(mid);
ch[pre][mid>=pre]=mid;
return;
}
inline int Delete(int x)
{
int L=Find(rt,x),R=Find(rt,x+2);
Splay(L,rt);
Splay(R,ch[L][1]);
int tmp=val[ch[R][0]];
siz[ch[R][0]]=0;
fa[ch[R][0]]=0;
ch[R][0]=0;
pushup(R);
pushup(L);
return tmp;
}
inline void Insert(int x,int value)
{
int L=Find(rt,x+1),R=Find(rt,x+2);
Splay(L,rt);
Splay(R,ch[L][1]);
fa[++cnt]=R;
val[cnt]=maxx[cnt]=value;
siz[cnt]=1;
ch[R][0]=cnt;
pushup(R);
pushup(L);
return;
}
inline int Ask(int x,int y)
{
int L=Find(rt,x),R=Find(rt,y+2);
Splay(L,rt);
Splay(R,ch[L][1]);
return maxx[ch[R][0]];
}
int main(void)
{
int i,n,m,x,y;
char dir;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)scanf("%d",&a[i]);
Build(1,n+2,0);
rt=n+3>>1;
cnt=n+2;
for(i=1;i<=m;++i)
{
scanf("%d %c %d",&x,&dir,&y);
if(dir=='L')printf("%d\n",Ask(x-y,x-1));
if(dir=='D')printf("%d\n",Ask(x+1,x+y));
int tmp=Delete(x);
if(dir=='L')Insert(x-y-1,tmp);
if(dir=='D')Insert(x+y-1,tmp);
}
return 0;
}
|