「算法笔记」FHQ-Treap
$\text{FHQ-Treap}$ 是一种无旋 $\text{Treap}$,它不但能够兼容其他平衡树所涉及的问题,而且可以轻松地进行可持久化。
题目链接:BZOJ 1500
请写一个程序,要求维护一个数列。一共有 $m$ 个操作,支持以下 $6$ 种操作:
操作 | 输入格式 | 说明 |
---|---|---|
插入 | INSERT post tot c[1] c[2] ... c[tot] | 在当前数列的第 $pos$ 个数字后插入 $tot$ 个数字:$c_1,c_2,\cdots,c_{tot}$;若在数列首插入,则 $pos$ 为 $0$。 |
删除 | DELETE pos tot | 从当前数列的第 $pos$ 个数字开始连续删除 $tot$ 个数字。 |
修改 | MAKE-SAME pos tot c | 将当前数列的第 $pos$ 个数字开始的连续 $tot$ 个数字统一修改为 $c$。 |
翻转 | REVERSE pos tot | 取出从当前数列的第 $pos$ 个数字开始的 $tot$ 个数字,翻转后放入原来的位置。 |
求和 | GET-SUM pos tot | 计算从当前数列的第 $pos$ 个数字开始的 $tot$ 个数字的和并输出。 |
求和最大的子列 | MAX-SUM | 求出当前数列中和最大的一段非空子列,并输出最大和。 |
数据范围:$1\le m\le 2\times 10 ^ 4$,任何时刻数列中最多含有 $5\times 10 ^ 5$,数列中任何一个数字均在 $[-10^3,10^3]$,插入的数字总数不超过 $4\times 10 ^ 6$ 个。