提交记录

#include <cstdio>
using namespace std;
const int N = 500005;
const int NO_COVER = 1001;
int fa[N], ch[N][2], size[N];
int v[N];
int lmax[N], rmax[N], tmax[N], sum[N];
int cover[N], rev[N];
int root;
int free_node[N], top;
int new_node() {
	return free_node[top--];
}
void delete_node(int node) {
	fa[node] = ch[node][0] = ch[node][1] = rev[node] = 0;
	lmax[node] = rmax[node] = tmax[node] = sum[node] = 0;
	size[node] = v[node] = 0;
	cover[node] = NO_COVER;
	free_node[++top] = node;
}
void delete_tree(int p) {
	if (p == 0) {
		return;
	}
	delete_node(p);
	delete_tree(ch[p][0]);
	delete_tree(ch[p][1]);
}
int max(int a, int b) {
	return a > b ? a : b;
}
void push_up(int p) {
	size[p] = size[ch[p][0]] + size[ch[p][1]] + 1;
	lmax[p] = max(lmax[ch[p][0]], sum[ch[p][0]] + v[p] + lmax[ch[p][1]]);
	rmax[p] = max(rmax[ch[p][1]], sum[ch[p][1]] + v[p] + rmax[ch[p][0]]);
	tmax[p] = max(max(tmax[ch[p][0]], tmax[ch[p][1]]), rmax[ch[p][0]] + v[p] + lmax[ch[p][1]]);
	sum[p] = sum[ch[p][0]] + v[p] + sum[ch[p][1]];
}
void push_cover_tag(int p, int tag) {
	if (p == 0) {
		return;
	}
	v[p] = tag;
	cover[p] = tag;
	if (tag >= 0) {
		lmax[p] = rmax[p] = tmax[p] = sum[p] = size[p] * tag;
	} else {
		lmax[p] = rmax[p] = 0;
		tmax[p] = tag;
		sum[p] = size[p] * tag;
	}
}
void swap(int & a, int & b) {
	a ^= b ^= a ^= b;
}
void push_rev_tag(int p) {
	rev[p] ^= 1;
	swap(ch[p][0], ch[p][1]);
	swap(lmax[p], rmax[p]);
}
void push_down(int p) {
	if (cover[p] != NO_COVER) {
		push_cover_tag(ch[p][0], cover[p]);
		push_cover_tag(ch[p][1], cover[p]);
		cover[p] = NO_COVER;
		rev[p] = 0;
	} else if (rev[p] == 1) {
		push_rev_tag(ch[p][0]);
		push_rev_tag(ch[p][1]);
		rev[p] = 0;
	}
}
void rotate(int x) {
	int y = fa[x], z = fa[y];
	int k = ch[y][0] == x ? 0 : 1;
	fa[x] = z;
	if (z != 0) {
		if (ch[z][0] == y) {
			ch[z][0] = x;
		} else {
			ch[z][1] = x;
		}
	}
	ch[y][k] = ch[x][1 - k];
	if (ch[y][k] != 0) {
		fa[ch[y][k]] = y;
	}
	fa[y] = x;
	ch[x][1 - k] = y;
	push_up(y);
	push_up(x);
}
void splay(int x, int goal_father) {
	int y, z;
	while (fa[x] != goal_father) {
		y = fa[x], z = fa[y];
		if (z == goal_father) {
			rotate(x);
		} else {
			if ((ch[y][0] == x) == (ch[z][0] == y)) {
				rotate(y);
			} else {
				rotate(x);
			}
			rotate(x);
		}
	}
	if (goal_father == 0) {
		root = x;
	}
}
int find_kth(int p, int k) {
	push_down(p);
	if (k < size[ch[p][0]]) {
		return find_kth(ch[p][0], k);
	} else if (k == size[ch[p][0]]) {
		return p;
	} else {
		return find_kth(ch[p][1], k - size[ch[p][0]] - 1);
	}
}
void split(int posi, int tot) {
	splay(find_kth(root, posi - 1), 0);
	splay(find_kth(root, posi + tot), root);
}
int a[N];
int build(int l, int r) {
	int p = new_node();
	if (l == r) {
		size[p] = 1;
		v[p] = tmax[p] = sum[p] = a[l];
		lmax[p] = rmax[p] = max(a[l], 0);
	} else {
		int mid = (l + r) / 2;
		v[p] = a[mid];
		if (l <= mid - 1) {
			ch[p][0] = build(l, mid - 1);
			fa[ch[p][0]] = p;
		}
		if (mid + 1 <= r) {
			ch[p][1] = build(mid + 1, r);
			fa[ch[p][1]] = p;
		}
		push_up(p);
	}
	return p;
}
bool used[N];
void print() {
	for (int i = 1; i < N; i++) {
		used[i] = true;
	}
	for (int i = 1; i <= top; i++) {
		used[free_node[i]] = false;
	}
	printf("root = %d\n", root);
	for (int i = 1; i < N; i++) {
		if (used[i]) {
			printf("Node #%d:\n", i);
			printf("v = %d, ", v[i]);
			printf("fa = %d, lc = %d, rc = %d, size = %d\n", fa[i], ch[i][0], ch[i][1], size[i]);
			printf("lmax = %d, rmax = %d, tmax = %d, sum = %d\n", lmax[i], rmax[i], tmax[i], sum[i]);
//			printf("cover = %d, rev = %d\n", cover[i], rev[i]);
		}
	}
	printf("----------------------------\n");
}
void print_seq(int p) {
	if (p == 0) {
		return;
	}
	push_down(p);
	print_seq(ch[p][0]);
	printf("%d ", v[p]);
	print_seq(ch[p][1]);
}
int main() {
//	freopen("in.txt", "r", stdin);
	for (int i = N - 1; i >= 1; i--) {
		delete_node(i);
	}
	tmax[0] = -0x7fffffff - 1;
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	a[0] = a[n + 1] = -1001;
	root = build(0, n + 1);
//	print_seq(root);
//	putchar(10);
//	print();
	char op[10];
	for (int i = 1, posi, tot, c, temp_root; i <= m; i++) {
		scanf("%s", op);
		if (op[0] == 'M' && op[2] == 'X') {
			printf("%d\n", tmax[root]);
		} else {
			scanf("%d %d", &posi, &tot);
			if (op[0] == 'I') {
				for (int i = 1; i <= tot; i++) {
					scanf("%d", a + i);
				}
				split(posi + 1, 0);
				temp_root = build(1, tot);
				ch[ch[root][1]][0] = temp_root;
				fa[temp_root] = ch[root][1];
			} else {
				split(posi, tot);
				if (op[0] == 'D') {
					delete_tree(ch[ch[root][1]][0]);
					ch[ch[root][1]][0] = 0;
				} else if (op[0] == 'M') {
					scanf("%d", &c);
					push_cover_tag(ch[ch[root][1]][0], c);
				} else if (op[0] == 'R') {
					push_rev_tag(ch[ch[root][1]][0]);
				} else if (op[0] == 'G') {
					printf("%d\n", sum[ch[ch[root][1]][0]]);
				}
			}
			push_up(ch[root][1]);
			push_up(root);
		}
//		print_seq(root);
//		putchar(10);
//		print();
	}
	return 0;
}