题解：P10284 [USACO24OPEN] Splitting Haybales P
ty_mxzhn
·
·
题解
插入标记回收算法
本算法在 lxl 讲课时提出。然后立马就被放到了数据结构专场的签到题。
解决的问题是：
第 $i$ 种操作是 $x\leftarrow F_i(x)$ 这样。可以离线。
算法流程如下：
1. 插入数据。在 $l$ 时间开始前把 $x$ 加入集合 $S$ 中。
2. 标记。在 $i$ 时间执行 $S\leftarrow F_i(S)$。
3. 回收数据。在 $r+1$ 时间开始前把 $l$ 丢进去的数据从 $S$ 中回收。
难得 lxl 讲这么简单的算法。
## 例题 $1
PKUSC 的题（澡堂）：F_i(x)=x+[x\in[l_i,r_i]]。
显然 S 中节点保持单调顺序。直接用线段树二分定位线段树区间加即可。时间复杂度 O(n\log n)。
平衡树合并技巧
平衡树合并是在没有一些奇怪操作的 FHQ-Treap 上的合并两颗不需要满足任何条件的 FHQ-Treap 的方法。
一个暴力
假设我们要从 y 合并到 x，启发式后直接一个一个合并。
然而这样复杂度是错的，因为我们可以不断分裂合并。
一个暴力？
直接按照 x 的键值分裂 y。然后把 y 的两边放到 x 的两边递归合并。
需要注意的是要求 P_x>P_y 也就是按照优先级决定谁合并谁。其实理论上按照大小合并会更优但是其实差不多。
复杂度证明
假设 n,q 同阶。上述“暴力”的时间复杂度为 O(n\log n\log V)。
证明考虑设计势能函数 \epsilon(x) 表示 x 内部相邻两点的值域差对数的和。
设值域连续段有 c 个，这里的连续段指的是合并 A,B 两颗平衡时后新树的值总是成 A..B..A..B..A..B..A..B.. 这样。则 c=8。
合并时有值域连续段内总有 O(c) 个节点的势能减少 1。而上述“暴力”的复杂度最高只有 O(c\log n)。
显然分裂不增加势能。
友情提示
例题 2
例题：Ynoi TEST_100。
用刚才两个算法。则相当于对 a_i 的大小关系分讨后使用平衡树合并在一起。
并不是这样的，因为强制在线限制了第一个算法。
考虑分块。因为值域很小所以我们可以每一段内暴力平衡树合并跑出 1\sim V 的答案。
查询时散块暴力，跳整块直接用刚才平衡树合并时跑出来的结果即可。
## 例题 $3
例题：Splitting Haybals P。
用刚才提到的两个算法。插入标记回收以后，按照 0 分裂以后分别打加法标记并合并。