Beyond the Void
BYVoid
NOI 2005 维护数列

一点题外话:

这个题忒折磨人了,我写了将近一天,两顿饭没吃。直到最后我下决心晚饭不吃我也要写出来才搞出来。写完后发现其实也不是很难,245行程序就搞定了。Splay真的不错,反正我是懒得学块状链表了。

sequence

————————————以下是题解——————————

这是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

相关日志