[NOI2005]维护数列 做题心得
这题我很久以前就写了，但是经常90
现在仔细分析了一下我发现，原来是我写题的时候基础定义不明确。实际上，在信息竞赛中，我们通常只注重思想差不多对了就开始写代码，实际上，我们维护的东西具体定义：维护的是什么信息？具体怎么定义？可不可以是0？可不可以空？这些都要好好考虑，从理论上分析，确保没有漏洞了，再开始写代码。
还有就是，一定要小心细节啊啊啊
题解部分
分析题目
有6个操作，一个一个看
在...后插入（insback）
我们可以先把后面的数列建一颗splay树，找到它的树根对应点 (u) ，找地方插入。
那这样就是两个参数：插入的位置 (p)，点 (u)
特判一下首尾插入，然后找到插入的位置，一前一后splay一下，然后就可以插入过来了。
具体的说，就是 (splay(kth(p)))，然后 (splay(kth(p+1)))，到 (kth(p)) 之下（p+1在p右边，显然是右儿子）
然后这时候，根的右儿子的左儿子就空出来一个位置，把 (u) 放在这里即可；同时，这里正好也是 (p) 和 (p+1) 之间，满足我们"在...后插入"的需求
区间操作：区间删除，区间修改（翻转，覆盖）
首先我们搞一个提取区间的操作：通过区间两端（l-1，r+1）splay两下，把区间的点都打在一颗连续的子树里。
假设这颗子树的根是 (u)。并且称这个操作为 区间提取操作 （split）。接下来就好办了：
- 对于删除，找到 (u) 之后断点它和父亲的边，并回收节点即可
- 对于修改，找到 (u) 之后打对应的 tag 即可
这里有一个小细节：你可以选择回收或者不回收，不回收节约一点常数时间，但是浪费一点常数空间，并且多常数倍代码
我个人是不喜欢开太多空间，所以选择了回收
区间求和，与区间求最大连续子段和（非空）
前面一个很trival，细节部分主要在后面
众所周知最大连续子段和就是搞出来一个左连续最大，右连续最大，区间最大子段和，区间和，然后瞎上传一下就行了。
splay区间和线段树区间不太一样，splay 区间带一个中间点。所以我们要不同的考虑：
-
最大子段和落在左儿子/右儿子的内部，直接两边取max即可
这也就说明左右儿子维护的最大子段和，应该是非空的
-
跨过中间 点，那就是当前的值+左儿子的右连续+右儿子的左连续
由于我们已经保证了跨过中间点，所以左右儿子的连续都应该维护的是 可空 的
细节
0号节点的最大子段和应该是 (-infin)
要不然对于一段全负的区间，如果它左儿子/右儿子中有一个是空的，那么它就会把 0 号节点的最大子段和上传上来，认为当前最大子段和是 0 —— 而它应该是一个负的值。
还有就是，各种操作都特判一下首尾，别忘了update和pushdown
代码
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
#define N 1000006
#define F(i,l,r) for(int i=l;i<=r;++i)
#define D(i,r,l) for(int i=r;i>=l;--i)
#define Fs(i,l,r,c) for(int i=l;i<=r;c)
#define Ds(i,r,l,c) for(int i=r;i>=l;c)
#define MEM(x,a) memset(x,a,sizeof(x))
#define FK(x) MEM(x,0)
#define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))
#define p_b push_back
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define iter(a,p) (a.begin()+p)
#define PUT(a,n) F(i,1,n) printf("%d ",a[i]); puts("");
int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}
template <typename T> void Rd(T& arg){arg=I();}
template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}
void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}
int n,m;
void Input()
{
Rd(n,m);
}
struct info
{
int s,ls,rs,mx;
info(int x=0,int len=1)
{
s=len*x;
if (x>0) ls=rs=mx=s;
else ls=rs=0,mx=x;
}
};
info merge3(info a,int val,info b)
{
info res;
res.s=a.s+val+b.s;
res.ls=max(a.ls,a.s+val+b.ls);
res.rs=max(b.rs,b.s+val+a.rs);
res.mx=max({a.mx,b.mx,a.rs+b.ls+val});
return res;
}
class SplayTree
{
public:
int ch[N][2],fa[N];
int val[N]; info s[N]; int sz[N];
int cov[N],rev[N];
int pool[N],psz=0;
int tot=0,rt=0;
#define ls(u) ch[u][0]
#define rs(u) ch[u][1]
bool id(int u) {return u==rs(fa[u]);}
int lk(int f,bool i,int u) {return fa[ch[f][i]=u]=f;}
void cl(int u)
{
if (u==0) return;
ls(u)=rs(u)=fa[u]=val[u]=sz[u]=0; s[u]=info(0);
rev[u]=0; cov[u]=-114514;
}
int newp(int x=0)
{
int u=psz?pool[psz--]:++tot;
cl(u); val[u]=x; s[u]=info(x);
return u;
}
void cycall(int u)
{
if (ls(u)) cycall(ls(u));
if (rs(u)) cycall(rs(u));
cl(u); pool[++psz]=u;
}
void up(int u)
{
if (u==0) return;
s[u]=merge3(s[ls(u)],val[u],s[rs(u)]);
sz[u]=sz[ls(u)]+sz[rs(u)]+1;
}
void covone(int u,int c)
{
val[u]=cov[u]=c;
s[u]=info(c,sz[u]);
}
void revone(int u)
{
swap(ls(u),rs(u)); swap(s[u].ls,s[u].rs);
rev[u]^=1;
}
void down(int u)
{
if (cov[u]!=-114514)
{
rev[u]=0;
if (ls(u)) covone(ls(u),cov[u]);
if (rs(u)) covone(rs(u),cov[u]);
cov[u]=-114514;
}
if (rev[u])
{
if (ls(u)) revone(ls(u));
if (rs(u)) revone(rs(u));
rev[u]=0;
}
}
void downall(int u)
{
if (fa[u]) downall(fa[u]);
down(u);
}
void rot(int u)
{
int f=fa[u],f2=fa[f],i=id(u),i2=id(f),w=ch[u][i^1];
lk(f2,i2,lk(u,i^1,lk(f,i,w))); fa[0]=ch[0][i2]=0;
up(f); up(u);
}
void sp(int u,int to=0)
{
downall(u);
while(fa[u]!=to)
{
int f=fa[u];
if (fa[f]!=to)
{
rot(id(u)==id(f)?f:u);
}
rot(u);
}
if (!to) rt=u;
}
int kth(int k)
{
int u=rt;
while(1)
{
down(u);
if (k<=sz[ls(u)])
{
u=ls(u);
}
else
{
k-=sz[ls(u)];
if (k==1)
{
sp(u); return u;
}
else
{
k--; u=rs(u);
}
}
}
}
int build(int *p,int l,int r)
{
if (l>r) return 0;
int mid=(l+r)>>1;
int u=newp(p[mid]);
lk(u,0,build(p,l,mid-1)); fa[0]=0;
lk(u,1,build(p,mid+1,r)); fa[0]=0;
up(u); return u;
}
void insback(int p,int uu)
{
if (p==0)
{
int u=rt; down(u);
while(ls(u))
{
u=ls(u);
down(u);
}
sp(u); up(lk(u,0,uu));
}
else if (p==sz[rt])
{
int u=rt; down(u);
while(rs(u))
{
u=rs(u);
down(u);
}
sp(u); up(lk(u,1,uu));
}
else
{
int kl=kth(p),kr=kth(p+1);
sp(kl); sp(kr,kl);
up(lk(rs(rt),0,uu)); up(rt);
}
}
int split(int l,int r)
{
if (l==1 and r==sz[rt]) return rt;
if (l==1)
{
sp(kth(r+1)); return ls(rt);
}
if (r==sz[rt])
{
sp(kth(l-1)); return rs(rt);
}
int kl=kth(l-1),kr=kth(r+1);
sp(kl); sp(kr,kl); return ls(rs(rt));
}
void rangedel(int l,int r)
{
int u=split(l,r),f=fa[u],i=id(u);
ch[f][i]=0; cycall(u);
up(f); up(fa[f]);
}
void rangerev(int l,int r)
{
int u=split(l,r),f=fa[u],i=id(u);
revone(u);
up(f); up(fa[f]);
}
void rangecov(int l,int r,int c)
{
int u=split(l,r),f=fa[u],i=id(u);
covone(u,c);
up(f); up(fa[f]);
}
info query(int l,int r)
{
int u=split(l,r),f=fa[u],i=id(u);
return s[u];
}
}T;
int tmp[N];
void Sakuya()
{
T.s[0].mx=-1e9;
F(i,1,n) tmp[i]=I();
T.rt=T.build(tmp,1,n);
F(i,1,m)
{
char o[10]; scanf("%s",o);
if (o[0]=='I')
{
int p,len; Rd(p,len);
if (len==0) continue;
F(j,1,len) tmp[j]=I();
int u=T.build(tmp,1,len);
T.insback(p,u);
}
if (o[0]=='D')
{
int p,len; Rd(p,len);
if (len==0) continue;
T.rangedel(p,p+len-1);
}
if (o[0]=='M' and o[2]=='K')
{
int p,len,c; Rd(p,len,c);
if (len==0) continue;
T.rangecov(p,p+len-1,c);
}
if (o[0]=='R')
{
int p,len; Rd(p,len);
if (len==0) continue;
T.rangerev(p,p+len-1);
}
if (o[0]=='G')
{
int p,len; Rd(p,len);
info tmp=T.query(p,p+len-1);
printf("%d
",tmp.s);
}
if (o[0]=='M' and o[2]=='X')
{
info tmp=T.s[T.rt];
printf("%d
",tmp.mx);
}
}
}
void IsMyWife()
{
Input();
Sakuya();
}
}
#undef int //long long
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();
return 0;
}