Splay裸题。
具体来说，维护两个延迟标记，翻转标记和改变标记。然后对于每一个标记考虑下传。
对于两种询问各自更新区间和与区间最大子段和。
一个区间的最大子段和有可能有三种情况：左子区间的最大子段和，右子区间的最大子段和，以及跨过两个区间的子段和。
故而我们对每个区间关于子段和维护三个信息，左起最大子段和、右起最大子段和以及总最大子段和。
而对于左起最大子段和的更新，则考虑两种情况：左子区间的最大子段和，以及整个左子区间加上根节点再加上右子区间的左起最大子段和。
右起同理。
注意：
- 1.updt时应当先updt(tr[X].sn[D^1])再updt(X)
- 2.添加节点和各种修改之后应当科学地rnw
- 3.添加节点时应当注意是从posi~posi+1之间的区间。
- 4.一个节点被删除以后，rnw它的父亲是没有意义的，应当从根开始rnw
- 5.内存回收机制中，添加入栈应当是++tp,出栈应当是tp–
- 6.考虑updt和pshd的方式：对于每一次pshd，我们应该统一修改它的子节点的标记，并对它的子节点计算贡献，然后取消它本身的标记；打标记的时候对它本身计算好贡献。
- 换句话说，不要在统计一个节点的贡献之前，updt它的父亲。
- 7.加入节点应当加入成一棵二叉树，而不是一条链。根据我根本不懂的势能分析法，加入一棵二叉树带来的势能改变是常数乘大小级的，而一条链则是对数乘大小级的。
- 8.对于MAX-SUM操作，必须要至少选中一个节点，所以应当额外维护一个最大值。
#include<iostream>
#include<cstdio>
#define R register
#define MAGIC 19260817
#define MID ((L+R_R)>>1)
/*
*/
inline int Max(int A,int B){
return A>B?A:B;
}
inline int Chck(int X){
return X>0?X:0;
}
inline void Swap(int &A,int &B){
A^=B^=A^=B;
}
//表示特殊状态
class Splay{
private:
class Node{
public:
int fa;
int sn[2];
int sz;
int sm;
int lmxsm;
int rmxsm;
int mxsm;
int mx;
int v;
int lzy_flp;
int lzy_chng;
inline void set(int FA,int V){
fa=FA,sz=1,sm=v=mxsm=mx=V,lmxsm=rmxsm=Chck(V);
sn[0]=sn[1]=lzy_flp=0,lzy_chng=MAGIC;
}
inline void init(){
fa=sz=sm=lmxsm=rmxsm=v=sn[0]=sn[1]=lzy_flp=0;
mxsm=mx=-MAGIC;
lzy_chng=MAGIC;
}
};
Node tr[500005];
int st[500005],tp,cnt,rt;
inline int fndD(int X){
return tr[tr[X].fa].sn[0]==X?0:1;
}
inline void chng(int X){
tr[X].sm=tr[X].lzy_chng*tr[X].sz,tr[X].mxsm=Max(tr[X].lzy_chng,tr[X].lzy_chng*tr[X].sz);tr[X].lmxsm=tr[X].rmxsm=Chck(tr[X].lzy_chng*tr[X].sz);
tr[X].v=tr[X].mx=tr[X].lzy_chng;
}
inline void flp(int X){
Swap(tr[X].sn[0],tr[X].sn[1]);
Swap(tr[X].lmxsm,tr[X].rmxsm);
}
inline void pshd(int X){
if(!X){
return;
}
if(tr[X].lzy_chng!=MAGIC){
tr[tr[X].sn[0]].lzy_chng=tr[tr[X].sn[1]].lzy_chng=tr[X].lzy_chng;
chng(tr[X].sn[0]),chng(tr[X].sn[1]);
tr[X].lzy_chng=MAGIC;
}
if(tr[X].lzy_flp){
tr[tr[X].sn[0]].lzy_flp^=1,tr[tr[X].sn[1]].lzy_flp^=1;
flp(tr[X].sn[0]),flp(tr[X].sn[1]);
tr[X].lzy_flp=0;
}
}
inline void updt(int X){
if(!X){
return;
}
tr[X].sm=tr[tr[X].sn[0]].sm+tr[tr[X].sn[1]].sm+tr[X].v;
tr[X].mx=Max(Max(tr[tr[X].sn[0]].mx,tr[tr[X].sn[1]].mx),tr[X].v);
tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
tr[X].lmxsm=Max(tr[tr[X].sn[0]].sm+tr[X].v+tr[tr[X].sn[1]].lmxsm,tr[tr[X].sn[0]].lmxsm);
tr[X].rmxsm=Max(tr[tr[X].sn[1]].sm+tr[X].v+tr[tr[X].sn[0]].rmxsm,tr[tr[X].sn[1]].rmxsm);
tr[X].mxsm=Max(Max(tr[tr[X].sn[0]].mxsm,tr[tr[X].sn[1]].mxsm),tr[tr[X].sn[0]].rmxsm+tr[X].v+tr[tr[X].sn[1]].lmxsm);
}
inline void splayOne(int X){
int D=fndD(X),D2=fndD(tr[X].fa);
tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
tr[tr[X].sn[D^1]].fa=X,tr[tr[X].fa].sn[D2]=X;
updt(tr[X].sn[D^1]),updt(X);
}
inline void splayTwo(int X){
int D=fndD(X),D2=fndD(tr[X].fa);
tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
}
inline void splayRnw(int X){
if(!X){
return;
}
//printf("%d->",X);
while(tr[X].fa){
splayTwo(X);
//printf("[%d,%d,%d[%d,%d](%d)] ",X,tr[X].fa,tr[tr[X].fa].fa,tr[X].sn[0],tr[X].sn[1],fndD(X));
}
//puts("");
rt=X;
}
//注意，权值splay中的fnd函数实质上求的是排名为K的节点。
inline int fnd(int K){
R int P=rt,FP=0;
while(P){
pshd(P);
FP=P;
if(tr[tr[P].sn[0]].sz+1<K){
K-=(tr[tr[P].sn[0]].sz+1);
P=tr[P].sn[1];
}else if(tr[tr[P].sn[0]].sz<K){
return P;
}else{
P=tr[P].sn[0];
}
}
return FP;
}
inline int nwlc(int FA,int D,int V){
if(!cnt){
rt=1;
}
int P=tp?st[tp--]:++cnt;
tr[FA].sn[D]=P;
tr[P].set(FA,V);
return P;
}
inline int preSplay(int L,int LEN){
int __L__=fnd(L),__R__=fnd(L+LEN+1);
splayRnw(tr[__L__].fa),splayRnw(tr[__R__].fa);
splayRnw(__L__);
splayRnw(__R__);
//printf("%d,%d,%d\n",rt,tr[rt].sn[0],tr[rt].sn[1]);
if(tr[__L__].fa!=__R__&&__L__!=__R__){
splayOne(__L__);
}
pshd(tr[tr[rt].sn[0]].sn[1]);
return tr[rt].sn[0];
}
inline void rmv(int X){
if(!X){
return;
}
rmv(tr[X].sn[0]);
rmv(tr[X].sn[1]);
tr[tr[X].fa].sn[fndD(X)]=0;
tr[tr[X].sn[0]].fa=tr[tr[X].sn[1]].fa=0;
st[++tp]=X;
}
inline void prnt(int X, int dep=0){
if(!X){
return;
}
//pshd(X);
prnt(tr[X].sn[0], dep+1);
//printf("{%d}[%d](%d,%d)[%d][%d,%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].mxsm,tr[X].lmxsm,tr[X].rmxsm);
for(int i = 1; i <= dep; ++i) printf("口");
//printf("ID:%d VAL:%d SM:%d CHANGE_TAG:%d \n",X,tr[X].v,tr[X].sm,tr[X].lzy_chng);
printf("%d %d\n",tr[X].v,tr[X].mxsm);
prnt(tr[X].sn[1], dep+1);
}
inline void build(int L,int R_R,int *IN,int D,int FA){
if(L>R_R){
return;
}
int P=nwlc(FA,D,IN[MID]);
build(L,MID-1,IN,0,P);
build(MID+1,R_R,IN,1,P);
updt(P);
}
public:
inline void INSERT(int L,int TOT,int *IN){
int X=preSplay(L+1,0);
build(1,TOT,IN,1,X);
updt(X),updt(tr[X].fa),updt(tr[tr[X].fa].fa);
}
inline void DELETE(int L,int LEN){
int X=tr[preSplay(L,LEN)].sn[1];
rmv(X);
updt(tr[rt].sn[0]),updt(rt);
}
inline void MAKE_SAME(int L,int LEN,int V){
int X=tr[preSplay(L,LEN)].sn[1];
tr[X].lzy_chng=V;
chng(X);
updt(tr[X].fa),updt(tr[tr[X].fa].fa);
}
inline void REVERSE(int L,int LEN){
int X=tr[preSplay(L,LEN)].sn[1];
tr[X].lzy_flp^=1;
if(tr[X].lzy_flp){
flp(X);
}
updt(tr[X].fa),updt(tr[tr[X].fa].fa);
}
inline void GET_SUM(int L,int LEN){
int X=tr[preSplay(L,LEN)].sn[1];
printf("%d\n",tr[X].sm);
}
inline void MAX_SUM(){
printf("%d\n",(tr[rt].mxsm)?tr[rt].mxsm:tr[rt].mx);
}
inline void INIT(int N,int *IN){
tr[0].init();
rt=tp=cnt=0;
int X=0;
for(int i=1;i<=N;++i){
X=nwlc(X,1,IN[i]);
}
nwlc(1,0,-MAGIC),nwlc(X,1,-MAGIC);
splayRnw(N+1),splayRnw(N+2);
}
inline void PRINT(){
printf("%d ->\n",rt);
prnt(rt);
puts("");
}
};
int n,m;
int a[4000005];
Splay T;
void init(){
scanf("%d%d",&n,&m);
int posi,tot,c;
char op[10];
for(int i=1;i<=n;++i){
scanf("%d",a+i);
}
T.INIT(n,a);
for(int i=1;i<=m;++i){
std::cin>>op;
switch(op[2]){
case 'S':{
scanf("%d%d",&posi,&tot);
for(int j=1;j<=tot;++j){
scanf("%d",a+j);
}
T.INSERT(posi,tot,a);
break;
}
case 'L':{
scanf("%d%d",&posi,&tot);
T.DELETE(posi,tot);
break;
}
case 'K':{
scanf("%d%d%d",&posi,&tot,&c);
T.MAKE_SAME(posi,tot,c);
break;
}
case 'V':{
scanf("%d%d",&posi,&tot);
T.REVERSE(posi,tot);
break;
}
case 'T':{
scanf("%d%d",&posi,&tot);
T.GET_SUM(posi,tot);
break;
}
case 'X':{
T.MAX_SUM();
break;
}
}
}
}
int main(){
init();
return 0;
}
