Reversals

#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;

typedef struct node* pnode;
struct node{
  pnode l, r;
  int pr, c;
  bool rv;
  int id;
  node(){
    l=0; r=0; c=1; pr=rand(); rv=0; id=0;
  }
};

inline int cnt(pnode t){
  if (t) return t->c;
  return 0;
}

inline void upd(pnode t){
  if (t) t->c=cnt(t->l)+cnt(t->r)+1;
}

inline void rev(pnode t){
  if (t) t->rv=!t->rv;
}

inline void push(pnode t){
  if (t){
    if (t->rv){
      swap(t->l, t->r);
      rev(t->l); rev(t->r);
      t->rv=0;
    }
  }
}

void merg(pnode& t, pnode l, pnode r){
  push(l); push(r);
  if (!l) t=r;
  else if (!r) t=l;
  else{
    if (l->pr>r->pr){
      merg(l->r, l->r, r); t=l;
    }else{
      merg(r->l, l, r->l); t=r;
    }
  }
  upd(t);
}

void split(pnode t, pnode& l, pnode& r, int k){
  if (!t){
    l=0; r=0; return;
  }else{
    push(t);
    if (cnt(t->l)>=k){
      split(t->l, l, t->l, k); r=t;
    }else{
      split(t->r, t->r, r, k-cnt(t->l)-1); l=t;
    }
  }
  upd(t);
}


node nodes[505050];
pnode root;

void print(pnode c){
  if (!c) return;
  push(c);
  print(c->l);
  cout << s[c->id];
  print(c->r);
}

int main(){
  for (int i=0; i<505050; ++i) nodes[i].id=i;
//   ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  cin >> s;
  for (int i=0; i<n; ++i) merg(root, root, &(nodes[i]));

  for (int i=0; i<m; ++i){
    int a, b;
    cin >> a >> b; --a; --b;
    pnode l, r;
    split(root, l, root, a);
    split(root, root, r, (b-a+1));
    rev(root);
    merg(root, l, root);
    merg(root, root, r);
  }
  print(root); cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED