From The Stupid

类似于这道题的题似乎以前多面体在codevs月赛里出过

不管怎么动 处在同一列的格子总是处在同一列 行同理 则问题转化成要找到一些黑格子 其中任意两个都不在同一行或同一列

把行号看成二分图的一部 列看成另一部 那么就变成了一个二分图匹配的问题 对于每一个f[i][j]是黑的 我们连边(i,j)，之后匈牙利算法（不会的百度一下或者问学长）搞一下就好了

我在打匈牙利算法的时候 忘记在每一轮的匹配中加上这一轮匹配是否用过的标记 于是就wa了……

还有注意边的数比较多……

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=41000;
int e[N],pre[N],now[N],T,n,tail,to[N],from[N],vis[N],tmp;
bool flag;
void add(int u,int v){e[++tail]=v;pre[tail]=now[u];now[u]=tail;}
bool hungary(int a){
	for(int i=now[a];i;i=pre[i]){
		if(vis[e[i]]) continue;else vis[e[i]]=1;
		if(!from[e[i]] || hungary(from[e[i]])) {from[e[i]]=a,to[a]=e[i];return true;}
	}
	return false;
}
int main(){
	freopen("1059.in","r",stdin);freopen("1059.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(e,0,sizeof(e));
		memset(pre,0,sizeof(pre));
		memset(now,0,sizeof(now));
		memset(to,0,sizeof(to));
		memset(from,0,sizeof(from));
		tail=0;flag=1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				scanf("%d",&tmp);
				if(tmp) add(i,j);
			}
		for(int i=1;i<=n;i++){
			memset(vis,0,sizeof(vis));
			if(!hungary(i)) {flag=0;break;}
		}
		printf(flag?"Yes\n":"No\n");
	}
	return 0;
}

离散化+树状数组统计 

看到这题第一个反应二维树状数组 看数据范围 这画风不对啊……

考虑离线解决这个问题

首先离散化y轴坐标

我们发现可以把一个询问拆成4个询问 一个是从(0,0)到(cj,dj)一个从(0,0)到(aj-1,bj-1)一个从(0,0)到(aj-1,dj)一个从(0,0)到(cj,bj-1)，然后这个询问就可以用这几个相加减弄出来了。

将询问和树按横坐标排序后 从左往右扫一遍 遇到树就将其加入树状数组，遇到询问就查询一下，最后计算一下答案输出

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=4000000;
struct query{int x,y,y0,op,id;}q[N+10];
struct tree{int x,y;}t[N+10];
int s[N+10],ans[N+10],n,m,cnt=0,tmp=0;
bool cmp(query a,query b){return a.x==b.x?a.op<b.op:a.x<b.x;}
bool cmp2(query a,query b){return a.y<b.y;}
bool cmp3(query a,query b){return a.id<b.id;}
void add(int x,int d){for(;x<=tmp;x+=x&-x) s[x]+=d;}
int sum(int x){int ret=0;for(;x;x-=x&-x) ret+=s[x];return ret;}
void read(int &x){char c;while((c=getchar())<'0' || c>'9');x=c-'0';while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}
int main(){
	//freopen("1935.in","r",stdin);freopen("1935.out","w",stdout);
	// scanf("%d%d",&n,&m);
	read(n),read(m);q[0].y=-65478;
	for(int i=1;i<=n;i++) read(q[i].x),read(q[i].y);
	for(int i=1;i<=m;i++) {
		int x1,y1,x2,y2;
		read(x1);read(y1);read(x2);read(y2);
		// scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		q[n+(++cnt)].x=x1-1;//q1;
		q[n+cnt].y=y1-1;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;
		q[n+(++cnt)].x=x1-1;//q2;
		q[n+cnt].y=y2;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;
		q[n+(++cnt)].x=x2;//q3;
		q[n+cnt].y=y1-1;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;
		q[n+(++cnt)].x=x2;//q4;
		q[n+cnt].y=y2;
		q[n+cnt].id=cnt;
		q[n+cnt].op=1;//ans[i]=q4-q2-q3+q1
	}
	sort(q+1,q+n+4*m+1,cmp2);
	for(int i=1;i<=n+4*m;i++) {if(q[i].y!=q[i-1].y) tmp++;q[i].y0=tmp;}
	sort(q+1,q+n+4*m+1,cmp);
	for(int i=1;i<=n+4*m;i++){
		if(!q[i].op) add(q[i].y0,1);
		else ans[q[i].id]=sum(q[i].y0);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[4*i]-ans[4*i-1]-ans[4*i-2]+ans[4*i-3]);
	return 0;
}

线段树 

