记录编号	359461	评测结果	MMMMMMMMMM
题目名称	[NOI 2005]维护数列	最终得分	0
用户昵称	Rapiz	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-12-22 20:13:23	内存使用	0.00 MiB

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#define lch ch[o][0]
#define rch ch[o][1]
#define forch for(int d = 0; d < 2; d++) 
#define file(x) "seq2005." # x
typedef long long ll;
using std::swap;
using std::max;
namespace I {
	const int L = 1 << 15;
	char buf[L], *s, *t;
	inline char gc() {
		if (s == t) t = (s = buf) + fread(buf, 1, L, stdin);
		if (s == t) return EOF;
		return *s++;
	}
	inline void gs(char* d) {
		int ch = gc();
		while (!isgraph(ch)) ch = gc();
		while (isgraph(ch)) *d++ = ch, ch = gc();
	}
	inline int gi() {
		int r = 0, f = 1, ch = gc();
		while (!isdigit(ch)) f = ch == '-' ? -1 : f, ch = gc();
		while (isdigit(ch)) r = r*10 + ch - '0', ch = gc();
		return r*f;
	}
}using I::gi;
using I::gs;
const int N = 4000000 + 10;
const ll INF = 1 << 35;
int n, m, a[N], ch[N][2], fa[N], nsz, sz[N], rt, be[N], st[N];
ll s[N][3], mxs[N];
bool fp[N];
inline void up(int o) {
	sz[o] = 1;
	s[o][2] = mxs[o] = st[o];
	forch {
		mxs[o] += max(s[ch[o][d]][d^1], 0ll);
		sz[o] += sz[ch[o][d]];
		s[o][d] = max(s[ch[o][d]][2] + max(s[ch[o][d^1]][d], 0ll) + st[o], s[ch[o][d]][d]);
		s[o][2] += s[ch[o][d]][2];
	}
	forch mxs[o] = max(mxs[o], mxs[ch[o][d]]);
}
inline void mkbe(int o, int v) {
	if (!o) return;
	fp[o] = 0;
	st[o] = be[o] = v;
	s[o][0] = s[o][1] = mxs[o] = max(sz[o]*v, v);
	s[o][2] = sz[o]*v;
}
inline void mkfp(int o) {
	if (!o) return;
	fp[o] ^= 1;
	swap(lch, rch);
	swap(s[o][0], s[o][1]);
}
inline void down(int o) {
	if (fp[o]) {
		mkfp(lch), mkfp(rch);
		fp[o] = 0;
	}
	if (be[o] <= 1000) {
		mkbe(lch, be[o]), mkbe(rch, be[o]);
		be[o] = 1010;
	}
}
inline int gd(int o) {return ch[fa[o]][1] == o;}
inline void lk(int x, int y, int d) {
	if (x) fa[x] = y;
	if (y) ch[y][d] = x;
}
inline void rot(int o) {
	int x = fa[o], d = gd(o);
	lk(o, fa[x], gd(x));
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
	up(x);
	up(o);
	if (x == rt) rt = o;
}
inline int newnode(int v) {
	st[++nsz] = v;
	be[nsz] = 1010;
	up(nsz);
	return nsz;
}
int build(int l, int r) {
	int mid = l + r >> 1, o = newnode(a[mid]);
	if (l < mid) lk(build(l, mid - 1), o, 0);
	if (mid < r) lk(build(mid + 1, r), o, 1);
	up(o);
	return o;
}
inline int splay(int o, int t) {
	for(int x; (x = fa[o]) != t; rot(o)) if (fa[x] != t) rot(gd(o) == gd(x) ? x : o); 
	return o;
}
inline int kth(int o, int k) {
	while (k) {
		down(o);
		if (k == sz[lch] + 1) return o;
		else if (k <= sz[lch]) o = lch;
		else k -= sz[lch] + 1, o = rch;
	}
	return o;
}
inline int select(int l, int r) {
	if (l > r) return 0;
	splay(kth(rt, l), 0);
	splay(kth(rt, r + 2), rt);
	return ch[ch[rt][1]][0];
}
char cmd[100];
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	n = gi(), m = gi();
	s[0][0] = s[0][1] = mxs[0] = -(1ll << 32);
	a[0] = a[n + 1] = -1001;
	for (int i = 1; i <= n; i++) a[i] = gi();
	rt = build(0, n + 1);
	while (m--) {
		gs(cmd);
		if (cmd[0] == 'I') {
			int x = gi(), y = gi();
			for (int i = 1; i <= y; i++) a[i] = gi();
			splay(kth(rt, x + 1), 0);
			int t = ch[rt][1];
			t = splay(kth(t, 1), rt);
			lk(build(1, y), t, 0);
			up(t);
			up(rt);
			splay(nsz, 0);
		}
		else if (cmd[0] == 'M' && cmd[2] == 'X') printf("%lld\n", mxs[rt]);
		else {
			int x = gi(), y = gi(), t;
			y = x + y - 1;
			if (cmd[0] == 'D') {
				t = select(x, y);
				ch[fa[t]][gd(t)] = 0;
			}
			else if (cmd[0] == 'M') mkbe(t = select(x, y), gi());
			else if (cmd[0] == 'R') mkfp(t = select(x, y));
			else if (cmd[0] == 'G') printf("%lld\n", s[t = select(x, y)][2]);
			if (fa[t]) up(fa[t]);
			up(rt);
		}
	}
}