OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【NOI2005】维修数列

【题目描述】

请写一个程序,要求维护一个数列,支持以下6种操作:(请注意,格式栏中的下划线‘ _ ’表示实际输入文件中的空格)


【输入】

第1行包含两个数N和M,N表示初始时数列中数的个数,M表示要进行的操作数目。

第2行包含N个数字,描述初始时的数列。

以下M行,每行一条命令,格式参见问题描述中的表格。

【输出】

对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行。

【输入样例】

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

【输出样例】

-1

10

1

10

【数据范围】

你可以认为在任何时刻,数列中至少有1个数。
输入数据一定是正确的,即指定位置的数在数列中一定存在。
50%的数据中,任何时刻数列中最多含有30 000个数;
100%的数据中,任何时刻数列中最多含有500 000个数。
100%的数据中,任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中,M ≤20 000,插入的数字总数不超过4 000 000个,大小不超过20MBytes。

【题解】

这傻题竟然做了那么久,我是不是没救了……

史上最强Splay模板题,除了MAX-SUM其他都是常规操作,使劲码就行,可以参考前几道平衡树的相关操作。

对于MAX-SUM操作,我们维护以每个节点为根的子树中最左端和最右端的最大连续和以及整个序列的最大连续和。合并时,最左端最大连续和可以是左子树的最左端最大连续和,整个左子树加上该节点值,整个左子树加上该节点值再加上右子树的最左端最大连续和,最右端最大连续和类似。最大连续和可以是左子树最大连续和、右子树最大连续和、该节点值、该节点值加上左子树/右子树的最右端/最左端最大连续和(可以都加上)。

然后就没什么难点了,注意下放标记时交换最右端/最左端最大连续和。

PS.这道题节点数最多有400w,明显空间不足,但注意到任何时刻数列中最多含有50w个数,所以可以回收空间,用一个栈存储没有用过的节点,每次删除时把删除的节点都加进去(这并不会超时,因为最多删除400w个节点),这样就能解决了~

【代码】

没事儿的时候可以把这题当模板练练,再不练我真的没救了QAQ

http://paste.ubuntu.com/10760323/

评论

© OI技术宅 | Powered by LOFTER