Dfs序
CF383C
- 简化：子树加， 子树和（线段树 + Dfs 序）
- 考虑对树做一个奇偶的分层
- x 的深度为奇数， x 子树中， 深度为奇数 + ， 深度为偶数 -
BZOJ3306
-
小技巧：换根， Dfs序
-
现在的根为 x， 原来的为 rt
- y 在 x 的子树内 -> 无影响
- y 在 x 到根路径上 -> 影响
- 其他无影响
-
if (Lca(x, y) == y)
- 找到离 y 最近的一点 z （x， y 之间）
- 刨去 z 的子树， 询问剩下所有点的最小值
-
分类讨论
-
P3128
- 树上差分
- x 到根的和 + y 到根的和 - Lca 到根的和 - Lca 的父亲到根的和
x++, y++, Lca--, fa[Lca]--
P2680
- 最晚完成的工作完成的最早时刻
- 二分
- 找出所有 > mid 的计划， 修改的边一定在 (x, y) 路径上 （公共边）
- 树上差分找公共边
- 边权最大的改成虫洞
P4216
- 一个 log
- 询问：(x, y) 上有多少大于 c 的
- i - c 时刻， 有多少 > 0 的点 （打个标记就行）
- 操作变为（离线）
- val 0-> 1
- 路径上 1 的个数（路径和）
- f[x] ：x 到根路径的和（子树加问题）
- Dfs序， 区间加， 单点查（线段树）
- 子树 [l] + 1, [r + 1] - 1 （树状数组）
- 如果强制在线
- 主席树（维护历史版本）
P5838
-
(x, y) 有多少 = c
-
‘和’ 可以差分
-
求点到根路径上有多少个 c
-
离线
-
同时处理同一个 c 的
-
-
时间复杂度
- 修改 总共 \(O(n)\) （均摊）
- 询问 总共\(O(m log n)\)
-
题解lzyqwq 树剖
HDU 5692
- 转化为以 0 为根， 查询 x 子树内到根路径的最大值
P4211
l, r 如何转化
l -> r 按 Dfn 排序， 找有多少点在 z 的子树内， 有多少在 z -> 0 的路径上， 有多少不和 z 在同一子树
- dep = dep[z]
- dep = dep[x]
- dep = dep[0]
Lca 都在 (z, 0) 上
- z 到 [1, r] 的 Lca_dep 和， 到[1, l - 1] 的 Lca_dep 和
- 维护集合（修改 n 次)
- 插入
- z 与集合中 Lca_dep 和
- 集合点 x
- x 到 0 路径 + 1
- z 到根的路径和 等价于 Lca 的 dep
- 树链剖分
- k 次方 [P5305 GXOI/GZOI2019] 旧词 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
CF696E
输出排名
- 先找最大/小的， 删掉， 重复 k 次
- 路径信息无法差分, 子树加 -> 树剖
- 维护路径min, 子树加
- 每个节点可能有多个物品, 维护 vector, 删除后找一个次大的挂上去
P4219
-
负载: x 这边的点数 * y 这边的
-
在线不好做
- 离线
-
边权 0->不连通, 1->联通
- 加边:一条边的权从 0 改成 1
-
然后?
CF536E
需要把所有 0/1 都求出来吗
-
树剖作用:路经查询 -> 区间查询
-
按 l 排序
- 单点修改,
- 然后
//下午
可持久化数据结构
- 每次操作是一个新的时刻
- 可查询 i 时刻的信息
- 暴力方法: 把线段树复制一遍, 在新的上面修改 $ O(n) $
- 单点修改只影响 log n 个节点, 只新建这些, 原来的不动 -> 路径复制 (一种可持久化方法)
- 查询, 修改 $ O(log n) $
- 空间 $ O(n log n) $
- 区间修改
- 标记下放 -> 把父亲和儿子都复制一遍, 在新节点上下放
- 标记永久化
P3834
- 离散化, 动态开点 用其中一个即可
- 给定区间, 查 < x 的数的个数?
- [l, r] -> [1, r] - [1, l - 1]
- 类似于差分
- 方法一 : 二分答案 $ O(n log ^ 2 n) $
- 方法二 : 和线段树一起二分(每次舍去一半的区间)
- 原理: 两颗线段树对应节点表示的值域相同
P4592
子树问题, 可持久化 01Trie ?
Dfn, 1 棵可持久化 01Trie (1 - n 个时刻), 树剖
- opt 1
- Dfs 序, 转化成区间 [l, r] 与 z 的最大异或
- 可持久化 01Trie, 1 - n 个时刻(和主席树一样)
- $ O(log 值域) $
- opt 2
- 路径: 树上差分
- 树上主席树
- 维护节点到根的可持久化 01Trie, 子节点的上一个版本是自己的父亲
- + x到根 + y到根 - Lca到根 - Lca的父亲到根
- 在四颗树上一起二分
P3567
其他思路: 找区间中位数, 查询其次数, 如果小于一半, 那就不存在绝对众数, 否则答案是他?
-
可持久化值域线段树
-
在线段树上二分找出现次数 > 一半的区间, 直到递归到叶子, 否则无答案
-
其他:摩尔投票, 随机化...
P2839
最大中位数, 端点取值范围 ??
好像不可以对中位数的值或者端点二分, 没有单调性
- 二分一个中位数 mid, 验证
- 把 > mid 的标记为 1, < 的标为 - 1
- mid 从小变大， 序列中的数 1 -> -1
- 预处理出 mid = 1 -> n
- 可持久化线段树
- 找一个区间, 使得和 >= 0
- 把 > mid 的标记为 1, < 的标为 - 1
- 转化为: 求出一个和最大的区间
- [b + 1, c - 1] 必选
- [a, b] 的后缀最大值, [c, d] 的前缀最小值
- 怎么求
CF464E
- 图论（最短路） + 数据结构
- \(dis[y] = dis[x] + 2 ^ v\)
- 用数据结构维护dis (值域线段树)
- dis -> 两个 01 串比大小， 找最长公共前缀， 比较前缀的后一位
- 二分哈希 线段树维护 $O(log n) $
- 两个线段树结构相同
- 可持久化， y 的历史版本是 x
- 修改 ？
- 复制一份， \(+ 2 ^ v\)
- 相当于在 v 单点修改
- 如何解决进位问题 ？
- 暴力进位的复杂度不对
- 二分极长的 1 的连续段的开头 或 线段树维护最靠右的 0 的位置
- 修改 $ O(log n) $ ， 比大小一样
- Dij 带个 log
P3402
- 部分持久化：只查询历史版本， 不对其进行修改（主席树板子）
- 完全持久化：对历史版本做修改， 得到多个新版本（上一题dis， 本题）
- 如果不路径压缩：查询复杂度 $ O(n) \(, 每次返回历史：\)O(n ^ 2) $
- 带均摊的数据结构不好访问历史版本， 可以卡
- 按秩合并
- 按 si， dep 等
- si[x] > si[y], fa[y] = x
- 2 * si[y] < si[x] + si[y], 最多向上走 log 步
- 可持久化数组 + 按秩合并
P3302
启发式合并
- 树上主席树
- 维护 x - > 根的路径权值
- （线段树合并是均摊复杂度？）用不了
- 启发式合并
- 以 si 较大的树的根为根
- 重建较小树的主席树 $ O(n log ^ 2 n) $
- 细节
- 合并 Lca：启发式合并维护倍增表
Loj 6144
怎么维护 或 的最值
直接分别建一颗主席树， 一颗 01Trie ？
- 异或：trie 的左右子树互换
- 与， 或：具有破坏性
- 使 trie 的分支减少
- 均摊：log 位， 暴力重构， $O(n log ^ 2 n) $