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
125
126
127
128
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
const int maxn = 2100005;
int c[maxn][2], rev[maxn], fa[maxn], siz[maxn], tot = 0, root;
char ch[maxn];
void pd(int x) {
if (rev[x]) {
int &l = c[x][0], &r = c[x][1];
if (l) rev[l] ^= 1;
if (r) rev[r] ^= 1;
rev[x] = 0;
swap(l, r);
}
}
void pu(int x) {
siz[x] = 1;
if (c[x][0]) siz[x] += siz[c[x][0]];
if (c[x][1]) siz[x] += siz[c[x][1]];
}
int build(int l, int r, char *str) {
if (l > r) return 0;
int mid = (l + r) >> 1, ret = ++tot;
c[ret][0] = build(l, mid - 1, str);
c[ret][1] = build(mid + 1, r, str);
fa[c[ret][0]] = fa[c[ret][1]] = ret;
ch[ret] = str[mid];
pu(ret);
return ret;
}
void rotate(int x) {
int y = fa[x], z = fa[y], a = (c[y][1] == x), b = a ^ 1;
if (z) {c[z][c[z][1]==y]=x;}
fa[x] = z; fa[y] = x; fa[c[x][b]] = y;
c[y][a] = c[x][b]; c[x][b] = y;
fa[0] = 0;
pu(y); pu(x);
}
void splay(int x, int pos = 0) {
while (fa[x] != pos) {
int y = fa[x], z = fa[y];
if (z != pos) {
if (c[z][0] == y ^ c[y][0] == x) rotate(x);
rotate(y);
}
rotate(x);
}
if (pos == 0) root = x;
}
int K(int x, int k) {
pd(x);
int l = c[x][0], ls = siz[l];
if (k == ls + 1) return x;
if (k <= ls) return K(l, k);
return K(c[x][1], k - ls - 1);
}
void rever(int pos1, int pos2) {
int L = K(root, pos1 + 1), R = K(root, pos2 + 2);
splay(L);
splay(R, L);
rev[c[R][0]] ^= 1;
}
void delet(int pos1, int pos2) {
int L = K(root, pos1 + 1), R = K(root, pos2 + 2);
splay(L);
splay(R, L);
c[R][0] = 0;
pu(R); pu(L);
}
void inser(int pos, char *str, int len) {
int L = K(root, pos + 1), R = K(root, pos + 2);
splay(L);
splay(R, L);
c[R][0] = build(0, len - 1, str);
pu(R); pu(L);
fa[c[R][0]] = R;
}
char query(int pos) {
int L = K(root, pos + 2);
splay(L);
return ch[L];
}
int n;
char str[maxn], opt[10];
int main() {
scanf("%d", &n);
root = build(0, 1, str);
int ptr = 0, x;
while (n--) {
scanf("%s", opt);
if (opt[0] == 'M') {
scanf("%d", &ptr);
continue;
}
if (opt[0] == 'I') {
scanf("%d", &x);
gets(str);
gets(str);
inser(ptr, str, x);
continue;
}
if (opt[0] == 'D') {
scanf("%d", &x);
delet(ptr, ptr + x);
continue;
}
if (opt[0] == 'R') {
scanf("%d", &x);
rever(ptr, ptr + x);
continue;
}
if (opt[0] == 'G') {
printf("%c\n", query(ptr));
continue;
}
if (opt[0] == 'P') {
--ptr;
continue;
}
if (opt[0] == 'N') {
++ptr;
continue;
}
}
return 0;
}
|
