维护一个序列, 要求支持如下操作:

1. 在第pos个数后面加上tot个数.

2. 把第pos个数起的连续tot个数删除

3. 把第pos个数起的连续tot个数统一改为c

4. 把第pos个数起的连续tot个数翻转

5. 输出第pos个数起的连续tot个数的和

6. 输出区间最大子段和

每次把区间[A,B]中[A-1]节点splay到根，把[B+1]splay到根的右结点，[B+1]的左孩子里所有的元素便是区间[A,B]中所有的元素，可以直接在O(1)的时间内对其进行标记。（使用懒标记，splay时再进行下传）

然后要设置一个[0]和[n+1]的结点防止在首尾进行修改

坑了我半天的两点要注意的：

1、对于第6个操作，我们要记录每个结点的maxr,marl,max分别表示右起、左起、区间内最大和进行转移，注意这里的值不能为0，即如果全是负的也不能一个都不选。转移时要分三种情况，从左边开始取，左边+中间，左边+中间+右边。而且增加的[0]和[n+1]的结点所有值要为-INF，而且不能被更新，不然会挂。

2、删除节点的复杂度诚然是O(N)的，但是删除的时候要注意清除一定的信息，不然再回来搞的时候会挂。

得到两点启示：

1、不要用gets。。慢成翔，比cin还慢

2、用inline的过程好像快不了多少。。即便经常被调用。
 

/*
NOI 2005 sequence
*/

#include <cstdio>
#define MAXN 1000000
#define INF 0x7fffffff

using namespace std;

int next[MAXN];
int lc[MAXN],rc[MAXN],fa[MAXN],data[MAXN];
int rev[MAXN],same[MAXN];
int maxr[MAXN],maxl[MAXN],maxm[MAXN],sum[MAXN],size[MAXN];
int a[MAXN],q[MAXN];
int ROOT,temp,op,ed;

char ctrl[10],st[MAXN],*pch;

void update(int x);
void passdown(int x); 

inline int max(int a, int b)
{
	if (a>b) return a;
	else return b;
}

inline void getnum(int x)
{
	scanf("%d%d",&a[1],&a[2]);
	if (x == 2) scanf("%d",&a[3]);
	if (x == 1) for (int i = 3; i <= 2 + a[2]; i ++) scanf("%d",&a[i]); 
}

inline void swap(int& a, int& b)
{
 	temp = a; a = b; b = temp;
}

inline int left(int x)
{
	int p = fa[x];
	if (lc[p] == x) return 1;
	else return 0;
} 

inline void reverse(int x)
{
	swap(maxl[x],maxr[x]);	
	swap(lc[x],rc[x]);
	rev[x] = ! rev[x];
}

inline void makesame(int x, int val)
{
	data[x] = val;
	sum[x] = val * size[x];
	val = max(val * size[x],val);
	maxl[x] = maxr[x] = maxm[x] = val;
	same[x] = 1;
}

inline void passdown(int x)
{
	if (rev[x])
	{
		if (lc[x]) reverse(lc[x]);
		if (rc[x]) reverse(rc[x]);
		rev[x] = 0;
	}
	if (same[x])
	{
		if (lc[x]) makesame(lc[x],data[x]);
		if (rc[x]) makesame(rc[x],data[x]);
		same[x] = 0;
	} 
}

inline void update(int x)
{
	size[x] = 1;
	sum[x] = data[x];
	if (lc[x])
	{
		size[x] += size[lc[x]];
		sum[x] += sum[lc[x]];
	}
	if (rc[x])
	{
		size[x] += size[rc[x]];
		sum[x] += sum[rc[x]];
	}
	if (x > 2)
	{
		maxl[x] = max(maxl[lc[x]] , sum[lc[x]] + data[x] + max(0 , maxl[rc[x]]));
		maxr[x] = max(maxr[rc[x]] , sum[rc[x]] + data[x] + max(0 , maxr[lc[x]])); 
		maxm[x] = max(maxm[lc[x]] , maxm[rc[x]]);
		maxm[x] = max(maxm[x] , max(0 , maxr[lc[x]]) + data[x] + max(0 , maxl[rc[x]]));
	}
	else
	{
		maxl[x] = maxl[lc[x]];
		maxr[x] = maxr[rc[x]];
		maxm[x] = max(maxm[lc[x]] , maxm[rc[x]]);
	}
}

inline void zig(int x)
{
	int p = fa[x], s = rc[x];
	
	passdown(p);
	passdown(x);
	
	if (left(p)) lc[fa[p]] = x;
	else rc[fa[p]] = x;
	fa[x] = fa[p];
	
	fa[p] = x;
	rc[x] = p;
	
	fa[s] = p;
	lc[p] = s;
	
	update(p);
}

