序列终结者 LeeRinji

题目链接 说是终结者其实是这题的真子集…

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct FhqTreap
{
	struct Node
	{
		int ch[2], siz, rev;
		ll key, val, max, add;
		void REV()
		{
			rev ^= 1, swap(ch[0], ch[1]);
		}
		void ADD(ll v)
		{
			val += v, max += v, add += v;
		}
	};
	vector<Node> v;
	int root;
	FhqTreap() : v(1), root(0) {}
	void push_down(int k)
	{
		if (!k)
			return;
		for (int i = 0, *ch = v[k].ch; i < 2; ++i)
			if (ch[i])
			{
				v[ch[i]].ADD(v[k].add);
				if (v[k].rev)
					v[ch[i]].REV();
			}
		v[k].add = v[k].rev = 0;
	}
	void push_up(int k)
	{
		if (!k)
			return;
		v[k].siz = 1, v[k].max = v[k].val;
		for (int i = 0, *ch = v[k].ch; i < 2; ++i)
			if (ch[i])
				v[k].siz += v[ch[i]].siz, v[k].max = max(v[k].max, v[ch[i]].max);
	}
	int merge(int a, int b)
	{
		if (!a || !b)
			return a + b;
		if (v[a].key < v[b].key)
			return push_down(a), v[a].ch[1] = merge(v[a].ch[1], b), push_up(a), a;
		return push_down(b), v[b].ch[0] = merge(a, v[b].ch[0]), push_up(b), b;
	}
	void split(int a, int s, int &l, int &r)
	{
		if (!s)
			l = 0, r = a;
		else if (v[v[a].ch[0]].siz < s)
			push_down(a), split(v[a].ch[1], s - v[v[a].ch[0]].siz - 1, v[a].ch[1], r), push_up(l = a);
		else
			push_down(a), split(v[a].ch[0], s, l, v[a].ch[0]), push_up(r = a);
	}
	void push_back(ll d)
	{
		v.push_back(Node{{0, 0}, 1, 0, rand(), d, d, d});
		root = merge(root, v.size() - 1);
	}
	void add(int l, int r, ll d)
	{
		int a, b, c;
		split(root, r, b, c), split(b, l - 1, a, b), v[b].ADD(d), root = merge(merge(a, b), c);
	}
	Node ask(int l, int r)
	{
		int a, b, c;
		split(root, r, b, c), split(b, l - 1, a, b);
		Node ret = v[b];
		return root = merge(merge(a, b), c), ret;
	}
	void reverse(int l, int r)
	{
		int a, b, c;
		split(root, r, b, c), split(b, l - 1, a, b), v[b].REV(), root = merge(merge(a, b), c);
	}
};
int main()
{
	int n, k, l, r;
	FhqTreap t;
	for (scanf("%d", &n); n--;)
		t.push_back(0);
	for (scanf("%d", &n); n--;)
	{
		scanf("%d%d%d", &k, &l, &r);
		if (k == 1)
			scanf("%d", &k), t.add(l, r, k);
		else if (k == 2)
			t.reverse(l, r);
		else
			printf("%d\n", t.ask(l, r).max);
	}
}