#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template <class T> bool ckmin(T& a, const T& b) {return a > b ? a = b, true : false;}
template <class T> bool ckmax(T& a, const T& b) {return a < b ? a = b, true : false;}
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int n, m, k;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ar array
struct treap{
char data;
int pr, sz;
ar<treap*, 2> kids;
treap(char data);
};
int size(treap* me){
return me == NULL? 0:me->sz;
}
void recalc(treap *me){
if(me == NULL)return;
me->sz = 1;
for(treap* t:me->kids)if(t != NULL)me->sz += t->sz;
}
treap* merge(treap *l, treap *r){
if(l == NULL)return r;
if(r == NULL)return l;
if(l->pr < r->pr){
l->kids[1] = merge(l->kids[1], r);
recalc(l);
return l;
}else {
r->kids[0] = merge(l, r->kids[0]);
recalc(r);
return r;
}
}
ar<treap*, 2> split(treap *me, int pos){
if(me == NULL)return {NULL, NULL};
if(size(me->kids[0]) >= pos){
ar<treap*, 2> left = split(me->kids[0], pos);
me->kids[0] = left[1];
recalc(me);
return {left[0], me};
}else {
pos -= size(me->kids[0])+1;
ar<treap*, 2> right= split(me->kids[1], pos);
me->kids[1] = right[0];
recalc(me);
return {me, right[1]};
}
}
treap::treap(char data){
kids = {NULL, NULL};
this->data = data;
recalc(this);
int t = uniform_int_distribution<int>(0, N)(rng);
this->pr = t;
}
void show(treap *me){
if(me == NULL)return;
show(me->kids[0]);
cout << (me->data);
show(me->kids[1]);
}
void solve(int test_case){
int i, j;
cin >> n >> m;
char c;
cin >> c;
treap *root = new treap(c);
for(i=1;i<n;i++){
cin >> c;
treap *tmp = new treap(c);
root = merge(root, tmp);
}
while(m--){
char type;
cin >> type;
if(type == 'a'){
int l, r;
cin >> l >> r;
l--,r--;
if(l <= r){
ar<treap*, 2> tmp = split(root, l);
ar<treap*, 2> tmp2= split(tmp[1], 1);
ar<treap*, 2> tt = split(tmp2[1], r-l);
root = merge(tmp[0], tt[0]);
root = merge(root, tmp2[0]);
root = merge(root, tt[1]);
}else {
ar<treap*, 2> tmp = split(root, l);
ar<treap*, 2> tmp2= split(tmp[0], r);
ar<treap*, 2> tt = split(tmp[1], 1);
root = merge(tmp2[0], tt[0]);
root = merge(root, tmp2[1]);
root = merge(root, tt[1]);
}
}else {
int p;
cin >> p;
p--;
ar<treap*, 2> tmp = split(root, p);
ar<treap*, 2> tmp2 = split(tmp[1], 1);
char ans = tmp2[0]->data;
root = merge(tmp[0], merge(tmp2[0], tmp2[1]));
cout << ans << '\n';
}
}
return;
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int _T;
cin >> _T;
for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
collider.cpp: In function 'void solve(int)':
collider.cpp:80:9: warning: unused variable 'j' [-Wunused-variable]
80 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
10 ms |
364 KB |
Output is correct |
| 3 |
Correct |
26 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
155 ms |
37856 KB |
Output is correct |
| 5 |
Correct |
212 ms |
37996 KB |
Output is correct |
| 6 |
Correct |
205 ms |
42604 KB |
Output is correct |
| 7 |
Correct |
231 ms |
47360 KB |
Output is correct |
| 8 |
Correct |
195 ms |
47340 KB |
Output is correct |
| 9 |
Correct |
231 ms |
47340 KB |
Output is correct |
| 10 |
Correct |
211 ms |
47340 KB |
Output is correct |
