记录编号	427998	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]维护数列	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	1.962 s
提交时间	2017-07-24 10:53:09	内存使用	0.32 MiB

/**************************************
      Judge Result: Wrong Answer

**************************************/
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstring>
#include <iostream>
#include <algorithm>

#define lch chd[0]
#define rch chd[1]
#define kch chd[k]
#define xch chd[k^1]

const int INF=0x2FFFFFFF;

class SplayTree{
private:
	struct Node{
		int k;
		int sz;
		int sm;
		int lm;
		int rm;
		int ms;
		bool set;
		bool rev;
		Node* prt;
		Node* chd[2];
		Node(const int& key){
			this->k=key;
			this->sm=key;
			this->ms=key;
			this->lm=key>=0?key:0;
			this->rm=key>=0?key:0;
			this->sz=1;
			this->prt=NULL;
			this->lch=NULL;
			this->rch=NULL;
			this->rev=false;
			this->set=false;
		}
		~Node(){
			if(this->lch!=NULL)
				delete this->lch;
			if(this->rch!=NULL)
				delete this->rch;
		}
		inline void Maintain(){
			if(this!=NULL){
				this->sz=this->lch->size()+this->rch->size()+1;
				this->sm=this->lch->sum()+this->rch->sum()+this->k;
				this->lm=std::max(this->lch->lmax(),this->lch->sum()+this->k+this->rch->lmax());
				this->rm=std::max(this->rch->rmax(),this->rch->sum()+this->k+this->lch->rmax());
				this->ms=std::max(std::max(this->lch->maxSum(),this->rch->maxSum()),this->lch->rmax()+this->k+this->rch->lmax());
			}
		}
		inline void Swap(){
			if(this!=NULL){
				this->rev=!this->rev;
				std::swap(this->lm,this->rm);
				std::swap(this->lch,this->rch);
			}
		}
		inline void Set(const int& key){
			if(this!=NULL){
				this->set=true;
				this->k=key;
				this->sm=key*this->sz;
				this->lm=std::max(this->sm,0);
				this->rm=std::max(this->sm,0);
				this->ms=std::max(this->sm,this->k);
			}
		}
		inline void PushDown(){
			if(this->set){
				this->set=this->rev=false;
				this->lch->Set(this->k);
				this->rch->Set(this->k);
			}
			if(this->rev){
				this->rev=false;
				this->lch->Swap();
				this->rch->Swap();
			}
		}
		inline int sum(){
			return this==NULL?0:this->sm;
		}
		inline int maxSum(){
			return this==NULL?-INF:this->ms;
		}
		inline int key(){
			return this==NULL?0:this->k;
		}
		inline int lmax(){
			return this==NULL?0:this->lm;
		}
		inline int rmax(){
			return this==NULL?0:this->rm;
		}
		inline int size(){
			return this==NULL?0:this->sz;
		}
	}*root;
	inline void Rotate(Node* root,int k){
		Node* tmp=root->xch;
		root->PushDown();
		tmp->PushDown();
		tmp->prt=root->prt;
		if(root->prt==NULL)
			this->root=tmp;
		else if(root->prt->lch==root)
			root->prt->lch=tmp;
		else
			root->prt->rch=tmp;
		root->xch=tmp->kch;
		if(tmp->kch!=NULL)
			tmp->kch->prt=root;
		tmp->kch=root;
		root->prt=tmp;
		root->Maintain();
		tmp->Maintain();
	}
	void Splay(Node* root,Node* prt=NULL){
		// fprintf(stderr, "root=0x%X\n", root);
		// fprintf(stderr, "root->key=%d\n", root->key());
		while(root->prt!=prt){
			int k=root->prt->lch==root;
			if(root->prt->prt==prt){
				Rotate(root->prt,k);
			}
			else{
				int d=root->prt->prt->lch==root->prt;
				Rotate(k==d?root->prt->prt:root->prt,k);
				Rotate(root->prt,d);
			}
		}
		// this->Print();
	}
	Node* Build(const std::vector<int>& v,int l,int r){
		if(l>r)
			return NULL;
		int mid=(l+r)>>1;
		Node* tmp=new Node(v[mid]);
		tmp->lch=Build(v,l,mid-1);
		tmp->rch=Build(v,mid+1,r);
		if(tmp->lch!=NULL)
			tmp->lch->prt=tmp;
		if(tmp->rch!=NULL)
			tmp->rch->prt=tmp;
		tmp->Maintain();
		return tmp;
	}
	void PrintTree(Node* root,int deep){
		for(int i=0;i<deep;i++)
			fputc(' ',stdout);
		fprintf(stdout, "(root=0x%X,key=%d,sum=%d,size=%d,lmax=%d,rmax=%d,maxSum=%d)\n", root,root->key(),root->sum(),root->size(),root->lmax(),root->rmax(),root->maxSum());
		if(root==NULL)
			return;
		PrintTree(root->lch,deep+1);
		PrintTree(root->rch,deep+1);
	}
public:
	SplayTree(){
		this->root=new Node(-INF);
		this->root->rch=new Node(-INF);
		this->root->rch->prt=this->root;
	}
	SplayTree(const std::vector<int>& v){
		this->root=Build(v,0,v.size()-1);
	}
	~SplayTree(){
		delete this->root;
	}
	Node* Kth(int pos){
		++pos;
		Node* root=this->root;
		while(root!=NULL){
			// fprintf(stderr, "Kth:root=0x%X,pos=%d\n", root,pos);
			root->PushDown();
			int k=root->lch->size()+1;
			if(pos<k)
				root=root->lch;
			else if(pos==k)
				return root;
			else{
				pos-=k;
				root=root->rch;
			}
		}
		return NULL;
	}
	inline int Sum(const int& pos,const int& len){
		// fprintf(stderr, "pos=%d,len=%d\n", pos,len);
		this->Splay(this->Kth(pos-1));
		this->Splay(this->Kth(pos+len),this->root);
		return this->root->rch->lch->sum();
	}
	inline void Reverse(const int& pos,const int& len){
		this->Splay(this->Kth(pos-1));
		this->Splay(this->Kth(pos+len),this->root);
		this->root->rch->lch->Swap();
		this->root->rch->Maintain();
		this->root->Maintain();
	}
	inline void Set(const int& pos,const int& len,const int& d){
		this->Splay(this->Kth(pos-1));
		this->Splay(this->Kth(pos+len),this->root);
		this->root->rch->lch->Set(d);
		this->root->rch->Maintain();
		this->root->Maintain();
	}
	inline void Insert(const int& pos,SplayTree* data){
		this->Splay(this->Kth(pos));
		this->Splay(this->Kth(pos+1),this->root);
		Node* tmp=data->root;
		data->root=NULL;
		this->root->rch->lch=tmp;
		tmp->prt=this->root->rch;
		this->root->rch->Maintain();
		this->root->Maintain();
	}
	inline void Delete(const int& pos,const int& len){
		this->Splay(this->Kth(pos-1));
		this->Splay(this->Kth(pos+len),this->root);
		delete this->root->rch->lch;
		this->root->rch->lch=NULL;
		this->root->rch->Maintain();
		this->root->Maintain();
	}
	inline int MaxSum(){
		return this->root->maxSum();
	}
	void Print(){
		this->PrintTree(this->root,0);
	}
};

