专栏文章

题解：P10284 [USACO24OPEN] Splitting Haybales P

tty_mxzhn
P10284题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqowmzu
此快照首次捕获于
2025/12/04 08:20
3 个月前
此快照最后确认于
2025/12/04 08:20
3 个月前
查看原文

插入标记回收算法

本算法在 lxl 讲课时提出。然后立马就被放到了数据结构专场的签到题。
解决的问题是：
qq 次询问 xx 依次经过 r−l+1r-l+1 种操作的结果。
第 ii 种操作是 x←Fi(x)x\leftarrow F_i(x) 这样。可以离线。
算法流程如下：
  1. 插入数据。在 ll 时间开始前把 xx 加入集合 SS 中。
  2. 标记。在 ii 时间执行 S←Fi(S)S\leftarrow F_i(S)。
  3. 回收数据。在 r+1r+1 时间开始前把 ll 丢进去的数据从 SS 中回收。
难得 lxl 讲这么简单的算法。

例题 11

PKUSC 的题（澡堂）：Fi(x)=x+[x∈[li,ri]]F_i(x)=x+[x\in[l_i,r_i]]。
显然 SS 中节点保持单调顺序。直接用线段树二分定位线段树区间加即可。时间复杂度 O(nlog⁡n)O(n\log n)。

平衡树合并技巧

平衡树合并是在没有一些奇怪操作的 FHQ-Treap 上的合并两颗不需要满足任何条件的 FHQ-Treap 的方法。

一个暴力

假设我们要从 yy 合并到 xx，启发式后直接一个一个合并。
然而这样复杂度是错的，因为我们可以不断分裂合并。

一个暴力？

直接按照 xx 的键值分裂 yy。然后把 yy 的两边放到 xx 的两边递归合并。
需要注意的是要求 Px>PyP_x>P_y 也就是按照优先级决定谁合并谁。其实理论上按照大小合并会更优但是其实差不多。

复杂度证明

假设 n,qn,q 同阶。上述“暴力”的时间复杂度为 O(nlog⁡nlog⁡V)O(n\log n\log V)。
证明考虑设计势能函数 ϵ(x)\epsilon(x) 表示 xx 内部相邻两点的值域差对数的和。
设值域连续段有 cc 个，这里的连续段指的是合并 A,BA,B 两颗平衡时后新树的值总是成 A..B..A..B..A..B..A..B..A..B..A..B..A..B..A..B.. 这样。则 c=8c=8。
合并时有值域连续段内总有 O(c)O(c) 个节点的势能减少 11。而上述“暴力”的复杂度最高只有 O(clog⁡n)O(c\log n)。
显然分裂不增加势能。

友情提示

例题 22

例题：Ynoi TEST_100。
用刚才两个算法。则相当于对 aia_i 的大小关系分讨后使用平衡树合并在一起。
并不是这样的，因为强制在线限制了第一个算法。
考虑分块。因为值域很小所以我们可以每一段内暴力平衡树合并跑出 1∼V1\sim V 的答案。
查询时散块暴力，跳整块直接用刚才平衡树合并时跑出来的结果即可。
n,q,Vn,q,V 同阶。时间复杂度 O(nn+nlog⁡2n)O(n\sqrt{n}+n\log^2n)。

例题 33

例题：Splitting Haybals P。
用刚才提到的两个算法。插入标记回收以后，按照 00 分裂以后分别打加法标记并合并。
n,qn,q 同阶。时间复杂度 O(nlog⁡nlog⁡V)O(n\log n\log V)。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...