打两个标记，一个记录乘法一个记录加法，根据乘法分配律可以得到：标记下传的时候要先传乘法的标记再传加法的标记，下传乘法的时候要同时将子节点的加法标记也乘对应的数。

然后总结一下我自己犯的错误

1.标记下传时 判断无标记之后直接不操作 而不是把标记加上去 

2.线段树开始忘记build

3.开始的时候没有看到要取模

代码 

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=300010,NUL=-657558;
typedef long long LL;
LL sum[N*4],plus[N*4],mul[N*4],a[N],L[N*4],R[N*4],mod,m,op,x1,y1,z1,n;
void up(int x){sum[x]=(sum[x<<1]+sum[x<<1|1])%mod;}
void down(int x){
	if(mul[x]!=NUL) {
		(sum[x<<1]*=mul[x])%=mod;
		if(mul[x<<1]!=NUL) (mul[x<<1]*=mul[x])%=mod;else mul[x<<1]=mul[x]%mod;
		if(plus[x<<1]!=NUL) (plus[x<<1]*=mul[x])%=mod;
		(sum[x<<1|1]*=mul[x])%=mod;
		if(mul[x<<1|1]!=NUL) (mul[x<<1|1]*=mul[x])%=mod;else mul[x<<1|1]=mul[x]%mod;
		if(plus[x<<1|1]!=NUL) (plus[x<<1|1]*=mul[x])%=mod;
	}
	if(plus[x]!=NUL) {
		(sum[x<<1]+=plus[x]*(R[x<<1]-L[x<<1]+1)%mod)%=mod;
		if(plus[x<<1]!=NUL) (plus[x<<1]+=plus[x])%=mod;else plus[x<<1]=plus[x]%mod;
		(sum[x<<1|1]+=plus[x]*(R[x<<1|1]-L[x<<1|1]+1)%mod)%=mod;
		if(plus[x<<1|1]!=NUL) (plus[x<<1|1]+=plus[x])%=mod;else plus[x<<1|1]=plus[x]%mod;
	}
	mul[x]=plus[x]=NUL;
}
void build(int x,int l,int r){
	plus[x]=mul[x]=NUL;L[x]=l;R[x]=r;
	if(l==r) {sum[x]=a[l]; return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	up(x);
}
void change1(int x,int l,int r,int d){//plus
	int mid=(L[x]+R[x])>>1;
	if(l<=L[x] && R[x]<=r) {
		if(plus[x]!=NUL) (plus[x]+=d)%=mod;else plus[x]=d%mod;
		(sum[x]+=d*(R[x]-L[x]+1)%mod)%=mod;
		return;
	}
	down(x);
	if(mid<r) change1(x<<1|1,l,r,d);
	if(mid>=l) change1(x<<1,l,r,d);
	up(x);
}
void change2(int x,int l,int r,int d){//multiply
	int mid=(L[x]+R[x])>>1;
	if(l<=L[x] && R[x]<=r) {
		(sum[x]*=d%mod)%=mod;
		if(plus[x]!=NUL) (plus[x]*=d)%=mod;
		if(mul[x]!=NUL) (mul[x]*=d)%=mod; else mul[x]=d%mod;
		return;
	}
	down(x);
	if(mid<r) change2(x<<1|1,l,r,d);
	if(mid>=l) change2(x<<1,l,r,d);
	up(x);
}
LL ask(int x,int l,int r){
	int mid=(L[x]+R[x])>>1;
	LL ret=0;
	if(l<=L[x] && R[x]<=r) return sum[x];
	down(x);
	if(mid<r) (ret+=ask(x<<1|1,l,r))%=mod;
	if(mid>=l) (ret+=ask(x<<1,l,r))%=mod;
	return ret;
}
void print(){
	for(int i=1;i<=n;i++)
		printf("%lld ",ask(1,i,i));
	printf("\n");
}
int main(){
	//freopen("1798.in","r",stdin);freopen("1798.out","w",stdout);
	scanf("%lld%lld",&n,&mod);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&op,&x1,&y1);
		if(op==1) {scanf("%lld",&z1);change2(1,x1,y1,z1);}
		if(op==2) {scanf("%lld",&z1);change1(1,x1,y1,z1);}
		if(op==3) {printf("%lld\n",ask(1,x1,y1));}
	//	print();
	}
	return 0;
}

看起来是个傻逼题

定义f[i][j]表示第i个节目音量能否为j ,则f[i][j]= f[i-1][j+c[i]] || f[i-1][j-c[i]]。最后扫一下f[n]里面的最大值

滚动数组都不用开就过了

 代码

