#include <bits/stdc++.h>
#define MN 1007171
#define INF 1000000000
using namespace std;
struct nod {
char v;
int c, p;
nod *l, *r;
} *nil = new nod{0, 0, 0, 0, 0};
using ns = nod *;
struct pns {
ns l, r;
};
ns mod_fiu(ns b, int s, ns f) {
(s ? b->r : b->l) = f;
b->c = 1 + b->l->c + b->r->c;
return b;
}
ns join(ns a, ns b) {
return a == nil ? b :
b == nil ? a :
(a->p > b->p) ? mod_fiu(a, 1, join(a->r, b)) :
mod_fiu(b, 0, join(a, b->l));
}
pns split(ns a, int nr) {
pns t;
return a == nil ? pns{nil, nil} :
(a->c <= nr) ? pns{a, nil} :
!nr ? pns{nil, a} :
(a->l->c >= nr) ? (t = split(a->l, nr), t.r = mod_fiu(a, 0, t.r), t) :
(t = split(a->r, nr - a->l->c - 1), t.l = mod_fiu(a, 1, t.l), t);
}
void afis(ns a) {
if(a == nil) return;
afis(a->l);
cout << a->v;
afis(a->r);
}
ns root = nil;
int n, m;
char C[MN];
int main() {
srand(time(0));
cin >> n >> m >> (C+1);
for(int i = 1; i <= n; ++i)
root = join(root, new nod{C[i], 1, rand(), nil, nil});
char tip;
for(int i = 1, l, r; i <= m; ++i) {
cin >> tip;
if(tip == 'a') {
cin >> l >> r;
pns a = split(root, l - 1), b = split(a.r, 1);
root = join(a.l, b.r);
ns el = b.l;
a = split(root, r - (r > l) - 1);
root = join(join(a.l, el), a.r);
} else {
cin >> l;
pns a = split(root, l-1), b = split(a.r, 1);
cout << b.l->v << "\n";
root = join(a.l, join(b.l, b.r));
}
// cout << "\n";
// afis(root);
// cout << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
