Reversals

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>

using namespace std;
typedef long long ll;

struct node {
	char val;
	int prio, size;
	bool lzinv;
	node *left, *right;

	node (char v) {
		val = v;
		prio = rand();
		size = 1;
		lzinv = false;
		left = nullptr;
		right = nullptr;
	}
};

int gsize(node *s) {
	if (s == nullptr) return 0;
	return s->size;
}

void upd(node *s) {
	if (s == nullptr) return;
	s-> size = gsize(s->left) + 1 + gsize(s->right);
}

void push(node *s) {
	if (s == nullptr) return;

	if (s->lzinv) {
		swap(s->left, s->right);
	}

	if (s->left != nullptr) {
		if (s->lzinv) {
			s->left->lzinv = !s->left->lzinv;
		}
	}
	if (s->right != nullptr) {
		if (s->lzinv) {
			s->right->lzinv = !s->right->lzinv;
		}
	}
	s->lzinv = false;
}

void split(node *t, node *&l, node *&r, int k) {
	push(t);
	if (t == nullptr) {
		l = nullptr;
		r = nullptr;
		return;
	}
	if (k >= gsize(t->left)+1) {
		split(t->right, t->right, r, k-(gsize(t->left)+1));
		l = t;
	}
	else {
		split(t->left, l, t->left, k);
		r = t;
	}
	upd(t);
}

void merge(node *&t, node *l, node *r) {
	push(l);
	push(r);
	if (l == nullptr) {
		t = r;
	}
	else if (r == nullptr) {
		t = l;
	}
	else {
		if (l->prio >= r->prio) {
			merge(l->right, l->right, r);
			t = l;
		}
		else {
			merge(r->left, l, r->left);
			t = r;
		}
	}
	upd(t);
}

void rangeInv(node *&t, int a, int b) {
	node *cl, *cur, *cr;
	int tsz = gsize(t);
	bool lsplit = false;
	bool rsplit = false;
	cur = t;
	if (a > 1) {
		split(cur, cl, cur, a-1);
		lsplit = true;
	}
	if (b < tsz) {
		split(cur, cur, cr, b-a+1);
		rsplit = true;
	}
	cur->lzinv = !cur->lzinv;
	if (lsplit) {
		merge(cur, cl, cur);
	}
	if (rsplit) {
		merge(cur, cur, cr);
	}
	t = cur;
}

string trav(node *s) {
	push(s);
	string res = "";
	if (s == nullptr) return res;
	res += trav(s->left);
	res += s->val;
	res += trav(s->right);
	return res;
}

int n, m;
string cs;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	srand(time(NULL));
	cin >> n >> m;
	cin >> cs;

	node *tree = nullptr;
	for (int i = 1; i <= n; ++i) {
		node *nw = new node(cs[i-1]);
		merge(tree, tree, nw);
	}

	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		rangeInv(tree, a, b);
	}

	string res = trav(tree);
	cout << res << "\n";
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED