可持久线段树简记
约 269 个字 预计阅读时间 1 分钟
P3747 [六省联考 2017] 相逢是问候¶
\[c^{a_i}modp = c^{a_imod\phi(p)+\phi(p)}modp\]
维护 \(a_imod\phi(p)\) 即可。
UOJ228¶
线段树加懒标记即可。 时间复杂度 \(O(n\log\log{v})\)。
P4198 楼房重建¶
线段树维护斜率，递归最大值分块。
李超线段树¶
1 合并¶
暴力递归两线段树同向子节点，若一方不存在则返回另一方节点值。
复杂度 \(O(n\log{n})\)。
2 可持久化¶
-
Path Copy : 复制路径信息，但对空间需求较大
-
Fat Node : 在节点上开 vector，查找需要二分
3 区间 kth¶
对序列建主席树，询问时在树上二分
4 树上路径 kth¶
P3293 美味¶
从高往低位枚举贪心，假设现在在第 \(i\) 位，已得到答案是 \(ans\)，希望知道
CF893F¶
\(k\) 限制了深度到一个区间。考虑到其只限制了上界，那么将矩阵 \(dep\) 拓展至 \(1- Side\)。
区间修改可持久化¶
对于定位到的区间打永久化标记（修改满足交换律）。