[文章目录]
Description
这是我写的第二道splay，由于小细节，耗时比较大。不过A了还是很开心的。
插入，删除，修改，翻转，求和没得说。
不过反转要注意一下在标记后需要更新一下root->rs和root，由于还有区间最大子序列，所以需要更新，并不像文艺平衡树那样，只更新size，还可以省略。
求和最大的子序列的splay（是不是想到了小白逛公园233），所以我们维护几个连续子序列最大值。
1.mxs，表示当前节点代表的子树区间中和最大的子序列（不可以没有元素）
2.mxl，表示包含左节点的和最大子序列（可以没有元素）
3.mxr，表示包含右节点的序列（可以无元素）
然后就得到了递推式：
mxs=max(ls->mxs , rs->mxs , ls->mxr+val+rs->mxl);
mxl=max(ls->mxl , ls->sum+val+mxr->mxl);
mxr=max(rs->mxr , rs->sum+val+ls->mxr);
由于mxl和mxr可以为0，所以不用考虑区间端点在val左右时的情况。
然后就是各种考码力的东西。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[501000];
int n,m;
char st[100];
int pos,tot,c;
int read()//加负号的读入优化
{
int re=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9'){if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') re=(re<<1)+(re<<3)+gc-'0',gc=getchar();
return re*f;
}
struct node
{
node *fa,*ls,*rs;
int val,sum,size,mxl,mxr,mxs;
bool tur;//旋转标记
int chag;//更改标记
node(int x);
void push_up();
void push_down();
void reverse();
void make_same(int x);
}*null=new node(0xefefefef),*root;
node :: node(int x)//直接初始化的时候将点权赋上
{
fa=ls=rs=null;
sum=null?x:0;//null的sum一定为0
mxs=val=x;
tur=false;
mxl=mxr=max(0,x);
chag=-1100;
size=null?1:0;//
}
void node :: reverse()
{
swap(ls,rs);
swap(mxl,mxr);//这两个也要换，不过在第一次WA的时候就发现了
tur^=1;
}
void node :: make_same(int x)//写这种函数的时候应该看结构体定义了啥，每个的含义都是啥
{
val=chag=x;
sum=x*size;
mxr=mxl=max(sum,0);
mxs=max(x,sum);
}
void node :: push_up()//向上修改
{
size=ls->size+rs->size+1;
mxl=max(ls->mxl,ls->sum+val+rs->mxl);
mxr=max(rs->mxr,rs->sum+val+ls->mxr);
mxs=max(max(ls->mxs,rs->mxs),ls->mxr+val+rs->mxl);
sum=ls->sum+val+rs->sum;
}
void node :: push_down()//下传标记
{
if(tur)
{
if(ls!=null)ls->reverse();
if(rs!=null)rs->reverse();
tur=0;
}
if(chag!=-1100)
{
if(ls!=null)ls->make_same(chag);
if(rs!=null)rs->make_same(chag);
chag=-1100;
}
}
node* build(int l,int r)
{
if(l>r) return null;
int mid=l+r>>1;
node *re=new node(a[mid]);
re->ls=build(l,mid-1);
re->rs=build(mid+1,r);
re->ls->fa=re;re->rs->fa=re;
re->push_up();
return re;
}
void initialize()//初始化
{
root=new node(0);//由于val赋值为0，所以查询mxs时要更改区间
root->rs=new node(0);
root->rs->ls=build(1,n);
root->rs->ls->fa=root->rs;
root->rs->fa=root;
root->rs->push_up();
root->push_up();
}
void zig(node *x)
{
node *y=x->fa;
y->ls=x->rs;
x->rs->fa=y;
x->rs=y;
x->fa=y->fa;
if(y==y->fa->ls) y->fa->ls=x;
else if(y==y->fa->rs) y->fa->rs=x;
y->fa=x;
y->push_up();
x->push_up();
if(y==root) root=x;
}
void zag(node *x)
{
node *y=x->fa;
y->rs=x->ls;
x->ls->fa=y;
x->ls=y;
x->fa=y->fa;
if(y==y->fa->ls) y->fa->ls=x;
else if(y==y->fa->rs) y->fa->rs=x;
y->fa=x;
y->push_up();//注意顺序
x->push_up();
if(y==root) root=x;
}
void splay(node *x,node *tar)
{
while(1)
{
node *y=x->fa,*z=y->fa;
if(y==tar) break;
if(z==tar)
{
if(x==y->ls) zig(x);
else zag(x);
break;
}
if(x==y->ls)
{
if(y==z->ls) zig(x),zig(x);
else zig(x),zag(x);
}
else
{
if(y==z->rs) zag(x),zag(x);
else zag(x),zig(x);
}
}
}
void find(node *x,int y,node *z)
{
while(1)
{
x->push_down();//在这里下传了，splay时就不用了
int tmp=x->ls->size;
if(y<=tmp) x=x->ls;
else
{
y-=tmp;
if(y==1) break;
y--;
x=x->rs;
}
}
splay(x,z);
}
void Free(node *x)//一定要释放内存，else MLE+1
{
if(x==null) return ;
Free(x->ls);
Free(x->rs);
free(x);
}
/*void dfs(node *x)
{
if(x==null) return ;
x->push_down();
dfs(x->ls);
printf("%d: sum%d size%d mxL%d mxR%d mxs%d\n tur%d chag%d ls%d rs%d\n",x->val,x->sum,x->size,x->mxl,x->mxr,x->mxs,x->tur,x->chag,x->ls->val,x->rs->val);
dfs(x->rs);
}*/
//调试用的，感觉不错哦233
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) a[i]=read();
initialize();
while(m--)
{
scanf("%s",st+1);
switch(st[3])
{
case 'S'://添加
{
pos=read();tot=read();
for(int i=1;i<=tot;i++) a[i]=read();
find(root,pos+1,null);
find(root,pos+2,root);
root->rs->ls=build(1,tot);
root->rs->ls->fa=root->rs;
root->rs->push_up();//
root->push_up();
break;
}
case 'L'://删除
{
pos=read();tot=read();
find(root,pos,null);
find(root,pos+tot+1,root);
node *tmp=root->rs->ls;//
root->rs->ls=null;
root->rs->push_up();//
root->push_up();
Free(tmp);//释放内存
break;
}
case 'K'://改成相同的
{
pos=read();tot=read();c=read();
find(root,pos,null);
find(root,pos+tot+1,root);
root->rs->ls->make_same(c);//不是简单chag=c标记
root->rs->push_up();//啊啊啊啊啊，重中之重
root->push_up();
break;
}
case 'V'://反转
{
pos=read();tot=read();
find(root,pos,null);
find(root,pos+tot+1,root);
root->rs->ls->reverse();//
root->rs->push_up();//重中之重，一顿神调
root->push_up();
break;
}
case 'T'://求和
{
pos=read();tot=read();
find(root,pos,null);
find(root,pos+tot+1,root);
printf("%d\n",root->rs->ls->sum);//不用向上修改了233
break;
}
case 'X':
{
find(root,1,null);//啊啊啊啊啊，最后WA的一个点
find(root,root->size,root);
printf("%d\n",root->rs->ls->mxs);
break;
}
}
}
return 0;
}