#include <cstdio>
#include <algorithm>
using namespace std;
int n,bl,ml,a[55],ans=0;
bool f[55][1010];
int main(){
	// freopen("2748.in","r",stdin);freopen("2748.out","w",stdout);
	scanf("%d%d%d",&n,&bl,&ml);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[0][bl]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=ml;j++) {
			if(j-a[i]>=0 && f[i-1][j-a[i]]) f[i][j]=1;
			if(j+a[i]<=ml && f[i-1][j+a[i]]) f[i][j]=1;
		}
	for(int i=ml;i>=0;i--) if(f[n][i]) {printf("%d",i);ans=1;break;}
	if(!ans) printf("-1");
	return 0;
}

这题本来第一个反应是数位dp 然而看到n这么大- - 管他呢照样数位dp 矩阵快速幂优化一下就好了

这道题的关键 是 利用kmp算法 构建转移矩阵

定义f[i][j]表示 i位的数字的最后j位 和不吉利数字的开始j位相同 的方案数有多少，然后我们就开始想转移方程，然而 这转移不是和给出的数字串有关吗……(其实我本来以为是f[i][j]=f[i-1][j-1]+9*f[i-1][j+1]的,打好之后发现样例都过不去……) 。既然字符串给出了 那我们一定可以用奇技淫巧弄出转移的方程 ——对就是kmp

我们用kmp算法匹配的时候 是不断的用fail指针跳转 直到匹配成功为止 在这里我们用相同的方法处理

对于某一个匹配长度k，我们枚举这个位置的数字i 然后进行匹配 fail指针不断的回跳 直到匹配成功或者跳出了字符串 这时候 我们就知道 匹配长度为k的字符串 在添加一个数字i之后 可以转移到哪个位置，转移矩阵中的对应位置++即可。这样就构造成功了转移矩阵，接下来就是用矩阵快速幂随便搞一下,把f[n][0]到f[n][m-1]加起来模一下就是答案了

代码

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,mod,s[30],f[30],nxt[30],sum;
struct mat{
	int a[30][30];
	void reset(){for(int i=0;i<30;i++) for(int j=0;j<30;j++) a[i][j]=0;}
	void set1(){reset();for(int i=0;i<=29;i++) a[i][i]=1;}
	friend mat operator *(mat x,mat y){
		mat z;
		z.reset();
		for(int i=0;i<=20;i++)
			for(int j=0;j<=20;j++)
				for(int k=0;k<=20;k++) (z.a[i][j]+=x.a[i][k]*y.a[k][j])%=mod;
		return z;
	}
}st,zy,ans;
void get(){
	int p;
	f[0]=0;f[1]=0;
	for(int i=2;i<=m;i++) {
		p=f[i-1];
		while(s[p]!=s[i-1] && p) p=f[p];
		f[i]= s[p]==s[i-1]?p+1:0;
	}
	for(int i=0;i<m;i++)
		for(int j=0;j<=9;j++) {
			if(j==s[i]) {zy.a[i][i+1]++;continue;}
			int p=f[i];
			while(s[p]!=j && p) p=f[p];
			if(s[p]==j) zy.a[i][p+1]++;else zy.a[i][0]++;
		}
}
int main(){
	//freopen("1009.in","r",stdin);freopen("1009.out","w",stdout);
	scanf("%d%d%d\n",&n,&m,&mod);
	for(int i=0;i<m;i++) s[i]=getchar()-'0';
	get();
	ans.set1();
	st.a[0][0]=1;
	for(;n;n>>=1){if(n&1)ans=ans*zy;zy=zy*zy;}
	st=st*ans;
	for(int i=0;i<m;i++) (sum+=st.a[0][i])%=mod;
	printf("%d",sum);
	return 0;
}

这题就是求 $\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)*2-1)$

我们考虑枚举k使 gcd(i,j)=k

定义 g[k]表示以k为公约数的i,j有多少对，f[k]表示以k为最大公约数的i,j有多少对

首先我们想k是若干个数的公约数(非最大) 那么  g[k]=(n/k)*(m/k)

而以k为最大公约数的时候 要用g[k]减掉 f[2k],f[3k],f[4k]...于是 $f[k]=g[k]-\sum_{i=1}^{i*k<=min(n,m)}f[i*k]$

最后求一下和就好了

下面是代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
typedef long long LL;
LL f[N],n,m,mx,ans;
int main(){
	//freopen("2005.in","r",stdin);freopen("2005.out","w",stdout);
	scanf("%lld%lld",&n,&m);mx=min(n,m);
	for(int i=1;i<=mx;i++) f[i]=(n/i)*(m/i);
	for(int i=mx;i>=1;i--) 
		for(int j=2;j*i<=mx;j++) f[i]-=f[j*i];
	for(int i=1;i<=mx;i++) ans+=(i*2-1)*f[i];
	printf("%lld",ans);
	return 0;
}

