Shared code

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, from, to) for (int i = from; i < (to); ++i)
 
// begin KACTL
 
 
struct Node {
	Node* l = 0, * r = 0;
	int val, y, c = 1;
	Node(int val) : val(val), y(rand()) {}
	void recalc();
};
 
int cnt(Node * n) { return n ? n->c : 0; }
void Node::recalc() { c = cnt(l) + cnt(r) + 1; }
 
template<class F> void each(Node * n, F f) {
	if (n) { each(n->l, f); f(n->val); each(n->r, f); }
}
 
pair<Node*, Node*> split(Node * n, int k) {
	if (!n) return {};
	if (cnt(n->l) >= k) { // "n->val >= k" for lower_bound(k)
		auto pa = split(n->l, k);
		n->l = pa.second;
		n->recalc();
		return { pa.first, n };
	}
	else {
		auto pa = split(n->r, k - cnt(n->l) - 1); // and just "k"
		n->r = pa.first;
		n->recalc();
		return { n, pa.second };
	}
}
 
Node* merge(Node * l, Node * r) {
	if (!l) return r;
	if (!r) return l;
	if (l->y > r->y) {
		l->r = merge(l->r, r);
		l->recalc();
		return l;
	}
	else {
		r->l = merge(l, r->l);
		r->recalc();
		return r;
	}
}
 
Node* ins(Node * t, Node * n, int pos) {
	auto pa = split(t, pos);
	return merge(merge(pa.first, n), pa.second);
}
 
// Example application: move the range [l, r) to index k
void move(Node * &t, int l, int r, int k) {
	Node* a, * b, * c;
	tie(a, b) = split(t, l); tie(b, c) = split(b, r - l);
	if (k <= l) t = merge(ins(a, b, k), c);
	else t = merge(a, ins(c, b, k - r));
}
//end KACTL
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	Node* root = 0;
	for (int i = 0; i < n; i++)
	{
		Node* e = new Node(s[i]);
		root = merge(root, e);
	}
	for (int i = 0; i < q; i++)
	{
		int l, r;
		cin >> l >> r;
		l--; r--;
		move(root, l, r + 1, n);
	}
	each(root, [](int x)
		{
			cout << (char)x;
		});
 
	return 0;
}