首页 > 题解 > bzoj 1500 [NOI2005]维修数列

bzoj 1500 [NOI2005]维修数列

恶心题

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。
第2行包含N个数字,描述初始时的数列。
以下M行,每行一条命令,格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个,输入文件大小不超过20MBytes。

Output

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

Sample Input

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

Sample Output

-1
10
1
10

恶心Treap/Splay模版题。。

前几个操作都很好搞,最后一个的话每一个节点维护一个最大子段和,和从左右子段最大,这样就可以愉快的合并了。

一个else卡了我一天


2 COMMENTS

  1. radish2018-05-03 下午9:09

    大佬您好,我想问一下lmx和rmx分别表示什么呢 谢谢

    • 远航之曲2018-05-03 下午9:29

      严格从左开始的最大子段和和严格从右开始的。。

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×