BZOJ1500 [NOI2005]维修数列 无旋Treap

发布于 2017-10-02  4.51k 次阅读


[toggle hide="yes" title="题目" color=""]

输入格式

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

 

输出格式

对于输入数据中的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

限制

每个测试点3s。

提示

[/toggle]

裸题,但是非常鬼畜,和线段树的“CPU监控”是同一程度的,都是要维护很多标记。

首先,先考虑要维护的标记:

ml:最大左缀和,mr:最大右缀和,ms:最大中缀和;

※本题要求最大连续和不能为空。

sum:区间和;

setv:区间修改标记;

rev:区间翻转标记。

接着,考虑标记的作用范围。如果只考虑区间修改操作,那么如果一个节点有setv标记,那么它的各项标记必须保证及时更新,同时子节点只打标记不更新信息。对于区间翻转操作,一旦有标记,则立即交换子节点并更新信息,而子节点同样只打标记不更新。对于修改,只要给根节点打上标记同时计算根节点信息,给子节点打上标记即可。考虑标记的下传:每次更新子节点信息(子节点已经有了标记),同时删除当前节点信息,因为只有要对子节点进行访问时才需下传,而我们又要求在进入子节点时能利用正确的信息,所以顺序非常重要。对于递归完成后重新计算当前节点,我们只需考虑子节点的贡献即可,直接利用子节点维护的信息更新。

一开始做这道题的时候,就是因为没弄清楚节点下传和更新信息的顺序,导致一些标记被清掉了,子节点记录的信息也不正确,调了很久很久。这也警示我,做题之前一定要想的非常清楚再动手,包括细节上的处理,尤其是数据结构题,否则只能在漫长的输出、调试中浪费时间。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974