Maratona Visagio - Problema B

B.cpp

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

ll pa(ll a, ll b) {
	ll n = (b - a + 1);
	return (a + b) * n / 2;
}

struct node {
	node *l, *r, *p;
	int a, b, s;
	int rev, lazy;
	ll sum;
	node(int a, int b) : l(nullptr), r(nullptr), p(nullptr), a(a), b(b), s(b - a + 1), rev(0), lazy(0), sum(0) { }
};
 
using tree = node*;
 
tree left(tree t) {return t ? t->l : nullptr;}
tree right(tree t) {return t ? t->r : nullptr;}
tree p(tree t) {return t ? t->p : nullptr;}
tree g(tree t) {return p(p(t));}
 
int size(tree t) {return t ? t->s : 0;}

void fix(tree t) {
	if (t) t->s = (t->b - t->a + 1) + size(left(t)) + size(right(t));
}
 
void update(tree t) {
	t->sum = pa(t->a, t->b);
	if (t->l) t->sum += t->l->sum;
	if (t->r) t->sum += t->r->sum;
}
 
void push(tree t) {
	if (t->lazy) {
		t->rev ^= 1;
		if (t->l) t->l->lazy ^= 1;
		if (t->r) t->r->lazy ^= 1;
		swap(t->l, t->r);
		t->lazy = 0;
	}
}

void print(tree t) {
	if (t) {
		push(t);
		print(left(t));
		printf("[%d, %d, %d] ", t->a, t->b, t->rev);
		print(right(t));
	}
}
 
void link_left(tree t, tree c) {
	t->l = c;
	if (c) c->p = t;
	fix(t);
	update(t);
}
 
void link_right(tree t, tree c) {
	t->r = c;
	if (c) c->p = t;
	fix(t);
	update(t);
}
 
void rotate_left(tree t) {
	tree x = right(t), y = p(t);
	link_right(t, left(x));
	link_left(x, t);
 
	if (t == left(y)) link_left(y, x);
	else if (t == right(y)) link_right(y, x);
	else x->p = nullptr;
}
 
void rotate_right(tree t) {
	tree x = left(t), y = p(t);
	link_left(t, right(x));
	link_right(x, t);
 
	if (t == left(y)) link_left(y, x);
	else if (t == right(y)) link_right(y, x);
	else x->p = nullptr; 
}
 
tree splay(tree t) {
	do {
		if (t == left(p(t))) {
			if (!g(t)) {
				rotate_right(p(t));
			} else if (p(t) == left(g(t))) {
				rotate_right(g(t));
				rotate_right(p(t));
			} else {
				rotate_right(p(t));
				rotate_left(p(t));
			}
		}
 
		if (t == right(p(t))) {
			if (!g(t)) {
				rotate_left(p(t));
			} else if (p(t) == right(g(t))) {
				rotate_left(g(t));
				rotate_left(p(t));
			} else {
				rotate_left(p(t));
				rotate_right(p(t));
			}
		}
	} while (p(t));
	return t;
}

tree join(tree t1, tree t2) {
	if (!t1 || !t2) return t1 ? t1 : t2;
	push(t1);
	while (right(t1)) {
		t1 = right(t1);
		push(t1);
	}
	splay(t1);
	link_right(t1, t2);
	return t1;
}

tree max(tree t) {
	if (!t) return nullptr;
	push(t);
	if (t->r) return max(t->r);
	return splay(t);
}

tree upper_bound(tree t, int key, tree& ub) {
	if (!t) return nullptr;
	push(t);
	int at = size(t->l) + 1;
	if (at > key) {
		ub = t;
		tree x = upper_bound(t->l, key, ub);
		return x ? x : splay(t);
	} else {
		tree x = upper_bound(t->r, key - size(t->l) - (t->b - t->a + 1), ub);
		return x ? x : splay(t);
	}
}

tree expose(tree t, int l) {
	assert(t);

	tree ub = nullptr;
	t = upper_bound(t, l, ub);

	if (ub) {
		t = splay(ub);
		assert(t->l);
		t = t->l;
	}

	t = max(t);

	int at = size(t->l) + 1;
	assert(at <= l);

	tree t1 = t->l;
	tree t2 = t->r;
	link_left(t, nullptr);
	link_right(t, nullptr);

	if (t1) t1->p = nullptr;
	if (t2) t2->p = nullptr;

	tree n1 = nullptr;
	int s1 = l - at;
	if (s1 > 0) {
		int a = t->rev ? (t->b - s1 + 1) : t->a;
		n1 = new node(a, a + s1 - 1);
		n1->rev = t->rev;
	}

	int s2 = (t->b - t->a + 1) - (l - at);
	int a = t->rev ? t->a : (t->a + s1);

	tree n2 = new node(a, a + s2 - 1);
	n2->rev = t->rev;

	delete t;

	t = join(t1, n1);
	t = join(t, n2);
	t = join(t, t2);

	return t;
}
 
tree find(tree t, int key) {
	if (!t) return t;
	push(t);
	int at = size(left(t));
	if (key == at) return splay(t);
	if (key < at) {
		tree x = find(left(t), key);
		return x ? x : splay(t);
	}
 
	tree x = find(right(t), key - at - (t->b - t->a + 1));
	return x ? x : splay(t);
}
 
pair<tree, tree> split(tree t, int k) {
	if (!t) return make_pair(nullptr, nullptr);
	if (k >= size(t)) return make_pair(t, nullptr);
	t = find(t, k);
	tree l = left(t), r = t;
	if (l) l->p = nullptr;
	link_left(r, nullptr);
	return make_pair(l, r);
}
 
tree reverse(tree t, int l, int r) {
	tree t1, t2, t3;
	tie(t1, t2) = split(t, l);
	tie(t2, t3) = split(t2, r - l + 1);
	assert(t2);
	t2->lazy ^= 1;
	return join(t1, join(t2, t3));
}

tree query(tree t, int l, int r, ll& ans) {
	tree t1, t2, t3;
	tie(t1, t2) = split(t, l);
	tie(t2, t3) = split(t2, r - l + 1);
	ans = t2->sum;
	return join(t1, join(t2, t3));
}
 
int main() {
	ios::sync_with_stdio(false);

	int n, q; cin >> n >> q;

	tree root = new node(1, n);

	while (q--) {
		char op; cin >> op;
		int l, r; cin >> l >> r;

		root = expose(root, l);
		if (r + 1 <= n) root = expose(root, r + 1);

		if (op == 'I') {
			root = reverse(root, l - 1, r - 1);
		} else {
			ll ans;
			root = query(root, l - 1, r - 1, ans);
			cout << ans << "\n";
		}
	}


	return 0;
}