#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(){
}
splay_tree(vector<T> A){
root = dfs(A, 0, A.size());
}
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;
}
bool empty(){
return root == nullptr;
}
int size(){
return size(root);
}
int size(node* v){
if (v == nullptr){
return 0;
}
return v->sz;
}
void update(node* v){
v->sz = 1 + size(v->ch[0]) + size(v->ch[1]);
}
int child_id(node *v){
if (v->p == nullptr){
return -1;
} else if (v->p->ch[0] == v){
return 0;
} else {
return 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(node* v, int c){
node* w = v->ch[c ^ 1];
update_child(v, w);
v->ch[c ^ 1] = w->ch[c];
if (w->ch[c] != nullptr){
w->ch[c]->p = v;
}
v->p = w;
w->ch[c] = v;
update(v);
update(w);
}
void splay(node* v){
while (v->p != nullptr){
node* p = v->p;
node* g = p->p;
int x = child_id(v);
int y = child_id(p);
if (y == -1){
rotate(p, x ^ 1);
} else if (x == y){
rotate(g, x ^ 1);
rotate(g, x ^ 1);
} else {
rotate(p, y);
rotate(g, x);
}
}
root = v;
}
node* get(int k){
node* res = root;
while (true){
int s = size(res->ch[0]);
if (k < s){
res = res->ch[0];
} else if (k == s){
splay(res);
return res;
} else {
k -= s + 1;
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 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
