#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct splay_tree{
struct node{
node* p;
array<node*, 2> ch;
int sz;
T x;
node(T x): p(nullptr), ch({nullptr, nullptr}), sz(1), x(x){
}
};
node* root = nullptr;
splay_tree(){
}
node* dfs(vector<T> &A, int L, int R){
if (L == R){
return nullptr;
}
int m = (L + R) / 2;
node* v = new node(A[m]);
node* l = dfs(A, L, m);
v->ch[0] = l;
if (l != nullptr){
l->p = v;
}
node* r = dfs(A, m + 1, R);
v->ch[1] = r;
if (r != nullptr){
r->p = v;
}
update(v);
return v;
}
splay_tree(vector<T> A){
root = dfs(A, 0, A.size());
}
int size(node* v){
if (v == nullptr){
return 0;
}
return v->sz;
}
int size(){
return size(root);
}
void update(node* v){
v->sz = 1 + size(v->ch[0]) + size(v->ch[1]);
}
void update_child(node* v, node *w){
w->p = v->p;
if (v->p == nullptr){
return;
}
if (v->p->ch[0] == v){
v->p->ch[0] = w;
} else {
v->p->ch[1] = w;
}
}
void rotate_left(node* v){
node* w = v->ch[1];
update_child(v, w);
v->ch[1] = w->ch[0];
if (w->ch[0] != nullptr){
w->ch[0]->p = v;
}
v->p = w;
w->ch[0] = v;
update(v);
update(w);
}
void rotate_right(node* v){
node* w = v->ch[0];
update_child(v, w);
v->ch[0] = w->ch[1];
if (w->ch[1] != nullptr){
w->ch[1]->p = v;
}
v->p = w;
w->ch[1] = v;
update(v);
update(w);
}
void splay(node* v){
while (v->p != nullptr){
node* p = v->p;
if (p->p == nullptr){
if (v == p->ch[0]){
rotate_right(p);
} else {
rotate_left(p);
}
} else {
node* g = p->p;
if (v == p->ch[0]){
if (p == g->ch[0]){
rotate_right(g);
rotate_right(p);
} else {
rotate_right(p);
rotate_left(g);
}
} else {
if (p == g->ch[0]){
rotate_left(p);
rotate_right(g);
} else {
rotate_left(g);
rotate_left(p);
}
}
}
}
root = v;
}
node* get(int k){
node* res = root;
while (true){
if (res->ch[0] != nullptr){
if (k < res->ch[0]->sz){
res = res->ch[0];
continue;
}
k -= res->ch[0]->sz;
}
if (k == 0){
splay(res);
return res;
}
k--;
res = res->ch[1];
}
}
T operator [](int k){
return get(k)->x;
}
void insert(int k, T x){
node* v = new node(x);
if (k == size(root)){
v->ch[0] = root;
if (root != nullptr){
root->p = v;
}
root = v;
update(v);
} else {
node* u = get(k);
v->ch[0] = u->ch[0];
v->ch[1] = u;
if (u->ch[0] != nullptr){
u->ch[0]->p = v;
}
u->ch[0] = nullptr;
u->p = v;
update(u);
update(v);
root = v;
}
}
void erase(node* v){
node* l = v->ch[0];
node* r = v->ch[1];
delete v;
if (l == nullptr && r == nullptr){
root = nullptr;
} else if (l == nullptr){
root = r;
r->p = nullptr;
} else if (r == nullptr){
root = l;
l->p = nullptr;
} else {
r->p = nullptr;
root = r;
r = get(0);
r->ch[0] = l;
l->p = r;
update(r);
}
}
void erase(int k){
erase(get(k));
}
};
int main(){
int n, m;
cin >> n >> m;
vector<char> c(n);
for (int i = 0; i < n; i++){
cin >> c[i];
}
splay_tree<char> ST(c);
for (int i = 0; i < m; i++){
char t;
cin >> t;
if (t == 'a'){
int x, y;
cin >> x >> y;
x--;
y--;
splay_tree<char>::node* v = ST.get(x);
char ans = v->x;
ST.erase(v);
ST.insert(y, ans);
}
if (t == 'q'){
int x;
cin >> x;
x--;
cout << ST[x] << endl;
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
15 ms |
456 KB |
Output is correct |
| 3 |
Correct |
20 ms |
5248 KB |
Output is correct |
| 4 |
Correct |
91 ms |
40260 KB |
Output is correct |
| 5 |
Correct |
104 ms |
40268 KB |
Output is correct |
| 6 |
Correct |
124 ms |
45260 KB |
Output is correct |
| 7 |
Correct |
131 ms |
50292 KB |
Output is correct |
| 8 |
Correct |
107 ms |
50164 KB |
Output is correct |
| 9 |
Correct |
141 ms |
50296 KB |
Output is correct |
| 10 |
Correct |
123 ms |
50292 KB |
Output is correct |
