中国珂学院

题目链接 珂朵莉树是一个可以维护区间 x 次方和查询的高效数据结构，原理十分暴力。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct ChthollyTree : map<int, ll>
{
	iterator split(int pos)
	{
		iterator it = lower_bound(pos);
		if (it->first == pos)
			return it;
		iterator jt = it--;
		return insert(jt, make_pair(pos, it->second));
	}
} t;
int n, m;
int main()
{
	scanf("%d%d", &n, &m);
	t[1] = 1;
	t[n + 1] = 0;
	for (int op, l, r, x, y; m--;)
	{
		scanf("%d%d%d", &op, &l, &r);
		ChthollyTree::iterator b = t.split(l), e = t.split(r + 1), it;
		if (op == 0)
			t.erase(b, e), t[l] = 0;
		else if (op == 1)
		{
			int res = 0;
			it = b;
			do
			{
				int pos = it->first, val = it->second;
				++it;
				if (val)
					res += it->first - pos;
			} while (it != e);
			t.erase(b, e), t[l] = 0;
			scanf("%d%d", &x, &y);
			if (res)
			{
				b = t.split(x), e = t.split(y + 1);
				if (res >= y - x + 1)
					t.erase(b, e), t[x] = 1;
				else
				{
					it = b;
					do
					{
						int pos = it->first, val = it->second;
						++it;
						if (!val)
						{
							t[pos] = 1;
							if (res >= it->first - pos)
								res -= it->first - pos;
							else
								res = t[pos + res] = 0;
						}
					} while (res && it != e);
				}
			}
		}
		else
		{
			int res = 0, now = 0;
			it = b;
			do
			{
				int pos = it->first, val = it->second;
				++it;
				if (!val)
					res += it->first - pos;
				else
					now = max(now, res), res = 0;
			} while (it != e);
			printf("%d\n", max(res, now));
		}
	}
}