int FastRead();

int main(){
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout);
	SplayTree* tree=new SplayTree();
	std::vector<int> v;
	int n=FastRead();
	int m=FastRead();
	int a,b;
	char buf[20];
	for(int i=0;i<n;i++){
		v.push_back(FastRead());
	}
	tree->Insert(0,new SplayTree(v));
	// tree->Print();
	for(int i=0;i<m;i++){
		scanf("%s",buf);
		if(*buf!='M'||buf[2]!='X'){
			a=FastRead();
			b=FastRead();
		}
		if(*buf=='G'){
			printf("%d\n",tree->Sum(a,b));
		}
		else if(*buf=='D')
			tree->Delete(a,b);
		else if(*buf=='R')
			tree->Reverse(a,b);
		else if(*buf=='I'){
			v.clear();
			while(b--)
				v.push_back(FastRead());
			tree->Insert(a,new SplayTree(v));
		}
		else if(*buf=='M'){
			if(buf[2]=='K')
				tree->Set(a,b,FastRead());
			else
				printf("%d\n",tree->MaxSum());
		}
		// tree->Print();
	}
	return 0;
}

int FastRead(){
	int ans=0;
	bool neg=false;
	register char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')
			neg=true;
		ch=getchar();
	}
	while(isdigit(ch)){
		ans=ans*10+ch-'0';
		ch=getchar();
	}
	if(neg)
		ans=-ans;
	return ans;
}