这题 可以splay 也可以块状链表

我打了一个块状链表时间复杂度是$n\sqrt{n}$ 具体的使用方法详见论文 信息学中的分块思想.pdf

这里要注意的是 split前要标记下传一下 s[0]是无意义的 要从s[0].nxt开始弄

还有这题很坑的是 修改的时候可能把一个区间修改成0 和 最大子段和至少要有一个数 也就是全负数的时候不能输出0而要输出最大那个负数

没加读入优化在我E3 cpu的电脑上跑了25s 加了读入优化变成了2.95s ……

反倒是输出优化没什么效果 加了变成 2.93s……

接下来是代码  处理操作那里写的比较丑……

#include <cstdio>
#include <algorithm>
#include <cassert>
using std::swap;
using std::min;
const int N=500,birth=19990616,INF=2099999999;
typedef long long LL;
struct node{
	int a[N+10];
	int sum,lm,rm,tag,rev,nxt,pre,sz,maxsum,mx;
}s[1000*2+10];
int trash[20000],inbin,nnode,tmp[500000],n,m,cnt;
LL max(LL a,LL b){return a>b?a:b;}
int newnode(){
	int ret=0;
	if(inbin) ret=trash[inbin--];else ret=++nnode;
	for(int i=0;i<=N;i++) s[ret].a[i]=0;
	s[ret].sum=s[ret].lm=s[ret].rm=s[ret].rev=s[ret].pre=s[ret].nxt=s[ret].sz=0;s[ret].mx=-INF;
	s[ret].tag=birth;
	return ret; 
}
int find(int &pos){int i;for(i=s[0].nxt;s[i].nxt && pos>s[i].sz;pos-=s[i].sz,i=s[i].nxt);return i;}
void up(int x){
	int tmax=0,tmin=0,maxsum=0,ms=0;
	s[x].sum=0,s[x].mx=-INF;
	for(int i=1;i<=s[x].sz;i++) {
		maxsum+=s[x].a[i];
		s[x].mx=max(s[x].mx,s[x].a[i]);
		if(maxsum > ms) ms=maxsum;
		if(maxsum<0) maxsum=0;
		s[x].sum+=s[x].a[i],tmax=max(tmax,s[x].sum),tmin=min(tmin,s[x].sum);
	}
	s[x].lm=tmax;s[x].rm=s[x].sum-tmin;s[x].maxsum=ms;
}
void down(int x){
	int i,j;
	if(s[x].rev) for(i=1,j=s[x].sz;i<j;i++,j--) swap(s[x].a[i],s[x].a[j]);s[x].rev=0;
	if(s[x].tag!=birth) for(i=1;i<=s[x].sz;i++) s[x].a[i]=s[x].tag;s[x].tag=birth;
	up(x);
}
void merge(int x){
	int t=s[x].nxt;
	if(!t) return;
	down(x);down(t);
	for(int i=1;i<=s[t].sz;i++) s[x].a[++s[x].sz]=s[t].a[i];
	if(s[t].nxt) s[s[t].nxt].pre=x;s[x].nxt=s[t].nxt;
	trash[++inbin]=t;
	up(x);
}
void maintain(){
	for(int i=s[0].nxt;i&&s[i].nxt;i=s[i].nxt){
		while(s[i].sz+s[s[i].nxt].sz<=N && s[i].nxt) 
			merge(i);
	}
}
void split(int x,int loc){//x 的第loc后分裂
	int t=newnode(),i,j;
	down(x);
	s[t].pre=x;s[t].nxt=s[x].nxt;s[x].nxt=t;
	if(s[t].nxt) s[s[t].nxt].pre=t;
	for(i=loc+1,j=1;i<=s[x].sz;i++,j++) s[t].a[j]=s[x].a[i],s[t].sz++;
	s[x].sz=loc;
	up(x);up(t);
}
void insert(int pos,int tot){
	int x=find(pos);
	split(x,pos);
	for(int i=1;i<=tot;i++){
		if(s[x].sz==N){
			int t=newnode();up(x);
			s[t].pre=x;s[t].nxt=s[x].nxt;s[x].nxt=t;x=t;
		}
		s[x].a[++s[x].sz]=tmp[i];
	}
	up(x);
	if(s[x].nxt) s[s[x].nxt].pre=x;
	maintain();
}
void remove(int pos,int tot){
	int t1=pos-1,t2=pos+tot-1;
	int x1=find(t1),x2=find(t2);
	if(x1==x2) {down(x1);s[x1].sz-=tot;for(int i=t1+1;i<=s[x1].sz;i++) s[x1].a[i]=s[x1].a[i+tot];up(x1);}
	else {
		split(x1,t1);
		split(x2,t2);
		for(int i=s[x1].nxt;i!=s[x2].nxt;i=s[i].nxt) trash[++inbin]=i;
		s[x1].nxt=s[x2].nxt;s[s[x2].nxt].pre=x1;
	}
	maintain();
}
void change(int pos,int tot,int c){
	int t1=pos,t2=pos+tot-1;
	int x1=find(t1),x2=find(t2);
	if(x1==x2){down(x1);for(int i=t1;i<=t2;i++) s[x1].a[i]=c;up(x1);}
	else{
		down(x1),down(x2);
		for(int i=t1;i<=s[x1].sz;i++) s[x1].a[i]=c;up(x1);
		for(int i=1;i<=t2;i++) s[x2].a[i]=c;up(x2);
		for(int i=s[x1].nxt;i!=x2;i=s[i].nxt)
			 s[i].tag=c,s[i].sum=c*s[i].sz,s[i].lm=c>0?s[i].sum:0,s[i].rm=c>0?s[i].sum:0,s[i].maxsum=c>0?s[i].sum:0;
	}
}
void flip(int pos,int tot){
	int t1=pos-1,t2=pos+tot-1,i,j;
	int x1=find(t1),x2=find(t2);
	if(x1==x2){
		down(x1);
		for(i=t1+1,j=t2;i<j;i++,j--) swap(s[x1].a[i],s[x1].a[j]);
		up(x1);
	}
	else{
		split(x1,t1),split(x2,t2);
		int tt=s[x1].nxt,ttt=s[x2].nxt;
		for(int i=x2;i!=x1;i=s[i].nxt)
			swap(s[i].lm,s[i].rm),swap(s[i].nxt,s[i].pre),s[i].rev^=1;
		s[x1].nxt=x2;s[x2].pre=x1;s[tt].nxt=ttt;s[ttt].pre=tt;
		//up(x1),up(ttt);
	}
	maintain();
}
LL sum(int pos,int tot){
	int t1=pos,t2=pos+tot-1;
	int x1=find(t1),x2=find(t2);
	LL ret=0;
	if(x1==x2){
		down(x1);
		for(int i=t1;i<=t2;i++) 
			ret+=s[x1].a[i];
	}
	else {
		down(x1),down(x2);
		for(int i=t1;i<=s[x1].sz;i++) ret+=s[x1].a[i];
		for(int i=1;i<=t2;i++)ret+=s[x2].a[i];
		for(int i=s[x1].nxt;i!=x2;i=s[i].nxt)ret+=s[i].sum;
	}
	return ret;
}
LL maxsum(){
	LL lm=s[0].lm,rm=s[0].rm,sum=s[0].sum,maxsum=s[0].maxsum,mx=-INF;
	for(int i=s[0].nxt;i;i=s[i].nxt){
		LL lm2,rm2,sum2,maxsum2;
		mx=max(mx,s[i].mx);
		sum2=sum+s[i].sum;
		lm2=max(lm,sum+s[i].lm);
		rm2=max(s[i].rm,s[i].sum+rm);
		maxsum2=max(maxsum,s[i].maxsum);
		maxsum2=max(maxsum2,rm+s[i].lm);
		sum=sum2;lm=lm2;rm=rm2,maxsum=maxsum2;
	}
	return mx<0?mx:maxsum;
}
void print(){
	for(int i=s[0].nxt;i;i=s[i].nxt) {
		down(i);
		for(int j=1;j<=s[i].sz;j++) printf("%d ",s[i].a[j]);
	}
	printf("\n");
}
void read(int &x){
	char c;
	bool fu=false;
	while((c=getchar())<'0' || c>'9') if(c=='-') fu=true;x=c-'0';
	while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';
	if(fu) x=-x;
}
int main(){
	//freopen("1500.in","r",stdin);freopen("1500.out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=n;i++)read(tmp[i]);
	s[0].nxt=newnode();
	insert(0,n);
	for(int i=1;i<=m;i++) {
		char op=getchar();
		switch(cnt++,op){
			int pos,tot,c;
			case 'I':{
				for(int i=1;i<=6;i++) getchar();
				read(pos),read(tot);
				for(int i=1;i<=tot;i++) 
					read(tmp[i]);
				insert(pos,tot);
				break;	
			}
			case 'D':{
				for(int i=1;i<=6;i++) getchar();
				read(pos),read(tot);
				remove(pos,tot);
				break;
			}
			case 'M':{
				getchar();
				char op2=getchar();
				if(op2=='K'){
					for(int i=1;i<=7;i++) getchar();
					read(pos),read(tot),read(c);
					change(pos,tot,c);
				}
				if(op2=='X'){
					for(int i=1;i<=5;i++) getchar();
					printf("%lld\n",maxsum());
				}
				break;
			}
			case 'R':{
				for(int i=1;i<=7;i++) getchar();
				read(pos),read(tot);
				flip(pos,tot);
				break;
			}
			case 'G':{
				for(int i=1;i<=6;i++) getchar();
				read(pos),read(tot);
				printf("%lld\n",sum(pos,tot));
				break;
			}
		}
	}
	return 0;
}