关于一个平衡树相关的问题

zx2003 · 2021-07-02 23:00:21 · 个人记录

要求维护若干个递增整数序列，要求支持 1.对于一个序列a，给定权值k，将a切成小于k和大于等于k的两个序列 2.将一个序列中所有元素加等于常数 3.将一个序列中所有元素取相反数，并反转整个序列 4.将两个序列归并为一个

做法： 考虑用平衡树+懒标记维护每个序列，操作1直接分裂即可，操作2,3直接打标记即可。而操作4可以用平衡树合并来实现，精细实现可以使得每次折叠的复杂度为 O(段数\log)。考虑证明这样复杂度是对的。

定义势能函数为在同一棵平衡树中，每一个元素 x， 到相邻两个 x 之间的距离取对数之后的和，那么一旦多出一段就代表一个 x_m 折叠后插入到了原本相邻的 x_l 和 x_r 之间，那么本来势能函数中原本 x_l 到 x_r 的贡献会被拆成 x_l 到 x_m 和 x_m 到 x_r，那么 “x_l 到它右边的点的距离“ 和 ”x_r 到它左边的点的距离“ 这两个东西中必然有一个会变成原来的一半，也就是说每多出一段要合并时势能函数必然会至少减一（特别地，若 x_m=x_l 或 x_r，则这样的合并最多只有 n 次，不会产生影响）。在中途加入一个 x 也并不影响势能函数的分析，故总复杂度为 O(q \log^2)。