2020-2021:teams:intrepidsword:2020.06.05-2020.06.11_周报
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020.06.05-2020.06.11_周报 [2020/06/13 01:08] chielo [jsh] |
2020-2021:teams:intrepidsword:2020.06.05-2020.06.11_周报 [2020/06/13 01:11] (当前版本) chielo [jsh] |
||
|---|---|---|---|
| 行 86: | 行 86: | ||
| 记当前 DFS 到的节点为 $u$，维护的线段树为 $A_u$，包括根，已经合并完的总节点集合为 $S_u$，数量为 $s_u$。 | 记当前 DFS 到的节点为 $u$，维护的线段树为 $A_u$，包括根，已经合并完的总节点集合为 $S_u$，数量为 $s_u$。 | ||
| 再记刚 DFS 完的那个子树根为 $v$，子树节点集合为 $S_v$，大小为 $s_v$，返回的线段树为 $A_v$。 | 再记刚 DFS 完的那个子树根为 $v$，子树节点集合为 $S_v$，大小为 $s_v$，返回的线段树为 $A_v$。 | ||
| - | 记接下来合并好的线段树为 $A'_u$，合并完的节点总数量为 $s'_u = s_u + s_v$。 | + | 记接下来合并好的线段树为 $A'_u$，合并完的子树点数量为 $s'_u = s_u + s_v$。 |
| 对于维护的答案，此时需要新增 $S_u$ 和 $S_v$ 之间，每对点形成的简单路径的贡献。 | 对于维护的答案，此时需要新增 $S_u$ 和 $S_v$ 之间，每对点形成的简单路径的贡献。 | ||
| 行 94: | 行 94: | ||
| 其中减掉一些信息，是因为 $C_{{A_u}, k}$ 和 $C_{{A_v}, k}$ 之间的简单路径被算了两次。 | 其中减掉一些信息，是因为 $C_{{A_u}, k}$ 和 $C_{{A_v}, k}$ 之间的简单路径被算了两次。 | ||
| - | 对于 $c_{{A'_u}, k}$，除了节点 $u$ 的颜色，都是两个线段树的信息直接求和。而对于节点 $u$ 的颜色 $k_u$，合并后有 $c_{{A'_u}, {k_u}} = s'_u$。 | + | 对于 $c_{{A'_u}, k}$，除了节点 $u$ 的颜色，都是 $c_{{A'_u}, k} = c_{{A_u}, k} + c_{{A_v}, k}$。而对于节点 $u$ 的颜色 $k_u$，合并后有 $c_{{A'_u}, {k_u}} = s'_u$。 |
| - | 其中乘一个数更新答案，可以用懒惰标记来做，在合并、修改、询问时下传标记即可。 | + | 其中乘一个数更新答案，可以用懒惰标记来做，因为标记可懒惰地叠加。在合并、修改、询问时下传标记即可。 |
| 减掉的那部分答案，就需要用一下线段树合并的性质，来将公共颜色的节点之间的简单路径的贡献处理好。 | 减掉的那部分答案，就需要用一下线段树合并的性质，来将公共颜色的节点之间的简单路径的贡献处理好。 | ||
2020-2021/teams/intrepidsword/2020.06.05-2020.06.11_周报.1591981695.txt.gz · 最后更改: 2020/06/13 01:08 由 chielo
