链接：https://www.luogu.org/problemnew/show/P2042
题解：
写模板这道题的时候遇到一些错误
1.对于元素初始化，又没写全面
2.max_pre 没有更新当前点
3.search里面少down了
注意点非常多的一道题
首先维护最大序列和可以类似线段树，维护max_all,max_pre,max_ess,
这样三个简单的方程就可以转移了
*但是 由于题目要求max_all中至少有一个元素，所以应该求一下其中的最大值
另外对于insert操作只需加入用那些节点建一颗新树，再连上去就可以了
*另外 这题的内存是会超的，所以要用内存池记录删去的元素
其中内存池中的元素要注意将其之前的值清空
其他就是平衡树的基本操作了
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 1111
#define INF 20000
int q1,q2,max_number[maxn],n,m,lazy[maxn],leftson[maxn],rightson[maxn],data[maxn],fa[maxn],root,
num,max_all[maxn],max_pre[maxn],max_ess[maxn],count2[maxn],sum[maxn],a[maxn],b[maxn];
queue<int> q;
bool rev[maxn];
void down(int x)
{
if (x==0) return;
if (lazy[x]!=-INF)
{
max_number[x]=lazy[x]; rev[x]=0;
data[x]=lazy[x];
sum[x]=count2[x]*lazy[x];
if (lazy[x]>=0)
{
max_pre[x]=count2[x]*lazy[x];
max_ess[x]=count2[x]*lazy[x];
max_all[x]=count2[x]*lazy[x];
} else
{
max_pre[x]=max_ess[x]=max_all[x]=0;
}
lazy[leftson[x]]=lazy[x];
lazy[rightson[x]]=lazy[x];
lazy[x]=-INF;
}
if (rev[x])
{
swap(leftson[x],rightson[x]);
swap(max_pre[x],max_ess[x]);
rev[leftson[x]]^=1; rev[rightson[x]]^=1;
rev[x]=0;
}
}
void updata(int x)
{
down(leftson[x]); down(rightson[x]);
max_number[x]=max(max(max_number[leftson[x]],max_number[rightson[x]]),data[x]);
count2[x]=count2[leftson[x]]+count2[rightson[x]]+1;
sum[x]=sum[leftson[x]]+sum[rightson[x]]+data[x];
max_pre[x]=max(max_pre[leftson[x]],sum[leftson[x]]+data[x]+max_pre[rightson[x]]);
max_ess[x]=max(max_ess[rightson[x]],sum[rightson[x]]+data[x]+max_ess[leftson[x]]);
max_all[x]=max(max(max_all[leftson[x]],max_all[rightson[x]]),max_ess[leftson[x]]+data[x]+max_pre[rightson[x]]);
}
void rotate(int x,int y)
{
int father=fa[x];
down(father); down(x);
if (y==1)
{
rightson[father]=leftson[x];
if (leftson[x]) fa[leftson[x]]=father;
} else
{
leftson[father]=rightson[x];
if (rightson[x]) fa[rightson[x]]=father;
}
fa[x]=fa[father];
if (fa[father])
{
if (leftson[fa[father]]==father)
leftson[fa[father]]=x;
else rightson[fa[father]]=x;
}
fa[father]=x;
if (y==1) leftson[x]=father; else rightson[x]=father;
updata(father); updata(x);
}
void splay(int x,int goal)
{
if (x==root) return;
int father;
while (fa[x]!=goal)
{
father=fa[x];
if (fa[father]==goal)
{
if (x==leftson[father]) rotate(x,2);
else rotate(x,1);
} else
{
if (father==leftson[fa[father]])
{
if (x==leftson[father])
rotate(father,2),rotate(x,2);
else rotate(x,1),rotate(x,2);
} else
{
if (x==rightson[father])
rotate(father,1),rotate(x,1);
else rotate(x,2),rotate(x,1);
}
}
}
if (goal==0) root=x;
}
#define mid (h+t)/2
void build(int h,int t,int father,bool x,int a[maxn])
{
num=q.front(); q.pop();
count2[num]=1; data[num]=a[mid]; fa[num]=father;
if (father)
{
if (x==1) leftson[father]=num; else rightson[father]=num;
}
int tmp=num;
if (h<mid) build(h,mid-1,tmp,1,a);
if (mid<t) build(mid+1,t,tmp,0,a);
updata(tmp);
}
int search(int goal)
{
int x=root,cnt=1;
while (x)
{
down(x);
if (cnt+count2[leftson[x]]==goal) return(x);
if (count2[leftson[x]]+cnt<goal)
{
cnt+=count2[leftson[x]]+1; x=rightson[x];
} else
{
x=leftson[x];
}
}
}
void reserve(int x,int y)
{
int x1=search(x),y1=search(y+2);
splay(x1,0);
splay(y1,x1);
rev[leftson[y1]]^=1;
}
void recycle(int x)
{
if (x==0) return;
recycle(leftson[x]);
recycle(rightson[x]);
max_number[x]=-INF; lazy[x]=-INF; rev[x]=0;
leftson[x]=0; rightson[x]=0; max_pre[x]=0;
max_all[x]=0; max_ess[x]=0; sum[x]=0;
q.push(x); q1++;
}
void del(int x,int y,int num)
{
int x1=search(x),y1=search(y+2);
splay(x1,0);
splay(y1,x1);
recycle(leftson[y1]);
leftson[y1]=0;
updata(y1); updata(x1);
}
void ins(int x,int y,int a[maxn],int l)
{
q2+=l;
int x1=search(x),y1=search(y+2);
splay(x1,0);
splay(y1,x1);
int tmp=q.front();
build(1,l,0,0,a);
fa[tmp]=y1; leftson[y1]=tmp;
updata(y1); updata(x1);
}
void query1(int x,int y)
{
int x1=search(x),y1=search(y+2);
splay(x1,0); splay(y1,x1);
cout<<sum[leftson[y1]]<<endl;
}
void query2(int x,int y)
{
int x1=search(x),y1=search(y+2);
splay(x1,0); splay(y1,x1);
if (max_number[leftson[y1]]>0)
cout<<max_all[leftson[y1]]<<endl;
else cout<<max_number[leftson[y1]]<<endl;
}
void change(int x,int y,int z)
{
int x1=search(x),y1=search(y+2);
splay(x1,0);splay(y1,x1);
lazy[leftson[y1]]=z;
}
char c[100];
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
std::ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=1;i<=maxn-10;i++) q.push(i);
for (int i=0;i<=maxn-1;i++) lazy[i]=-INF,max_number[i]=-INF;
for (int i=1;i<=n;i++) cin>>a[i]; a[0]=-INF; a[n+1]=-INF;
build(0,n+1,0,0,a); root=1;
// for (int i=0;i<=n+1;i++) insert(i,a[i]);
int ask=0;
for (int i=1;i<=m;i++)
{
ask=max(ask,n);
int d,e,f;
cin>>c;
if (c[2]=='S')
{
cin>>d>>e;
for (int j=1;j<=e;j++) cin>>b[j];
ins(d+1,d,b,e); n+=e;
}
if (c[2]=='L')
{
cin>>d>>e;
del(d,d+e-1,e); n-=e;
}
if (c[2]=='V')
{
cin>>d>>e;
reserve(d,d+e-1);
}
if (c[2]=='K')
{
cin>>d>>e>>f;
change(d,d+e-1,f);
}
if (c[2]=='T')
{
cin>>d>>e;
query1(d,d+e-1);
}
if (c[2]=='X')
{
query2(1,n);
}
}
// cout<<ask<<" "<<q1<<" "<<q2;
/* cout<<endl<<endl<<endl<<endl;
while (!q.empty())
{
cout<<q.front()<<endl;
q.pop();
} */
}
总结一下splay，打标记就是直接打得事情
每份代码里的splay和rotate操作是一样的
updata通过左右节点来计算当前节点
down将标记下传m,注意要考虑一下rev操作带来的影响