记录编号	143860	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]维护数列	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	3.170 s
提交时间	2014-12-18 12:11:38	内存使用	34.64 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#define CL(x) memset(x,0,sizeof(x))
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define dow(i,s,t) for(int i=(s);i>=(t);i--)
using namespace std;
typedef long long LL;
LL read(){
    LL ret=0,f=1;
    char x=getchar();
    while(!(x>='0' && x<='9')){if(x=='-')f=-1;x=getchar();}
    while(x>='0' && x<='9') ret=ret*10+x-'0', x=getchar();
    return ret*f;
}
char get_char(){
	char x=getchar();
	while(!((x>='a' && x<='z')||(x>='A' && x<='Z'))) x=getchar();
	return x;
}

const int MAXN=5e5+10;
const LL INF=1e16;
const LL ZERO=0;


struct node{
	int ls,rs,fa;
	//子树和 子树大小 点权 该点及其子树到达最右点的最大和 ...左... 此点及其子树的最大和 
	LL sum,sz,val,mx_l,mx_r,mx;
	int lz;
	bool revc,have_lz;
	node(){
		ls=rs=fa=sum=sz=val=mx_l=mx_r=mx=lz=0;
		mx=-INF;
		revc=have_lz=false;
	}
}t[MAXN];
int root=0;
int node_cnt;
int node_queue[MAXN],qn;

int new_node(){
	if(qn) return node_queue[--qn];
	return ++node_cnt;
}
void del_node(int & n){
	t[n]=node();
	node_queue[qn++]=n;
	n=0;
}

void push_up(int n){
	if(!n) return;
	int ls=t[n].ls, rs=t[n].rs;
	t[n].sz=t[ls].sz+t[rs].sz+1;
	t[n].sum=t[ls].sum+t[rs].sum+t[n].val;
	t[n].mx_l=max(max(ZERO,t[ls].mx_l)+t[n].val+t[rs].sum, t[rs].mx_l);
	t[n].mx_r=max(max(ZERO,t[rs].mx_r)+t[n].val+t[ls].sum, t[ls].mx_r);
	t[n].mx=max(t[ls].mx,t[rs].mx);
	t[n].mx=max(t[n].mx,max(t[ls].mx_l,ZERO)+t[n].val+max(t[rs].mx_r,ZERO));
}
void node_same(int n,int val){
	if(!n) return;
	t[n].val=val;
	t[n].sum=t[n].sz*val;
	if(val>=0) t[n].mx_l=t[n].mx_r=t[n].mx=t[n].sum;
	else       t[n].mx_l=t[n].mx_r=t[n].mx=val;
	t[n].lz=val;
	t[n].have_lz=true;
}
void node_revc(int n){
	if(!n) return;
	swap(t[n].ls,t[n].rs);
	swap(t[n].mx_l,t[n].mx_r);
	t[n].revc^=true;
}
void push_down(int n){
	if(!n) return ;
	int ls=t[n].ls, rs=t[n].rs;
	if(t[n].have_lz){
		node_same(t[n].ls,t[n].lz);
		node_same(t[n].rs,t[n].lz);
		t[n].lz=0;
		t[n].have_lz=false;
	}
	if(t[n].revc){
		node_revc(t[n].ls);
		node_revc(t[n].rs);
		t[n].revc=false;
	}
}

