#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m;
string s;
struct Node
{
Node *l, *r;
char val;
int prior,subtree;
Node(){}
Node(char _val)
{
l = nullptr;
r = nullptr;
val = _val;
prior = rand();
subtree = 1;
}
};
Node* root;
int get_subtree(Node* t)
{
if(t == nullptr) return 0;
return t->subtree;
}
void update_subtree(Node* t)
{
if(t == nullptr) return;
t->subtree = get_subtree(t->l)+get_subtree(t->r)+1;
return;
}
pair<Node*, Node*> split(Node* t, int key, int add)
{
if(t == nullptr) return {nullptr, nullptr};
int currKey = add+1+get_subtree(t->l);
if(currKey < key)
{
pair<Node*, Node*> tmp = split(t->r, key, currKey);
t->r = tmp.first;
update_subtree(t);
return {t,tmp.second};
}
else
{
pair<Node*, Node*> tmp = split(t->l, key, add);
t->l = tmp.second;
update_subtree(t);
return {tmp.first, t};
}
}
Node* merge_treaps(Node* t1, Node* t2)
{
if(t1 == nullptr) return t2;
if(t2 == nullptr) return t1;
if(t1->prior > t2->prior)
{
t1->r = merge_treaps(t1->r, t2);
update_subtree(t1);
return t1;
}
else
{
t2->l = merge_treaps(t1, t2->l);
update_subtree(t2);
return t2;
}
}
char get_value(int idx)
{
pair<Node*, Node*> tmp1 = split(root,idx,0);
pair<Node*, Node*> tmp2 = split(tmp1.second,2,0);
char ret = tmp2.first->val;
tmp1.second = merge_treaps(tmp2.first,tmp2.second);
root = merge_treaps(tmp1.first, tmp1.second);
return ret;
}
void erase_value(int idx)
{
pair<Node*, Node*> tmp1 = split(root,idx,0);
pair<Node*, Node*> tmp2 = split(tmp1.second,2,0);
root = merge_treaps(tmp1.first, tmp2.second);
return;
}
void insert_value(int idx,char new_val)
{
Node* newTreap = new Node(new_val);
pair<Node*, Node*> tmp = split(root,idx,0);
tmp.first = merge_treaps(tmp.first,newTreap);
root = merge_treaps(tmp.first, tmp.second);
return;
}
void update_treap(int old_idx, int new_idx)
{
char transit_value = get_value(old_idx);
erase_value(old_idx);
insert_value(new_idx, transit_value);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
cin>>s;
for(int i=0; i<n; i++)
{
insert_value(i+1,s[i]);
}
for(int i=0; i<m; i++)
{
char type;
int idx0,idx1;
cin>>type;
if(type == 'a')
{
cin>>idx0>>idx1;
if(idx0 <= idx1) update_treap(idx0,idx1-1);
else update_treap(idx0,idx1);
}
else
{
cin>>idx0;
cout<<get_value(idx0)<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
