Reversals

#include <bits/stdc++.h>
using namespace std;
typedef struct node* pnode;
struct node {
	pnode l, r;
	int pr, c;
	bool flipped;
	char val;
	node(char v) {
		l=0;r=0;c=1;pr=rand();
		val = v;
		flipped = false;
	}
};
int cnt(pnode t) {
	if (t) return t->c;
	return 0;
}
void upd(pnode t) {
	if (t) t->c=cnt(t->l)+cnt(t->r)+1;
}
void push(pnode t) {
	if (t) {
		if (t->flipped) {
			t->flipped = false;
			swap(t->r, t->l);
			if (t->r) t->r->flipped ^= 1;
			if (t->l) t->l->flipped ^= 1;
		}
	}
}
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);
}

void print(pnode t) {
	if (t) {
		push(t);
		print(t->l);
		cout << t->val;
		print(t->r);
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	pnode treap = 0;
	for (char c : s) {
		merg(treap, treap, new node(c));
	}
	//print(treap); cout << "\n";

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		pnode left, mid, right;
		split(treap, left, mid, a);
		split(mid, mid, right, b-a+1);
		//print(left);cout<<"-"; print(mid);cout<<"-"; print(right);cout<<endl;
		mid->flipped ^= 1;
		treap = 0;
		merg(treap, left, mid);
		merg(treap, treap, right);
	}

	print(treap);
	cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED