Reversals

#include <iostream>
#include <random>
#include <string>

struct Treap {
	Treap* left;
	Treap* right;
	bool flip;
	int ind;
	int size;
	int pri;

	Treap (int i) {
		left = 0;
		right = 0;
		flip = false;
		ind = i;
		size = 1;
		pri = rand();
	}
};

int getsize(Treap* a) {
	if (a == 0) return 0;
	return a->size;
}

void push(Treap* a) {
	if (a == 0) return;
	if (a->flip) {
		auto temp = a->left;
		a->left = a->right;
		a->right = temp;
		if (a->left) a->left->flip ^= 1;
		if (a->right) a->right->flip ^= 1;
		a->flip = false;
	}
}

void print2(Treap* a) {
	if (a == 0) return;
	std::cout << "("; print2(a->left); std::cout << ")";
	std::cout << a->ind;
	std::cout << "("; print2(a->right); std::cout << ")";
}

void join(Treap*& res, Treap* a, Treap* b) {
	if (a == 0) res = b;
	else if (b == 0) res = a;
	else {
		push(a);
		push(b);
		if ( (a->pri) > (b->pri) ) {
			join(a->right, a->right, b);
			res = a;
		} else {
			join(b->left, a, b->left);
			res = b;
		}
		res->size = getsize(res->left) + getsize(res->right) + 1;
	}
}

// ind and everything less goes to left size (a).
void split(int ind, Treap* source, Treap*& a, Treap*& b) {
	// std::cout << "split called for source="; print2(source); std::cout << ", a="; print2(a); std::cout << ", b="; print2(b); std::cout << '\n';
	if (source == 0) {
		a = 0;
		b = 0;
		return;
	}
	push(source);
	int ls = getsize(source->left);
	// std::cout << "split\n";
	// print2(source); std::cout << '\n';
	
	if (ls <= ind) {
		split(ind - ls - 1, source->right, source->right, b);
		a = source;
		a->size = getsize(a->left) + getsize(a->right) + 1;
	} else {
		split(ind, source->left, a, source->left);
		b = source;
		b->size = getsize(b->left) + getsize(b->right) + 1;
	}
}

void print(std::string& str, Treap* a) {
	if (a == 0) return;
	push(a);
	print(str, a->left);
	std::cout << str[a->ind];
	print(str, a->right);
}


int main() {
	int n, m;
	std::cin >> n >> m;
	std::string str;
	std::cin >> str;
	Treap* root = 0;
	for (int i = 0; i < n; ++i) {
		Treap* single = new Treap(i);
		join(root, root, single);
	}
	// print(str, root); std::cout << "\n";
	// print2(root);
	for (int i = 0; i < m; ++i) {
		int a, b;
		std::cin >> a >> b;
		a -= 2; --b;
		Treap* left = 0;
		Treap* right = 0;
		split(b, root, root, right);
		// print(str, root); std::cout << "\n";
		// print(str, right); std::cout << "\n";
		// print2(root); std::cout << "\n";
		// print2(right); std::cout << "\n";
		split(a, root, left, root);
		// print(str, left); std::cout << "\n";
		// print(str, root); std::cout << "\n";
		// print(str, right); std::cout << "\n";
		if (root != 0) root->flip = true;
		join(root, left, root);
		join(root, root, right);
	}
	print(str, root); std::cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED