[题解] Luogu P2042 [NOI2005]维护数列
大概是 Splay 的新手村最终关。
写完这个大概就算入了门。 S 树受虐全集 - 从入门到入土 
Problem
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
Solution
本题我们从几个方面来阐述。
第一，文艺平衡树 你得会写。
第二，你至少得写过其它一个维护区间的题目。
第三，你会线段树。你知道 lazy 的思想。
第四，本题我使用的是不维护父指针递归版本。
那么我们开始。细节我们一个一个来。
Struct
总而言之，我们要维护：
序列插入 / 删除 / 翻转 / 整体更改操作。序列和。子序列最大和。
许多操作我们将用到线段树的思想。
线段树是用一个棵二叉树，每个点表示一个区间，是二分的思想。而换到平衡树里面来，我们发现，每一颗子树的范围也是一个区间。所以在平衡树中，我们使用子树的根节点代表一个区间。
如果根节点能够维护子树的区间的话，那我们只需要提取那个区间的子树，输出子树根节点的信息就行了。
这就是平衡树中的线段树思想。而复杂度也是 log(n)的。且目前，我只知道 splay 能做到这种操作。
那么既然要用点维护子树序列的信息，我们需要用结构体保存以下信息。
struct Node {
int v,s,c;
Node *ch[2];
int lx,rx,mx,sum;
bool t1,t2; // tag1 -> chg; tag2 -> rev
... 前几个我就不用说了。
第四行开始是维护子树序列的信息。前三维护最大子序列，后一维护和。
第五行维护的是 lazy 标记。
干嘛用的我们一个个说。
Basic Operation
k 大比较函数，pushdown，pushup（包括了更新子树大小操作 / 子树序列变化之后的更新操作）等。
pushup 就是因为你旋转之后子树可能改变，那么子树代表的序列就改变了，因此你需要更新新子树序列的根节点。就是这种操作。
Insert
Initalization
因为我不会构造完美平衡树所以我用了另一个方法。大概是 O(3n)。
/* Input */
root=new Node(-INF), root->sum=0;
Node *nd=root;
int v;
for(int i=1;i<=n;i++) gn(v), nd->ch[1]=new Node(v), nd=nd->ch[1];
nd->ch[1]=new Node(-INF), nd->ch[1]->sum=0;
splay(root,INF); // upd tag 概括如下：
在根节点构造一个虚点——这是维护区间必须的操作。
之后我们一直向右构建节点。
n 个节点构建完之后，再往右加一个虚点。
之后，把最后一个点旋到根。由于我们在加点的时候并没有更新节点的其它信息，所以我们必须要通过这个操作将树的所有节点状态更新到最新，不然可能影响后面的操作。
并且，这样构造时虽然没有更新节点的其它信息（比如子树大小），但是在短时间内并不影响排名的查询。所以不会影响到 splay 的操作。
构造一遍 O(n)，旋上来一遍 O(2n)，我们可以发现这么做时间复杂度并不差。
上方代码还有一些其它的细节，我们一会儿讲。
Insert Operation
至于插入操作，我们可以用同样的方法。
在 l 插入 tot 个节点，我们把 l - 1 旋到根，l 旋到根的右儿子。然后以 l 的左儿子为根，开始进行同样的构造。而且同样要更新所有点的信息。
之后我们再把 l 和 l - 1 都给 pushup 一下就行了。
void insert(int l,int tot) {
splay(root, l-1), splay(root->ch[1],1);
int v;
gn(v);
root->ch[1]->ch[0]=new Node(v);
Node *nd=root->ch[1]->ch[0];
for(int i=2;i<=tot;i++) gn(v),nd->ch[1]=new Node(v), nd=nd->ch[1];
splay(root->ch[1]->ch[0], INF); // upd tag
root->ch[1]->pup(), root->pup();
}Delete
由于本题的空间限制较为严格，因此我们得递归删除节点。
跟普通的删除一样。记得把根节点和根节点儿子都给 pushup。
namespace Delete {
void dfs(Node *x) {
if(x==nil) return;
Delete::dfs(x->ch[0]), Delete::dfs(x->ch[1]);
delete x;
}
void main(int l,int r) {
splay(root,l-1), splay(root->ch[1],r+2-l);
Delete::dfs(root->ch[1]->ch[0]);
root->ch[1]->ch[0]=nil;
root->ch[1]->pup(), root->pup(); // upd tag
}
}Reverse
翻转还是一样。
但跟求最大子序列搭配起来有一些变化。这个我们之后讲。
而且我们采取即使更新当个节点的策略，lazy 只用于更新下方节点，即与线段树相同。
Largest subsequence
重头戏来了。
我们先回想一下怎么用线段树求最大子序列。
使用 lx,rx,mx，分别代表当前区间前缀最大子序列和，后缀最大子序列和，和当前区间的最大子序列和。
我们采用分治的思想，得到如下的方程：
lx[x]=max(lx[ls],sum[ls]+lx[rs]);
rx[x]=max(rx[rs],sum[rs]+rx[ls]);
mx[x]=max(mx[lx],mx[rx],rx[ls]+lx[rs]);这个方程还有些细节。即如果这个区间的左（右）前缀序列最大和本来就低于 0 了，那我们就不选，即认为其等于 0。mx[x] 最小也得包含一个元素，那么如果全部小于 0 就选区间里的最大元素。
变成 splay 的话就是：
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
mx=max(ch[0]->mx,max(ch[1]->mx,ch[0]->rx+v+ch[1]->lx)); 我们稍作思考就发现，这个方程囊括了所有可能的情况。
其中之一如果 lx,rx 都等于 0，那么 mx 会等于这个区间的最大元素。
其它情况就不多说了。
初始情况也很容易想。这里我们将整个结构体的构造函数放上来：
Node (int val=0): v(val),s(1),c(1),sum(val),mx(val),t1(0),t2(0) {
ch[0]=ch[1]=nil;
if(val>=0) lx=rx=val;
else lx=rx=0;
}Pushup 操作的内容也水到渠成：
inline void pup() {
s=c+ch[0]->s+ch[1]->s;
sum=ch[0]->sum+v+ch[1]->sum;
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
mx=max(ch[0]->mx,max(ch[1]->mx,ch[0]->rx+v+ch[1]->lx));
} 但是这里还有一个问题：我们不是构造了哨兵节点和头尾的虚点吗？这几个点在 Pushup 上的影响该怎么避免？
我们先说哨兵节点。哨兵节点不应该对判断造成任何影响，以至于它应该被方程所有情况避免。那么将其 sum/ls/rs 置为 0，mx 置为 -INF 是个不错的选择。
那么头尾的虚点呢？头尾的虚点是可能做根节点的。因此我们这么做：v 置为 -INF，与此同时，如果它作为叶子节点，那么它的 mx 会被置为 -INF。如果不作为叶子节点，那么对于它方程等价于：
lx=ch[0]->lx;
rx=ch[1]->rx;
mx=max(ch[0]->mx,ch[1]->mx); 同时这两个点肯定代表着某个区间的末尾 / 开头。那么这些虚点的影响就消失了。
但是 sum 要置为 0.
此时构造哨兵节点的函数就出来了。
inline void clr() { ch[0]=ch[1]=nil, v=0, s=c=0, lx=rx=sum=t1=t2=0, mx=-INF; }
...
void init() {
nil=new Node(-INF);
nil->clr();
} 与此同时，由于翻转之后整个区间都反了过来，因此根节点的 lx 和 rx 也要交换。
翻转的函数变成如下：
void rev(int l,int r) {
splay(root,l-1), splay(root->ch[1],r+2-l);
Node *rt=root->ch[1]->ch[0];
if(rt->t1==-INF) return;
rt->t2^=1;
swap(rt->ch[0],rt->ch[1]), swap(rt->lx,rt->rx); // attention
root->ch[1]->pup(), root->pup(); // attention
}Modify
修改很简单。但是要给节点的 lx,rx,mx 更改，还是有点麻烦的。
void chg(int l,int r,int v) {
splay(root,l-1), splay(root->ch[1],r+2-l);
Node *rt=root->ch[1]->ch[0];
rt->v=v,rt->sum=rt->s*v;
if(v>=0) rt->lx=rt->rx=rt->mx=rt->sum;
else rt->lx=rt->rx=0, rt->mx=v; // attention
rt->t1=1;
root->ch[1]->pup(), root->pup();
}讲完 Modify 和 Reverse，那么 Pushdown 函数也就出来了。
inline void pud() {
if(t1) {
t1=t2=0; // 如果全部赋为同一个值就不用翻转了
_rg Node *l=ch[0],*r=ch[1];
l->t1=1, l->v=v, l->sum=l->s*v;
r->t1=1, r->v=v, r->sum=r->s*v;
if(v>=0) {
l->lx=l->rx=l->mx=l->sum;
r->lx=r->rx=r->mx=r->sum;
}
else {
l->lx=l->rx=0, l->mx=v;
r->lx=r->rx=0, r->mx=v;
}
}
if(t2) {
t2=0;
_rg Node *l=ch[0], *r=ch[1];
l->t2^=1, r->t2^=1;
swap(l->ch[0],l->ch[1]), swap(r->ch[0],r->ch[1]);
swap(l->lx,l->rx), swap(r->lx,r->rx); // attention
}
nil->clr(); // attention
}Query
查询操作我们不再解释。
Code
// Code by ajcxsu
// Problem: P2042
#include<bits/stdc++.h>
#define _rg register
#define INF (0x3f3f3f3f)
using namespace std;
int n,m;
inline int max(const int &x, const int &y) { return x>y?x:y; }
inline int min(const int &x, const int &y) { return x<y?x:y; }
inline void gn(int &x) {
x=0;
_rg int pl=1;
_rg char ch=getchar();
while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
x*=pl;
}
inline char gb() {
_rg char ch=getchar();
while(ch<'A' || ch>'Z') ch=getchar();
return ch;
}
/* splay */
struct Node *nil;
struct Node {
int v,s,c;
Node *ch[2];
int lx,rx,mx,sum;
bool t1,t2; // tag1 -> chg; tag2 -> rev
Node (int val=0): v(val),s(1),c(1),sum(val),mx(val),t1(0),t2(0) {
ch[0]=ch[1]=nil;
if(val>=0) lx=rx=val;
else lx=rx=0;
}
inline int cmp(int &k) {
if(k<=ch[0]->s) return 0;
else if(k<=ch[0]->s+c) return -1;
else { k-=ch[0]->s+c; return 1; }
}
inline void clr() { ch[0]=ch[1]=nil, v=0, s=c=0, lx=rx=sum=t1=t2=0, mx=-INF; }
inline void pud() {
if(t1) {
t1=t2=0;
_rg Node *l=ch[0],*r=ch[1];
l->t1=1, l->v=v, l->sum=l->s*v;
r->t1=1, r->v=v, r->sum=r->s*v;
if(v>=0) {
l->lx=l->rx=l->mx=l->sum;
r->lx=r->rx=r->mx=r->sum;
}
else {
l->lx=l->rx=0, l->mx=v;
r->lx=r->rx=0, r->mx=v;
}
}
if(t2) {
t2=0;
_rg Node *l=ch[0], *r=ch[1];
l->t2^=1, r->t2^=1;
swap(l->ch[0],l->ch[1]), swap(r->ch[0],r->ch[1]);
swap(l->lx,l->rx), swap(r->lx,r->rx);
}
nil->clr();
}
inline void pup() {
s=c+ch[0]->s+ch[1]->s;
sum=ch[0]->sum+v+ch[1]->sum;
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
mx=max(ch[0]->mx,max(ch[1]->mx,ch[0]->rx+v+ch[1]->lx));
}
} *root;
void init() {
nil=new Node(-INF);
nil->clr();
}
void rot(Node *&x, bool type) {
Node *t=x->ch[type];
x->ch[type]=t->ch[!type];
t->ch[!type]=x;
x->pup(), t->pup();
x=t;
}
void splay(Node *&x, int k) {
x->pud();
int d=x->cmp(k);
if(d!=-1 && x->ch[d]!=nil) {
Node *&y=x->ch[d];
y->pud();
int d2=y->cmp(k);
if(d2!=-1 && y->ch[d2]!=nil) {
splay(y->ch[d2], k);
if(d==d2) rot(x,d), rot(x,d);
else rot(y,d2), rot(x,d);
}
else rot(x,d);
}
}
void insert(int l,int tot) {
splay(root, l-1), splay(root->ch[1],1);
int v;
gn(v);
root->ch[1]->ch[0]=new Node(v);
Node *nd=root->ch[1]->ch[0];
for(int i=2;i<=tot;i++) gn(v),nd->ch[1]=new Node(v), nd=nd->ch[1];
splay(root->ch[1]->ch[0], INF); // upd tag
root->ch[1]->pup(), root->pup();
}
namespace Delete {
void dfs(Node *x) {
if(x==nil) return;
Delete::dfs(x->ch[0]), Delete::dfs(x->ch[1]);
delete x;
}
void main(int l,int r) {
splay(root,l-1), splay(root->ch[1],r+2-l);
Delete::dfs(root->ch[1]->ch[0]);
root->ch[1]->ch[0]=nil;
root->ch[1]->pup(), root->pup(); // upd tag
}
}
void rev(int l,int r) {
splay(root,l-1), splay(root->ch[1],r+2-l);
Node *rt=root->ch[1]->ch[0];
if(rt->t1==-INF) return;
rt->t2^=1;
swap(rt->ch[0],rt->ch[1]), swap(rt->lx,rt->rx); // attention
root->ch[1]->pup(), root->pup(); // attention
}
int gsum(int l,int r) {
splay(root,l-1), splay(root->ch[1],r+2-l);
return root->ch[1]->ch[0]->sum;
}
void chg(int l,int r,int v) {
splay(root,l-1), splay(root->ch[1],r+2-l);
Node *rt=root->ch[1]->ch[0];
rt->v=v,rt->sum=rt->s*v;
if(v>=0) rt->lx=rt->rx=rt->mx=rt->sum;
else rt->lx=rt->rx=0, rt->mx=v; // attention
rt->t1=1;
root->ch[1]->pup(), root->pup();
}
int main() {
init();
gn(n),gn(m);
/* Input */
root=new Node(-INF), root->sum=0;
Node *nd=root;
int v;
for(int i=1;i<=n;i++) gn(v), nd->ch[1]=new Node(v), nd=nd->ch[1];
nd->ch[1]=new Node(-INF), nd->ch[1]->sum=0;
splay(root,INF); // upd tag
/* Solve */
char opt[100];
int a,b,c;
while(m--) {
scanf("%s",opt);
if(opt[0]=='I') gn(a),gn(b),a+=2,insert(a,b);
else if(opt[0]=='D') gn(a),gn(b),a++,Delete::main(a,a+b-1);
else if(opt[0]=='R') gn(a),gn(b),a++,rev(a,a+b-1);
else if(opt[0]=='G') gn(a),gn(b),a++,printf("%d\n",gsum(a,a+b-1));
else if(opt[0]=='M'&& opt[2]=='K') gn(a),gn(b),gn(c),a++,chg(a,a+b-1,c);
else printf("%d\n",root->mx);
}
return 0;
}感谢 I_AM_HELLOWORLD 的题解 。
本文链接：https://pst.iorinn.moe/archives/fu-king_sol_luogu_2042.html
许可： https://pst.iorinn.moe/license.html若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