第一个点AC其它全部MLE

#include <bits/stdc++.h>

using namespace std;

const int N = 4000000 + 5;

struct node {
	int l, r, val, mx, lmx, rmx, sz, pty, sum;
	bool tag, __tag;
} tree[N];

int root, num;

int a[N], b[N]; 

void pushup(int x) {
	tree[x].sz = tree[tree[x].l].sz + tree[tree[x].r].sz + 1;
	tree[x].sum = tree[tree[x].l].sum + tree[tree[x].r].sum + tree[x].val;
	tree[x].mx = max({tree[tree[x].l].mx, tree[tree[x].r].mx, tree[tree[x].l].rmx + tree[x].val + tree[tree[x].r].lmx});
	tree[x].lmx = max(tree[tree[x].l].lmx, tree[tree[x].l].sum + tree[x].val + tree[tree[x].r].lmx);
	tree[x].rmx = max(tree[tree[x].r].rmx, tree[tree[x].r].sum + tree[x].val + tree[tree[x].l].rmx);
}

void __pushdown(int key) {
	if (key) {
		tree[key].__tag ^= 1;
		swap(tree[key].l, tree[key].r);
		swap(tree[key].lmx, tree[key].rmx);
	}
}

void _pushdown(int key, int val) {
	if (key) {
		tree[key].tag = 1;
		tree[key].val = val;
		tree[key].sum = tree[key].sz * val;
		if (val > 0) {
			tree[key].mx = tree[key].lmx = tree[key].rmx = tree[key].sum;
		} else {
			tree[key].mx = val, tree[key].lmx = tree[key].rmx = 0;
		}
	}
}

void pushdown(int key) {
	if (key) {
		if (tree[key].tag) {
			tree[key].tag =  0;
			_pushdown(tree[key].l, tree[key].val);
			_pushdown(tree[key].r, tree[key].val);
		}
		if (tree[key].__tag) {
			tree[key].__tag = 0;
			__pushdown(tree[key].l);
			__pushdown(tree[key].r);
		}
	}
}

int add(int val) {
	int tot = b[num--];
	tree[tot].val = val;
	tree[tot].lmx = max(val, 0);
	tree[tot].rmx = max(val, 0);
	tree[tot].mx = val;
	tree[tot].sum = val;
	tree[tot].sz = 1;
	tree[tot].pty = rand();
	tree[tot].tag = tree[tot].__tag = 0;
	return tot;
}

void del(int key) {
	if (!key) {
		return;
	}
	del(tree[key].l);
	b[++num] = key;
	del(tree[key].r);
}

void split(int u, int & l, int & r, int k) {
	if (!u) {
		l = r = 0;
		return;
	}
	pushdown(u);
	int ln = tree[tree[u].l].sz;
	if (ln < k) {
		l = u;
		split(tree[u].r, tree[u].r, r, k - ln - 1);
	} else {
		r = u;
		split(tree[u].l, l, tree[u].l, k);
	}
	pushup(u);
}

int merge(int l, int r) {
	if (!l || !r) {
		return l + r;
	}
	if (tree[l].pty <= tree[r].pty) {
		pushdown(l);
		tree[l].r = merge(tree[l].r, r);
		pushup(l);
		return l;
	} else {
		pushdown(r);
		tree[r].l = merge(l, tree[r].l);
		pushup(r);
		return r;
	}
}

int make(int l, int r) {
	int mid = l + r >> 1;
	int key = add(a[mid]);
	if (l < mid) {
		tree[key].l = make(l, mid - 1);
	}
	if (r > mid) {
		tree[key].r = make(mid + 1, r);
	}
	pushup(key);	
	return key;
}

int main(void) {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	tree[0].mx = -1e9;
	for (int i = 3e6; i >= 1; i--) {
		b[++num] = i;
	}
	root = make(1, n);
	while (m--) {
		string opt;
		int p1, p2, p3;
		cin >> opt;
		if (opt == "INSERT") {
			int x, tot;
			cin >> x >> tot;
			for (int i = 1; i <= tot; i++) {
				cin >> a[i];
			}
			split(root, p1, p2, x);
			root = merge(merge(p1, make(1, tot)), p2);
		} else if (opt == "DELETE") {
			int x, tot;
			cin >> x >> tot;
			split(root, p1, p2, x - 1);
			split(p2, p2, p3, tot);
			root = merge(p1, p3);
			del(p2);
		} else if (opt == "MAKE-SAME") {
			int x, tot, c;
			cin >> x >> tot >> c;
			split(root, p1, p2, x - 1);
			split(p2, p2, p3, tot);
			_pushdown(p2, c);
			root =  merge(merge(p1, p2), p3);
		} else if (opt == "REVERSE") {
			int x, tot;
			cin >> x >> tot;
			split(root, p1, p2, x - 1);
			split(p2, p2, p3, tot);
			__pushdown(p2);
			root = merge(merge(p1, p2), p3);
		} else if (opt == "GET-SUM") {
			int x, tot;
			cin >> x >> tot;
			split(root, p1, p2, x - 1);
			split(p2, p2, p3, tot);
			cout << tree[p2].sum << endl;
			root = merge(merge(p1, p2), p3);
		} else {
			cout << tree[root].mx << endl;
		}
	}
	return 0;
}