#include<stdio.h>
#include<algorithm>
using namespace std;
const int N_ = 1e6 + 10;
const int inf = ~0u>>1;
//O(N + M lg N);
//이걸로 많이 우려먹는듯 ㅎㅎ
char inp[1000010];
class splaytree{
public:
splaytree(int N){
for(int i=0;i<N_;i++)ch[i][0] = ch[i][1] = down[i] = par[i] = 0;
rev[0] = false, val[0] = 0;
root = sz = 0;
make_node(root, 0);
make_node(ch[1][1], 0);
par[ch[1][1]] = 1;
down[1] = 2;
build(1,N,ch[ch[root][1]][0],ch[root][1]);
pushup(ch[root][1]), pushup(root);
}
int sz, root;
int down[N_], ch[N_][2], par[N_];
char val[N_];
bool rev[N_];
inline int dir(int x){return ch[par[x]][1] == x;}
inline void make_node(int &p,char v){
p = ++sz;
ch[p][0] = ch[p][1] = rev[p] = 0;
val[p] = v;
down[p] = 1;
}
void build(int s,int d,int &p,int u){
int m = (s+d)>>1;
make_node(p, inp[m]);
par[p] = u;
if(s<m)build(s,m-1,ch[p][0],p);
if(m<d)build(m+1,d,ch[p][1],p);
pushup(p);
}
inline void pushup(int x){
down[x] = down[ch[x][0]] + down[ch[x][1]] + 1;
}
inline void pushdown(int x){
if(rev[x]){
if(ch[x][0])rev[ch[x][0]]^=1;
if(ch[x][1])rev[ch[x][1]]^=1;
swap(ch[x][0],ch[x][1]);
rev[x] = 0;
}
}
inline void Rotate(int x){
int y = par[x];
pushdown(y), pushdown(x);
int d = dir(x);
ch[y][d] = ch[x][!d];
par[ch[x][!d]] = y;
ch[par[y]][dir(y)] = x;
par[x] = par[y];
par[y] = x, ch[x][!d] = y;
pushup(y);
}
inline void splay(int x,int f){
pushdown(x);
while(par[x]!=f){
if(par[par[x]] == f)Rotate(x);
else if(dir(x) == dir(par[x]))Rotate(par[x]), Rotate(x);
else Rotate(x), Rotate(x);
}
pushup(x);
if(f == 0)root = x;
}
inline void kth_splay(int k,int f){
int x = root;
pushdown(x);
while(down[ch[x][0]] != k){
if(down[ch[x][0]] > k)x = ch[x][0];
else k -= down[ch[x][0]]+1, x = ch[x][1];
pushdown(x);
}
splay(x, f);
}
inline void Reverse(int x,int y){
kth_splay(x-1,0);
kth_splay(y+1,root);
rev[ch[ch[root][1]][0]] ^= 1;
}
void quary(int x,int y){
if(x<y){
Reverse(x+1,y);
Reverse(x,y);
}
else{
Reverse(y,x-1);
Reverse(y,x);
}
}
char output(int x){
kth_splay(x,0);
return val[root];
}
};
int main()
{
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",inp+1);
splaytree st = splaytree(n);
int i, x, y;
char c[2];
for(i=0;i<m;i++){
scanf("%s",c);
if(c[0] == 'a'){
scanf("%d%d",&x,&y);
st.quary(x,y);
}
else{
scanf("%d",&x);
printf("%c\n",st.output(x));
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19524 KB |
Output is correct |
| 2 |
Correct |
12 ms |
19528 KB |
Output is correct |
| 3 |
Correct |
12 ms |
19528 KB |
Output is correct |
| 4 |
Correct |
36 ms |
19528 KB |
Output is correct |
| 5 |
Correct |
60 ms |
19524 KB |
Output is correct |
| 6 |
Correct |
76 ms |
19524 KB |
Output is correct |
| 7 |
Correct |
68 ms |
19528 KB |
Output is correct |
| 8 |
Correct |
44 ms |
19528 KB |
Output is correct |
| 9 |
Correct |
92 ms |
19528 KB |
Output is correct |
| 10 |
Correct |
68 ms |
19532 KB |
Output is correct |