inline void zag(int x)
{
	int p = fa[x], s = lc[x];
	
	passdown(p);
	passdown(x);
	
	if (left(p)) lc[fa[p]] = x;
	else rc[fa[p]] = x;
	fa[x] = fa[p];
	
	fa[p] = x;
	lc[x] = p;
	
	fa[s] = p;
	rc[p] = s;
	
	update(p);
} 

inline void splay(int x, int root)
{
	int p;
	int aim = fa[root];
	passdown(x);
	while (fa[x] != aim)
	{
		p = fa[x];
		if (p == root)
		{
			if (left(x)) zig(x);
			else zag(x);
		}
		else
		{
			if (left(p) && left(x)) zig(p), zig(x);
			else
			if (!left(p) && !left(x)) zag(p), zag(x);
			else
			if (!left(p) && left(x)) zig(x), zag(x);
			else
			if (left(p) && !left(x)) zag(x), zig(x);
		}
	}
	update(x);
	if (!fa[x]) ROOT = x;	
}

inline void delnode(int x)
{
	lc[x] = rc[x] = rev[x] = same[x] = 0;
	next[x] = next[0];
	next[0] = x;
}

inline int newnode()
{
	int p = next[0];
	next[0] = next[p];
	return p;
}

inline void find(int k, int aim)
{
	int p = ROOT;
	for (int t;1;)
	{
		passdown(p);
		t = size[lc[p]];
		if (t+1 == k) break;
		if (t >= k) p = lc[p];
		else k -= t + 1, p = rc[p];
	}
	splay(p,aim);
}

inline int maketree(int l, int r, int x) 
{
	int mid = (l + r) >> 1;
	int p = newnode();
	data[p] = a[mid];
	fa[p] = x;
	if (mid < r) rc[p] = maketree(mid+1, r, p);
	if (l < mid) lc[p] = maketree(l, mid-1, p);
	update(p);
	return p;
} 

inline void del(int x)
{
	op=0,ed=1;
	q[1] = x;
	while (op < ed)
	{
		op++;
		if (lc[q[op]]) q[++ed] = lc[q[op]];
		if (rc[q[op]]) q[++ed] = rc[q[op]];
		delnode(q[op]);
	} 
}

inline void range(int x, int y)
{
	find(x-1, ROOT);
	find(y+1, rc[ROOT]);
}

inline void insert(int x, int tot)
{
	range(x+1,x);
	int p = maketree(3, 2+tot, rc[ROOT]);
	lc[rc[ROOT]] = p;
	update(rc[ROOT]);
	update(ROOT); 
}

inline void remove(int x, int tot)
{
	range(x,x + tot -1);
	del(lc[rc[ROOT]]);
	lc[rc[ROOT]] = 0;
	update(rc[ROOT]);
	update(ROOT); 
}

inline int getsum(int x, int tot)
{
	range(x,x+tot-1);
	int t = sum[lc[rc[ROOT]]];
	return t;
} 

inline void init()
{
	for (int i = 0; i < MAXN; i ++) next[i] = i + 1;
	int l = newnode();
	int r = newnode();
	ROOT = l;
	rc[l] = r;
	fa[r] = l;
	update(r);
	update(l);
	maxm[l] = maxm[r] = maxl[l] = maxr[l] = maxr[r] = maxl[r] = -INF;
	maxm[0] = maxm[0] = maxl[0] = maxr[0] = maxr[0] = maxl[0] = -INF;
}


int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);	
	int n,m;
	scanf("%d%d",&n, &m);
	init();
	for (int i = 3; i <= n + 2; i ++) scanf("%d",&a[i]);
	insert(1,n);
	for (int i = 1; i <= m; i ++)
	{
			scanf("%s\0",ctrl); 
			if (ctrl[0] == 'M' && ctrl[2] == 'X')
			{ 
				printf("%d\n",maxm[ROOT]);
			} 
			else 
			if (ctrl[0] == 'G')
			{
				getnum(0);
				printf("%d\n",getsum(a[1]+1,a[2]));	
			}	
			else
			if (ctrl[0] == 'I')
			{
				getnum(1);
				insert(a[1]+1,a[2]);
			}
			else
			if (ctrl[0] == 'D')
			{
				getnum(0);
				remove(a[1]+1,a[2]);
			}
			else
			if (ctrl[0] == 'M' && ctrl[2] == 'K')
			{
				getnum(2);
				range(a[1]+1,a[1]+a[2]);
				makesame(lc[rc[ROOT]],a[3]);
				update(rc[ROOT]);
				update(ROOT);  
			}
			else
			if (ctrl[0] == 'R')
			{
				getnum(0);
				range(a[1]+1,a[1]+a[2]);
				reverse(lc[rc[ROOT]]); 
				update(rc[ROOT]);
				update(ROOT); 
			}
	} 
	return 0;
}