WA #3，且每次 WA 的地方不一样，可能有时还能过题

讨论帖翻遍了，貌似没这么写的。。

我是每次 pushup 时判左右儿子是否存在然后大力分类讨论，并 lans, rans, ans 都时刻非空，于是写得比较长。。

覆盖我用了两个变量 cover 和 covnum 维护，所以覆盖的数是 $0$ 时应该没啥问题。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <random>
#include <ctime>

using namespace std;

inline int read () {
	int ret = 0, t = 1;
	char c = getchar();
	while ((c < '0' || c > '9') && c != '-') c = getchar();
	if (c == '-') t = -1, c = getchar();
	while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
	return ret * t;
}

mt19937 rnd(time(NULL));

const int MAXN = 500300;
struct tree {
	int ls, rs;
	int siz, rnd, val, sum;
	int lans, rans, ans;
	bool cover, rev; int covnum;
} t[MAXN];
int trash[MAXN]; int trashtop;
int top, root;

int newnode (int x) {
	int ret = (trashtop ? trash[trashtop--] : ++top);
	t[ret].ls = t[ret].rs = 0;
	t[ret].siz = 1, t[ret].rnd = rnd();
	t[ret].val = t[ret].sum = t[ret].lans = t[ret].rans = t[ret].ans = x;
	t[ret].cover = t[ret].rev = false; t[ret].covnum = 0;
	return ret;
}

void pushup (int x) {
	t[x].siz = t[t[x].ls].siz + t[t[x].rs].siz + 1;
	t[x].sum = t[t[x].ls].sum + t[t[x].rs].sum + t[x].val;
	if (!t[x].ls && !t[x].rs)
		t[x].lans = t[x].rans = t[x].ans = t[x].val;
	if (t[x].ls && !t[x].rs)
		t[x].lans = max(t[t[x].ls].lans, t[t[x].ls].sum + t[x].val),
		t[x].rans = max(t[x].val, t[x].val + t[t[x].ls].rans),
		t[x].ans = max(t[t[x].ls].ans, t[x].rans);
	if (!t[x].ls && t[x].rs)
		t[x].lans = max(t[x].val, t[x].val + t[t[x].rs].lans),
		t[x].rans = max(t[t[x].rs].rans, t[t[x].rs].sum + t[x].val),
		t[x].ans = max(t[t[x].rs].ans, t[x].lans);
	if (t[x].ls && t[x].rs)
		t[x].lans = max(t[t[x].ls].lans, max(t[t[x].ls].sum + t[x].val, t[t[x].ls].sum + t[x].val + t[t[x].rs].lans)),
		t[x].rans = max(t[t[x].rs].rans, max(t[t[x].rs].sum + t[x].val, t[t[x].rs].sum + t[x].val + t[t[x].ls].rans)),
		t[x].ans = max(max(t[t[x].ls].ans, t[t[x].rs].ans), max(t[t[x].ls].rans + t[x].val, t[t[x].rs].lans + t[x].val)),
		t[x].ans = max(t[x].ans, t[t[x].ls].rans + t[t[x].rs].lans + t[x].val);
}
void cover (int x, int c) {
	t[x].val = c, t[x].sum = t[x].siz * t[x].val;
	t[x].lans = t[x].rans = t[x].ans = max(t[x].val, t[x].sum);
	t[x].cover = true, t[x].covnum = c;
}
void rev (int x) {
	swap(t[x].ls, t[x].rs); swap(t[x].lans, t[x].rans);
	t[x].rev ^= 1; 
}
void pushdown (int x) {
	if (t[x].cover) {
		cover(t[x].ls, t[x].covnum); cover(t[x].rs, t[x].covnum);
		t[x].cover = false; t[x].covnum = 0;
	}
	if (t[x].rev) {
		rev(t[x].ls); rev(t[x].rs);
		t[x].rev = false;
	}
}
void split (int now, int k, int &x, int &y) {
	if (!now) { x = y = 0; return; }
	pushdown(now);
	if (t[t[now].ls].siz + 1 <= k) x = now, split(t[now].rs, k - t[t[now].ls].siz - 1, t[now].rs, y);
	else y = now, split(t[now].ls, k, x, t[now].ls);
	pushup(now);
}
int merge (int x, int y) {
	if (!x || !y) return x + y;
	if (t[x].rnd < t[y].rnd) { pushdown(x); t[x].rs = merge(t[x].rs, y); pushup(x); return x; }
	else { pushdown(y); t[y].ls = merge(x, t[y].ls); pushup(y); return y; }
}

void _insert (int pos, int tot) {
	int r1, r2, r3 = 0;
	while (tot--) r3 = merge(r3, newnode(read()));
	split(root, pos, r1, r2);
	root = merge(merge(r1, r3), r2);
}

void savetrash (int x) {
	if (!x) return;
	trash[++trashtop] = x;
	savetrash(t[x].ls), savetrash(t[x].rs);
}

void _delete (int pos, int tot) {
	int r1, r2, r3;
	split(root, pos - 1, r1, r2);
	split(r2, tot, r2, r3);
	root = merge(r1, r3); savetrash(r2);
}

void _make_same (int pos, int tot, int c) {
	int r1, r2, r3;
	split(root, pos - 1, r1, r2);
	split(r2, tot, r2, r3);
	cover(r2, c);
	root = merge(merge(r1, r2), r3);
}

void _reverse (int pos, int tot) {
	int r1, r2, r3;
	split(root, pos - 1, r1, r2);
	split(r2, tot, r2, r3);
	rev(r2);
	root = merge(merge(r1, r2), r3);
}

void _get_sum (int pos, int tot) {
	int r1, r2, r3;
	split(root, pos - 1, r1, r2);
	split(r2, tot, r2, r3);
	printf("%d\n", t[r2].sum);
	root = merge(merge(r1, r2), r3);
}

char tmp[10];

int main () {
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	int n = read(), q = read();
	_insert(0, n);
	while (q--) {
		scanf("%s", tmp);
		if (tmp[0] == 'I') {
			int pos = read(), tot = read();
			_insert(pos, tot);
		}
		else if (tmp[0] == 'D') {
			int pos = read(), tot = read();
			_delete(pos, tot);
		}
		else if (tmp[0] == 'R') {
			int pos = read(), tot = read();
			_reverse(pos, tot);
		}
		else if (tmp[0] == 'G') {
			int pos = read(), tot = read();
			_get_sum(pos, tot);
		}
		else if (tmp[2] == 'K') {
			int pos = read(), tot = read(), c = read();
			_make_same(pos, tot, c);
		}
		else printf("%d\n", t[root].ans);
	}
	return 0;
}