fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. std::mt19937_64 rnd(std::chrono::system_clock::now().time_since_epoch().count());
  5. struct Treap{
  6.     struct Node{
  7.         char key=0;
  8.         int rev=0,pri=rnd(),sz=1;
  9.         array<Node*,2>c={0,0};
  10.         Node(){}
  11.         Node(char k){
  12.             key=k;
  13.         }
  14.     };
  15.     Node*root=0;
  16.     int getSize(Node*t)
  17.     {
  18.         return t?t->sz:0;
  19.     }
  20.     Treap(string&s)
  21.     {
  22.         for(int i=0;i<s.size();i++)
  23.         {
  24.             root=merge(root,new Node(s[i]));
  25.         }
  26.     }
  27.     Node*fix(Node*t)
  28.     {
  29.         t->sz=getSize(t->c[0])+getSize(t->c[1])+1;
  30.         return t;
  31.     }
  32.     void propegate(Node*t)
  33.     {
  34.         if(!t||!t->rev) return;
  35.         swap(t->c[0],t->c[1]);
  36.         if(t->c[0]) t->c[0]->rev^=1;
  37.         if(t->c[1]) t->c[1]->rev^=1;
  38.         t->rev=0;
  39.     }
  40.     array<Node*,2>split(Node*t,int k)
  41.     {
  42.         if(!t) return {0,0};
  43.         propegate(t);
  44.         if(getSize(t->c[0])>=k)
  45.         {
  46.             auto ret=split(t->c[0],k);
  47.             t->c[0]=ret[1];
  48.             return {ret[0],fix(t)};
  49.         }
  50.         else
  51.         {
  52.             auto ret=split(t->c[1],k-getSize(t->c[0])-1);
  53.             t->c[1]=ret[0];
  54.             return {fix(t),ret[1]};
  55.         }
  56.     }
  57.     Node*merge(Node*u,Node*v)
  58.     {
  59.         propegate(u);
  60.         propegate(v);
  61.         if(!u||!v) return u?u:v;
  62.         if(u->pri>v->pri)
  63.         {
  64.             u->c[1]=merge(u->c[1],v);
  65.             return fix(u);
  66.         }
  67.         else
  68.         {
  69.             v->c[0]=merge(u,v->c[0]);
  70.             return fix(v);
  71.         }
  72.     }
  73.     void reverse(int l,int r)
  74.     {
  75.         auto a=split(root,l-1);
  76.         auto b=split(a[1],r-l+1);
  77.         b[0]->rev^=1;
  78.         root=merge(a[0],merge(b[0],b[1]));
  79.     }
  80.     char getChar(int idx)
  81.     {
  82.         auto a=split(root,idx-1);
  83.         auto b=split(a[1],1);
  84.         propegate(b[0]);
  85.         char ret=b[0]->key;
  86.         merge(a[0],merge(b[0],b[1]));
  87.         return ret;
  88.     }
  89.     void print(Node*t)
  90.     {
  91.         if(!t) return;
  92.         print(t->c[0]);
  93.         cout<<t->key<<' ';
  94.         print(t->c[1]);
  95.     }
  96. };
  97. signed main()
  98. {
  99.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  100.     int n,l,r;string s;cin>>n>>l>>r>>s;
  101.     Treap t(s);
  102.     int q;cin>>q;while(q--)
  103.     {
  104.         char op;cin>>op;
  105.         if(op=='S')
  106.         {
  107.             char a,b;cin>>a>>b;
  108.             if(a=='R')
  109.             {
  110.                 if(b=='L')
  111.                 {
  112.                     r--;
  113.                 }
  114.                 else
  115.                 {
  116.                     r++;
  117.                 }
  118.             }
  119.             else
  120.             {
  121.                 if(b=='L')
  122.                 {
  123.                     l--;
  124.                 }
  125.                 else
  126.                 {
  127.                     l++;
  128.                 }
  129.             }
  130.         }
  131.         else if(op=='R')
  132.         {
  133.             t.reverse(l,r);
  134.         }
  135.         else
  136.         {
  137.             char x;cin>>x;
  138.             if(x=='R')
  139.             {
  140.                 cout<<t.getChar(r);
  141.             }
  142.             else
  143.             {
  144.                 cout<<t.getChar(l);
  145.             }
  146.         }
  147.     }
  148.     return 0;
  149. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
11 2 6
abracadabra
12
Q L
Q R
R
Q L
Q R
S L R
S R R
Q L
Q R
R
Q L
Q R
stdout 
baabcddc
https://ideone.com/LbItfT
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!