区间函数复合

yangzichen1203 · 2026-08-03 16:25:24 · 算法·理论

终于弄懂 ULR3F 了，写点文章。

前置知识

平衡树有交合并

https://www.luogu.com.cn/problem/P5494

:::success[Solution] 平衡树有交合并模板。

合并两棵平衡树时，若值域不交则直接合并，否则将小的平衡树分成左右子树，大的平衡树按小平衡树根的值分裂，对左右递归进行有交合并。

注意需要合并权值相同的节点，用并查集维护。

如果没有分裂操作，可以证明用 FHQ-Treap 和 WBLT 实现的时间复杂度都是 1log 的。

如果有分裂操作，则可以证明都是 2log 的。

如果不加值域不交的剪枝，FHQ-Treap 会被卡到 3log。

证明和 hack 见 https://www.luogu.com.cn/article/p4ejw9j6 和 wc2026-ds-lhx.pdf。

平衡树带分裂有交合并还存在 1log 做法，见 https://arxiv.org/pdf/1901.00718 。 :::

序列区间复制

https://www.luogu.com.cn/problem/P8263

:::success[Solution] 序列区间复制模板。

用可持久化平衡树维护，利用倍增进行多次区间复制即可。

用 FHQ-Treap 只能 O(\log n) 合并，但由于倍增时合并的平衡树大小相同，用 WBLT 能 O(1) 合并。

用 WBLT 的时空复杂度最优取到 1log，而用 FHQ-Treap 节点优先级随机顺序被破坏，时间复杂度应该介于 2log 到平方之间。 :::

正文

总结

一般来说，如果题目允许离线，用平衡树带分裂有交合并；如果强制在线，用可持久化平衡树区间复制。

时间复杂度都能做到 2log 甚至 1log。

1

https://www.luogu.com.cn/problem/P11622

:::success[Solution] 离线。

对序列扫描线，在 l 位置插入元素，在 r+1 位置取出元素。

维护一棵平衡树，维护分裂，加，取反，翻转，有交合并等操作即可。

时间复杂度 2log，用上文科技可能可以优化到 1log。

但看不懂论文怎么办？ :::

2

https://www.luogu.com.cn/problem/P8264

:::success[Solution] 强制在线。

先考虑一个子问题，r=n 时怎么做？

从右到左加入函数，函数显然满足多对一的性质，则每一次加入函数都是一对多，即区间复制。

对序列建线段树，每一条线段都从右到左维护复合函数，则可以 2log 预处理，2log 查询了。

注意初始需要得到 [0,V]\to[0,V] 的平衡树，也用倍增预处理。

这个算法存在很大浪费，对于 i\in[l,r]，我们维护了每一个 [i,r]，但只查询了 [l,r] 的答案。

所以考虑猫树分治，中点左侧用区间复制，中点右侧用有交合并，即可 2log 预处理，1log 查询。

同时 https://www.luogu.com.cn/article/f0dmp472 给出了很多卡常方法。

时间复杂度很难优化了。

真的吗? :::

3

https://www.luogu.com.cn/problem/P11692

https://uoj.ac/contest/96/problem/960

:::success[Solution] 2log 预处理，1log 查询做法同 2。

注意到每次有效取模会使值减半，所以我们维护下一次有效取模的位置，最多跳转 1log 次。

从右到左扫描线，每次对有效取模的值域赋值为当前位置，再进行区间复制变换到下一位置。

预处理做到了 1log，但是需要进入平衡树根部 1log 次，查询变成 2log 了。

对于一次跳转，其代表的区间大小一定不变，对目标平衡树进行分裂，原节点指向分裂出的节点。

由于目标区间只有 [0,a_i-1] 的一段前缀、全部、一段后缀，所以预处理可以做到 1log。

每次经过原平衡树边时对应值域大小都会减小 O(1) 倍，而最多进行 1log 次跳转，则可以 1log 查询。

预处理 1log，查询 1log。 :::

4

https://uoj.ac/contest/103/problem/1017

:::success[Solution] 区间函数复合的最优做法。