void zig(int x){
	int y=t[x].fa, z=t[y].fa;
	if(t[z].ls==y) t[z].ls=x;
	if(t[z].rs==y) t[z].rs=x;
	t[x].fa=z;
	t[y].ls=t[x].rs, t[t[x].rs].fa=y;
	t[x].rs=y, t[y].fa=x;
	push_up(y);
}
void zag(int x){
	int y=t[x].fa, z=t[y].fa;
	if(t[z].ls==y) t[z].ls=x;
	if(t[z].rs==y) t[z].rs=x;
	t[x].fa=z;
	t[y].rs=t[x].ls, t[t[x].ls].fa=y;
	t[x].ls=y, t[y].fa=x;
	push_up(y);
}
void splay(int n,int g=0){
	int x=n;
	push_down(x);
	while(t[x].fa!=g){
		int y=t[x].fa, z=t[y].fa;
		push_down(z), push_down(y), push_down(x);
		if(z==g){
			if(t[y].ls==x) zig(x);
			else zag(x);
			break;
		}else if(t[z].ls==y){
			if(t[y].ls==x) zig(y),zig(x);
			else zag(x),zig(x);
		}else{
			if(t[y].rs==x) zag(y),zag(x);
			else zig(x),zag(x);
		}
	}
	push_up(x);
	if(t[x].fa==0) root=x;
}
void dfs_print(int n){
	push_down(n);
	if(t[n].ls) dfs_print(t[n].ls);
	printf("%d ",t[n].val);
	if(t[n].rs) dfs_print(t[n].rs);
}
int find(int n,int sz){
	push_down(n);
	int ls=t[n].ls, rs=t[n].rs;
	if(sz<=t[ls].sz) return find(ls,sz);
	sz-=t[ls].sz;
	if(sz==1) return n;
	else return find(rs,sz-1);
}
int ins(int & n,int fa,LL val){
	push_down(n);
	if(!n){
		n=new_node();
		t[n].fa=fa;
		t[n].sz=1;
		t[n].val=t[n].sum=t[n].mx_l=t[n].mx_r=t[n].mx=val;
		return n;
	}
	int tn=ins(t[n].ls,n,val);
	push_up(n);
	return tn;
}
int build(int l,int r,vector<int> & ps){
	if(l>r) return 0;
	int mid=(l+r)/2;
	int n=new_node();
	t[n].val=t[n].sum=t[n].mx_l=t[n].mx_r=t[n].mx=ps[mid];
	t[n].sz=1;
	if(l==r) return n;
	t[n].ls=build(l,mid-1,ps); t[t[n].ls].fa=n;
	t[n].rs=build(mid+1,r,ps); t[t[n].rs].fa=n;
	push_up(n);
	return n;
}
void ins_node(int & n,int fa,int tn){
	push_down(n);
	if(!n){
		n=tn;
		t[n].fa=fa;
		return;
	}
	ins_node(t[n].ls,n,tn);
	push_up(n);
}
void insert(int p,vector<int> & ps){
	int n=find(root,p+1);
	int tn=build(0,(int)ps.size()-1,ps);
	splay(n);
	push_down(t[n].rs);
	ins_node(t[n].rs,n,tn);
	push_up(t[n].rs);
	push_up(root);
	//dfs_print(root);
	//printf("\n");
}
void del(int & n){
	if(!n) return;
	if(t[n].ls) del(t[n].ls);
	if(t[n].rs) del(t[n].rs);
	del_node(n);
}
void remove(int p,int tot){
	int sn=find(root,p);
	int en=find(root,p+tot+1);
	splay(sn);
	splay(en,sn);
	del(t[en].ls);
	push_up(en);
	push_up(sn);
}
void make_same(int p,int tot,int val){
	int sn=find(root,p);
	int en=find(root,p+tot+1);
	splay(sn);
	splay(en,sn);
	node_same(t[en].ls,val);
	push_down(t[en].ls);
	push_up(en);
	push_up(sn);
}
void reverse(int p,int tot){
	int sn=find(root,p);
	int en=find(root,p+tot+1);
	splay(sn);
	splay(en,sn);
	node_revc(t[en].ls);
	push_down(t[en].ls);
	push_up(en);
	push_up(sn);
}
LL get_sum(int p,int tot){
	int sn=find(root,p);
	int en=find(root,p+tot+1);
	splay(sn);
	splay(en,sn);
	return t[t[en].ls].sum;
}

int N,M;

void init(){
	ins(root,0,-INF);
	ins(root,0,-INF);
	N=read(), M=read();
	vector<int> val;
	rep(i,1,N) val.push_back(read());
	insert(0,val);
}
bool equal(char s1[],const char s2[]){
	rep(i,0,2) if(s1[i]!=s2[i]) return false;
	return true;
}

void work(){
	rep(i,1,M){
		char str[20]={0};
		scanf("%s",&str);
		if(equal(str,"INS")){
			int p=read(), tot=read();
			vector<int> val;
			rep(j,1,tot) val.push_back(read());
			insert(p,val);
		}else if(equal(str,"DEL")){
			int p=read(), tot=read();
			remove(p,tot); 
		}else if(equal(str,"MAK")){
			int p=read(), tot=read(), val=read();
			make_same(p,tot,val);
		}else if(equal(str,"REV")){
			int p=read(), tot=read();
			reverse(p,tot);
		}else if(equal(str,"GET")){
			int p=read(), tot=read();
			LL sum=get_sum(p,tot);
			printf("%lld\n",sum);
		}else{
			splay(root);
			LL mx=t[root].mx;
			printf("%lld\n",mx);
		}
		//dfs_print(root);
		//printf("\n");
	}
}

int main(){
	//freopen("in.txt","r",stdin);
	//freopen("1.out","w",stdout); 
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout); 
	init();
	work();
	return 0;
}