From ec9be5f2a95540710f416a6aaca3bc44098f582d Mon Sep 17 00:00:00 2001 From: ouuan Date: Sat, 30 Mar 2019 20:03:38 +0800 Subject: [PATCH] Update tree-decompose.md --- docs/ds/tree-decompose.md | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/docs/ds/tree-decompose.md b/docs/ds/tree-decompose.md index cea3bfb5..18468199 100644 --- a/docs/ds/tree-decompose.md +++ b/docs/ds/tree-decompose.md @@ -92,11 +92,11 @@ $=T(cu,tu)\ xor\ T(cv,tv)$ ### 复杂度分析 -每块大小在 $[B,3B)$，所以两点间路径长度也在 $[B,3B)$，块内移动就是 $O(B)$ 的；编号相邻的块位置必然是相邻的，所以两块间路径长度也是 $O(B)$；然后就和序列莫队的复杂度分析类似了... +每块大小在 $[B,3B)$，所以两点间路径长度也在 $[B,3B)$，块内移动就是 $\mathcal O(B)$ 的；编号相邻的块位置必然是相邻的，所以两块间路径长度也是 $\mathcal O(B)$；然后就和序列莫队的复杂度分析类似了... ### 例题代码 -[[WC2013]糖果公园](https://www.luogu.org/problemnew/show/P4074) +[[WC2013]糖果公园](https://www.luogu.org/problemnew/show/P4074)，这题要用带修莫队，复杂度为 $\mathcal O(n^{\frac 5 3}+m\log m)$（视作 $n,m$ 同阶）。 ```cpp #include @@ -296,6 +296,6 @@ void add(int u,int v) 在模拟赛遇到过一道题，并没有在线提交的地方，也找不到代码了.. -题意大概是：给你一棵点有颜色的树，每次询问给你若干条路径，要么询问这些路径的并的颜色数，要么询问这些路径的并出现的颜色的 mex（最小的未出现颜色），强制在线。 +题意大概是：给你一棵点有颜色的树，每次询问给你若干条路径，要么询问这些路径的并的颜色数，要么询问这些路径的并出现的颜色的 mex（最小的未出现颜色），强制在线。节点数 $n\le10^5$，总路径条数 $m\le10^5$，颜色数 $c\le10^4$。 -std 是树分块+bitset：预处理出块的关键点之间路径上颜色的 bitset，询问的时候块内暴力，块直接已经预处理了。 +std 是树分块+bitset：预处理出每块的关键点到祖先中每个关键点之间路径上颜色的 bitset，询问的时候把路径拆成两个端点分别到块内关键点、两个关键点分别到 $lca$ 所在块的下面一块的关键点、这两块的关键点分别到 $lca$，块内暴力，块的关键点到块的祖先关键点已经预处理了。时间复杂度是 $\mathcal O(n\sqrt n+m(\sqrt n+\frac c w))$（$w$ 为 bitset 的常数除以 $32$），空间复杂度为 $\mathcal O(\frac{nc}w)$。 -- 2.11.0