NOI 2005 维护数列
一点题外话：
这个题忒折磨人了，我写了将近一天，两顿饭没吃。直到最后我下决心晚饭不吃我也要写出来才搞出来。写完后发现其实也不是很难，245行程序就搞定了。Splay真的不错，反正我是懒得学块状链表了。
————————————以下是题解——————————
这是NOI有史以来出过的最BT的数据结构题了，不少人写的都是块状链表，我来个Splay的（比起编程难度，其实朴素才是王道）。
建立一棵Splay，每个节点上要维护一下几个信息：数值value，子树大小size，子树和sum，子数内和最大的子数列 maxsum，子树区间内由左边界能够延伸的和最大子数列mls,子树区间内由右边界能够延伸的和最大子数列mrs，以及两个标记：子树反转标记rev，子树同化标记same。为了避免判断边界条件，首先插入两个节点，作为开头和结尾，其永久排名分别为1和当前数列长度。
插入和删除操作和NOI2003的文本编辑器类似。插入一段数列，把第pos+1个元素splay到根节点，，把第pos+2个元素 splay到根节点的右子树根节点，把要插入的这段数列建成一条链最好，然后把这个新建的链接到根节点右子树的左子树上，最后把链的尾splay到根节点。自底向上splay过程中要维护各项信息。
删除就是把第pos个元素splay到根节点，把第pos+tot+1个元素splay到根节点的右子树根节点，然后把根节点右子树的左子树直接砍掉就行了。由于数据规模比较大，如果内存比较紧张，要考虑回收空间。
考虑到修改和翻转的区间可能很大，暴力的肯定不行。取得区间的方法和删除一样，然后我们就用标记标识代表这个区间的这棵子树，今后访问到这这棵子树时，处理标记然后标记下传。具体来说，下传rev标记时，交换两个子树以及mls和mrs的值，然后两棵子树获得标记。下传same标记时，先把当前节点值传给子节点，维护节点的sum值为当前节点的value * size。然后如果当前节点值为非负数，令maxsum，mls，mrs的值为value * size，如果当前节点值为负数，令maxsum，mls，mrs的值为p->value。要注意的是，任何时候只要访问到带标记的节点，一定要标记下传，尤其不要忘了在splay旋转的时候。
另一个比较复杂的地方为自底向上维护节点信息，我们有size，sum，mls，mrs，maxsum五个信息需要同时维护。其中size，sum比较简单。
mls的取值有三种可能，直接继承与左子树的mls值，整个左子树的sum + 当前节点value，以及左子树的sum + 当前节点value + 右子树的mls，取三者最大值。mrs类似于mls。
maxsum的维护更为复杂，可能直接为当前节点value，继承左子树的maxsum，继承右子树的maxsum，左子树的mrs + 当前节点value，右子树的mls + 当前节点value，以及左子树的mrs + 右子树的mls + 当前节点value，这五种情况，同样取最大值。
有了上述的维护，求一段区间和也就不难了。同样的方法找到待求和区间，直接读取子树根节点的sum值即可。求和最大的子数列直接读取根节点的maxsum就行了。
看了zkw神牛的 《BST拓展与伸展树(splay)一日通》，没学会自顶向下的伸展树，倒学了不少代码技巧。例如建一个null节点，方便自底向上维护节点信息，还有空树不好操作，那就插入两个节点，作为开头和结尾。于是我的代码仅仅245行（4.89K），比起许多块状链表简单多了。
/*
* Problem: NOI2005 sequence
* Author: Guo Jiabao
* Time: 2009.5.30 14:19
* State: Solved
* Memo: 伸展树
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=2850003,MAXL=500001,INF=1001;
struct SplayTree
{
struct SplayNode
{
SplayNode *c[2],*f;
int value,size,sum,maxsum,mls,mrs;
bool rev,same;
}*root,*null,*lb,*rb,SS[MAXN];
int SC;
SplayNode * NewNode(int value,SplayNode *f)
{
SplayNode *e=SS+ ++SC;
e->value=value;
e->size=1;e->f=f;
e->sum=e->maxsum=e->mls=e->mrs=value;
e->same=e->rev=false;
e->c[0]=e->c[1]=null;
return e;
}
inline int max(int a,int b){return a>b?a:b;}
void update(SplayNode *p)
{
if (p==null) return;
p->size = p->c[0]->size + p->c[1]->size + 1;
p->sum = p->c[0]->sum + p->c[1]->sum + p->value;
p->mls = p->c[0]->mls;
p->mls = max( p->mls , p->c[0]->sum + p->value);
p->mls = max( p->mls , p->c[0]->sum + p->value + p->c[1]->mls );
p->mrs = p->c[1]->mrs;
p->mrs = max( p->mrs , p->c[1]->sum + p->value);
p->mrs = max( p->mrs , p->c[1]->sum + p->value + p->c[0]->mrs );
p->maxsum = p->value;
p->maxsum = max( p->maxsum , p->c[0]->maxsum );
p->maxsum = max( p->maxsum , p->c[1]->maxsum );
p->maxsum = max( p->maxsum , p->c[0]->mrs + p->value );
p->maxsum = max( p->maxsum , p->c[1]->mls + p->value );
p->maxsum = max( p->maxsum , p->c[0]->mrs + p->c[1]->mls + p->value );
}
void pushdown(SplayNode *p)
{
if (p==null) return;
if (p->rev)
{
p->rev=false;
SplayNode *q=p->c[0]; p->c[0]=p->c[1]; p->c[1]=q;
p->c[0]->rev = !p->c[0]->rev;
p->c[1]->rev = !p->c[1]->rev;
int t=p->mls;
p->mls=p->mrs; p->mrs=t;
}
if (p->same)
{
p->same=false;
p->c[0]->same=p->c[1]->same=true;
p->c[0]->value=p->c[1]->value=p->value;
p->sum = p->maxsum = p->mls = p->mrs = p->value * p->size;
if (p->value < 0)
p->maxsum = p->mls = p->mrs = p->value;
}
}
void rotate(SplayNode *x,int o)//Zig o=0 Zag o=1
{
SplayNode *y=x->f;
pushdown(x->c[0]);
pushdown(x->c[1]);
pushdown(y->c[!o]);
y->c[o] = x->c[!o];
y->c[o]->f=y;
x->f = y->f;
if (y->f->c[0]==y)
y->f->c[0]=x;
else
y->f->c[1]=x;
y->f=x;
x->c[!o]=y;
update(y);
update(x);
if (root==y) root=x;
}
void splay(SplayNode *x,SplayNode *y)
{
pushdown(x);
while (x->f!=y)
{
if (x->f->f==y)
{
if (x->f->c[0]==x)
rotate(x,0);
else
rotate(x,1);
}
else if (x->f->f->c[0] == x->f)
{
if (x->f->c[0]==x)
rotate(x->f,0),rotate(x,0);
else
rotate(x,1),rotate(x,0);
}
else
{
if (x->f->c[1]==x)
rotate(x->f,1),rotate(x,1);
else
rotate(x,0),rotate(x,1);
}
}
}
void select(int k,SplayNode *y)
{
SplayNode *x=root;
pushdown(x);
for (;k != x->c[0]->size + 1;)
{
if (k <= x->c[0]->size)
x=x->c[0];
else
{
k-=x->c[0]->size + 1;
x=x->c[1];
}
pushdown(x);
}
splay(x,y);
}
void Insert(int pos,int tot,int *C)
{
SplayNode *z,*t;
z=t=NewNode(C[1],null);
for (int i=2;i<=tot;i++)
z=z->c[1]=NewNode(C[i],z);
select(pos+1,null);
select(pos+2,root);
root->c[1]->c[0] = t;
t->f=root->c[1];
splay(z,null);
}
void Delete(int pos,int tot)
{
select(pos,null);
select(pos+tot+1,root);
root->c[1]->c[0] = null;
splay(root->c[1],null);
}
void MakeSame(int pos,int tot,int value)
{
select(pos,null);
select(pos+tot+1,root);
root->c[1]->c[0]->same=true;
root->c[1]->c[0]->value=value;
splay(root->c[1]->c[0],null);
}
void Reverse(int pos,int tot)
{
select(pos,null);
select(pos+tot+1,root);
root->c[1]->c[0]->rev=!root->c[1]->c[0]->rev;
splay(root->c[1]->c[0],null);
}
int GetSum(int pos,int tot)
{
select(pos,null);
select(pos+tot+1,root);
pushdown(root->c[1]->c[0]);
return root->c[1]->c[0]->sum;
}
int MaxSum()
{
pushdown(root);
update(root);
return root->maxsum;
}
void init()
{
SC=-1;
null=0;
null=NewNode(-INF,0);
null->size=0;
lb=root=NewNode(-INF,null);
rb=root->c[1]=NewNode(-INF,root);
null->sum = lb->sum = rb->sum=0;
update(root);
}
}Splay;
int N,M,C[MAXL],pos,i,j,A;
char Ctrl[20];
int main()
{
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
Splay.init();
scanf("%d%d",&N,&M);
for (i=1;i<=N;i++)
scanf("%d",&C[i]);
Splay.Insert(0,N,C);
for (i=1;i<=M;i++)
{
scanf("%s",Ctrl);
switch (Ctrl[0])
{
case 'I':
scanf("%d%d",&pos,&N);
for (j=1;j<=N;j++)
scanf("%d",&C[j]);
Splay.Insert(pos,N,C);
break;
case 'D':
scanf("%d%d",&pos,&N);
Splay.Delete(pos,N);
break;
case 'R':
scanf("%d%d",&pos,&N);
Splay.Reverse(pos,N);
break;
case 'G':
scanf("%d%d",&pos,&N);
A=Splay.GetSum(pos,N);
printf("%d\n",A);
break;
case 'M':
if (Ctrl[2]=='K')
{
scanf("%d%d%d",&pos,&N,&C[0]);
Splay.MakeSame(pos,N,C[0]);
}
else
printf("%d\n",Splay.MaxSum());
break;
}
}
return 0;
}
<h2><span class="mw-headline">维护数列 </span></h2>
【问题描述】
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
<table border="1" cellspacing="0" cellpadding="0">
<tbody>
<tr>
<td width="91" valign="top">操作编号</td>
<td width="217" valign="top">输入文件中的格式</td>
<td width="276" valign="top">
<p align="center">说明</p>
</td>
</tr>
<tr>
<td width="91" valign="top">
1. 插入</td>
<td width="217" valign="top">
<span lang="EN-US">INSERT_<em>posi</em>_<em>tot</em>_<em>c</em>1_<em>c</em>2_..._<em>c</em></span><em><span lang="EN-US">tot</span></em></td>
<td width="276" valign="top"><span lang="EN-US">在当前数列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">个数字后插入 </span><em><span lang="EN-US">tot</span></em>
<span lang="EN-US">个数字：</span><em><span lang="EN-US">c</span></em><span lang="EN-US">1, <em>c</em>2, …, <em>c</em></span><em><span lang="EN-US">tot</span></em><span lang="EN-US">；若在数列首插</span>
<span lang="EN-US">入，则 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">为 0</span></td>
</tr>
<tr>
<td width="91" valign="top">2. 删除</td>
<td width="217" valign="top">
DELETE_<em>posi</em>_<em>tot</em></td>
<td width="276" valign="top"><span lang="EN-US">从当前数列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">个数字开始连续</span>
<span lang="EN-US">删除 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">个数字</span></td>
</tr>
<tr>
<td width="91" valign="top">3. 修改</td>
<td width="217" valign="top">
MAKE-SAME_<em>posi</em>_<em>tot</em>_<em>c</em></td>
<td width="276" valign="top"><span lang="EN-US">将当前数列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">个数字开始的连</span>
<span lang="EN-US">续 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">个数字统一修改为 </span><em><span lang="EN-US">c</span></em></td>
</tr>
<tr>
<td width="91" valign="top">4. 翻转</td>
<td width="217" valign="top">
REVERSE_<em>posi</em>_<em>tot</em></td>
<td width="276" valign="top"><span lang="EN-US">取出从当前数列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">个数字开始</span>
<span lang="EN-US">的 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">个数字，翻转后放入原来的位置</span></td>
</tr>
<tr>
<td width="91" valign="top">5. 求和</td>
<td width="217" valign="top">
GET-SUM_<em>posi</em>_<em>tot</em></td>
<td width="276" valign="top"><span lang="EN-US">计算从当前数列开始的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">个数字</span>
<span lang="EN-US">开始的 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">个数字的和并输出</span></td>
</tr>
<tr>
<td width="91" valign="top">6. 求和最
大的子列</td>
<td width="217" valign="top">
MAX-SUM</td>
<td width="276" valign="top">求出当前数列中和最大的一段子列，
并输出最大和</td>
</tr>
</tbody></table>
【输入格式】
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第 2 行包含 N 个数字，描述初始时的数列。
以下 M 行，每行一条命令，格式参见问题描述中的表格。
【输出格式】
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。
【输入样例】
<pre>9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM</pre>
【输出样例】
<pre>-1
10
1
10</pre>
【样例说明】
初始时，我们拥有数列 2 -6 3 5 1 -5 -3 6 3
执行操作 GET-SUM 5 4，表示求出数列中从第 5 个数开始连续 4 个数字之和，1+(-5)+(-3)+6 = -1：
<pre>2 -6 3 5 1 -5 -3 6 3</pre>
执行操作 MAX-SUM，表示要求求出当前数列中最大的一段和，应为 3+5+1+(-5)+(-3)+6+3 = 10：
<pre>2 -6 3 5 1 -5 -3 6 3</pre>
执行操作 INSERT 8 3 -5 7 2，即在数列中第 8 个数字后插入-5 7 2，
<pre>2 -6 3 5 1 -5 -3 6 -5 7 2 3</pre>
执行操作 DELETE 12 1，表示删除第 12 个数字，即最后一个：
<pre>2 -6 3 5 1 -5 -3 6 -5 7 2</pre>
执行操作 MAKE-SAME 3 3 2，表示从第 3 个数开始的 3 个数字，统一修改为 2：
<pre>2 -6 3 5 1 -5 -3 6 -5 7 2</pre>
改为
<pre>2 -6 2 2 2 -5 -3 6 -5 7 2</pre>
执行操作 REVERSE 3 6，表示取出数列中从第 3 个数开始的连续 6 个数：
<pre>2 -6 2 2 2 -5 -3 6 -5 7 2</pre>
如上所示的灰色部分 2 2 2 -5 -3 6，翻转后得到 6 -3 -5 2 2 2，并放回原来位置：
<pre>2 -6 6 -3 -5 2 2 2 -5 7 2</pre>
最后执行 GET-SUM 5 4 和 MAX-SUM，不难得到答案 1 和 10。
<pre>2 -6 6 -3 -5 2 2 2 -5 7 2</pre>
【评分方法】
本题设有部分分，对于每一个测试点：
-
如果你的程序能在输出文件正确的位置上打印 GET-SUM 操作的答案，你可以得到该测试点 60%的分数；
-
如果你的程序能在输出文件正确的位置上打印 MAX-SUM 操作的答案，你可以得到该测试点 40%的分数；
-
以上两条的分数可以叠加，即如果你的程序正确输出所有 GET-SUM 和MAX-SUM 操作的答案，你可以得到该测试点 100%的分数。
请注意：如果你的程序只能正确处理某一种操作，请确定在输出文件正确的位置上打印结果，即必须为另一种操作留下对应的行，否则我们不保证可以正确评分。
【数据规模和约定】
-
你可以认为在任何时刻，数列中至少有 1 个数。
-
输入数据一定是正确的，即指定位置的数在数列中一定存在。
-
50%的数据中，任何时刻数列中最多含有 30 000 个数；
-
100%的数据中，任何时刻数列中最多含有 500 000 个数。
-
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
-
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 个，输入文件大小不超过 20MBytes。
上次修改时间 2017-05-22