听说这道题可以用线性规划的方法水过去，但是这是一道网络流题

以下引用自百度

设每个时间i都需要有至少Ai个志愿者，设每种志愿者i使用了xi个，那么我们对于每个时间点都可以列出一个不等式：x1+x2+x3+...+xn>=Ai（其中如果第i类志愿者不能在该区间工作则xi固定为0）。

最后要求最小化w1*x1+w2*x2+x3*x3+...+wn*xn（其中wi是第i种志愿者的单位价格）。

这正是一个线性规划的问题。

那么我们是否可以转化为网络流来求解呢？

当然是可以哒~

现在我们将每个点的Ai取反，变成-Ai，这样他就成了一个“坑”了（相对于y=0而言），我们从源点S给最左边的时间点引流，流的大小为U（U为大整数），然后每个时间点i向时间点i+1建边（i，i+1，U-Ai，0），最后设汇点为最右端的时间点。

现在，如果所有时间点的Ai都为0，那么显然，汇点的流量恰好等于U。

问题来了，现在我们有的Ai不等于0了，那么显然源点到汇点的流量被这些“坑”所截断了，怎么解决这一个问题？

假设志愿者工作的时间为【Li，Ri】，且该种志愿者单位花费为Ci，则我们建边（Li，Ri+1，INF，Ci），表示我们雇佣了一些志愿者“填坑”来了，如果雇佣了xi个志愿者，则说明将该区间内的所有“坑”的深度填掉了xi（当然可能有的坑在“填坑”行动后高于y=0，那也无所谓了嘛，多多益善~）。

那么现在是不是看起来思路有一点清晰了？

于是志愿者的作用就是一个人可以填一个区间的“坑”（好厉害！），然后需要每种志愿者选择一些使得花费最小的情况下填掉所有的“坑”，就是这样~

最后就是让费用流帮我们选择志愿者的时候了~

于是我们按照上面的方法跑完一遍最小费用最大流，如果流量等于U，则说明满流（志愿者们成功填掉了所有的坑，同志们辛苦了~），此时的记录的cost就是最小值（cost为算法记录的最小费用）。如果流量不等于U则无解。

这时我们又收获了一种费用流的模型：初始给一道大流，然后将有至少覆盖次数限制的点（边）的权值取反变成“坑”，最后区间覆盖就等于“填坑”，只要最后的流量等于大流的流量，就有解。

或者看这个题解 http://blog.csdn.net/fzhvampire/article/details/50889187

接下来是代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010,INF=1000000000;
int to[N*2],from[N*2],pre[N*2],cost[N*2],flow[N],q[N],l,r,inq[N],dis[N],now[N],prev[N],tail=1,n,m,a,s,t,c,left=INF,ans;
void add(int u,int v,int cap,int co){to[++tail]=v;from[tail]=u;pre[tail]=now[u];now[u]=tail;cost[tail]=co;flow[tail]=cap;}
bool spfa(int s,int t){
	for(int i=1;i<=n+2;i++) dis[i]=INF;
	l=r=0;q[++r]=s;inq[s]=1;dis[s]=0;
	while(l<r){
		int x=q[(++l)%N];inq[x]=0;
		for(int i=now[x];i;i=pre[i]) if(flow[i]>0){
			if(dis[to[i]] > dis[x] + cost[i]) {
				dis[to[i]]=dis[x]+cost[i],prev[to[i]]=i;
				if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1;
			}
		}
	}
	return dis[t]!=INF;
}
int zg(int s,int t){
	int f=INF,sum=0;
	for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]);
	for(int i=t;i!=s;i=from[prev[i]]) flow[prev[i]]-=f,flow[prev[i]^1]+=f,sum+=cost[prev[i]]*f;
	return sum;
}
int main(){
	//freopen("1061.in","r",stdin);freopen("1061.out","w",stdout);
	scanf("%d%d",&n,&m);
	add(n+2,1,INF,0);add(1,n+2,0,0);
	for(int i=1;i<=n;i++) scanf("%d",&a),add(i,i+1,INF-a,0),add(i+1,i,0,0);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&s,&t,&c),add(s,t+1,INF*2,c),add(t+1,s,0,-c);
	while(spfa(n+2,n+1)) 
	ans+=zg(n+2,n+1);
	printf("%d",ans);
	return 0;
}

这题 可以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;
}