From 10c0aca1faa7a395c3f16bd18ba5e79b747bd064 Mon Sep 17 00:00:00 2001 From: TrisolarisHD Date: Wed, 27 Mar 2019 22:54:31 +0800 Subject: [PATCH] =?utf8?q?=E6=8C=AA=E5=8A=A8=E4=BA=86=E4=B8=80=E4=BA=9B?= =?utf8?q?=E5=8E=9F=E6=9C=AC=E5=9C=A8=E6=9D=82=E9=A1=B9=E4=B8=AD=E7=9A=84?= =?utf8?q?=E5=86=85=E5=AE=B9.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- docs/ds/odt.md | 95 +++++++++++++++++++++ docs/{misc => graph}/dsu-on-tree.md | 10 +-- .../24620.png => graph/images/dsu-on-tree-1.png} | Bin .../24919.png => graph/images/dsu-on-tree-2.png} | Bin .../24909.png => graph/images/dsu-on-tree-3.png} | Bin .../graph/images/{1341373589_4609.png => topo.png} | Bin docs/{misc => graph}/matrix-tree.md | 14 +-- docs/graph/topo.md | 10 +-- docs/misc/odt.md | 95 --------------------- mkdocs.yml | 6 +- 10 files changed, 115 insertions(+), 115 deletions(-) create mode 100644 docs/ds/odt.md rename docs/{misc => graph}/dsu-on-tree.md (90%) rename docs/{misc/images/24620.png => graph/images/dsu-on-tree-1.png} (100%) rename docs/{misc/images/24919.png => graph/images/dsu-on-tree-2.png} (100%) rename docs/{misc/images/24909.png => graph/images/dsu-on-tree-3.png} (100%) rename docs/graph/images/{1341373589_4609.png => topo.png} (100%) rename docs/{misc => graph}/matrix-tree.md (92%) delete mode 100644 docs/misc/odt.md diff --git a/docs/ds/odt.md b/docs/ds/odt.md new file mode 100644 index 00000000..a0b32ef4 --- /dev/null +++ b/docs/ds/odt.md @@ -0,0 +1,95 @@ +## 名称简介 + +老司机树，ODT(Old Driver Tree)，又名珂朵莉树（Ctholly Tree)。 +起源自 [CF896C](https://codeforces.com/problemset/problem/896/C)。 + +## 前置知识 + +会用 STL 的 set 就行。 + +## 核心思想 + +把值相同的区间合并成一个结点保存在 set 里面。 + +## 用处 + +骗分。 +只要是有区间赋值操作的数据结构题都可以用来骗分。 +一般出题人不会 **刻意** 卡，但是不小心卡了就…… + +如果要保证复杂度正确，必须保证数据随机。 +证明在[此](http://codeforces.com/blog/entry/56135?#comment-398940)。 + +## 正文 + +首先，结点的保存方式： + +```cpp +struct Node_t { + int l, r; + mutable int v; + Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {} + inline bool operator(const Node_t &o) const { return l < o.l; } +}; +``` + +其中， `int v` 是你自己指定的附加数据。 + +然后，我们定义一个 `set odt;` 来维护这些结点。 +为简化代码，可以 `typedef set::iterator iter`，当然在题目支持 C++11时也可以使用 `auto`。 + +### split + +最核心的操作之一 `split` ，它用于取得以 $x$ 开头的结点。 +参考代码如下： + +```cpp +auto split(int x) { + if (x > n) + return odt.end(); + auto it = --odt.upper_bound((Node_t){x, 0, 0}); + if (it->l == x) return it; + int l = it->l, r = it->r, v = it->v; + odt.erase(it); + odt.insert(Node_t(l, x - 1, v)); + return odt.insert(Node_t(x, r, v)).first; +} +``` + +这个玩意有什么用呢？ +任何对于 $[l,r]$ 的区间操作，都可以转换成 set 上 $[split(l),split(r + 1))$ 的操作。 + +### assign + +另外一个重要的操作 `assign` 用于对一段区间进行赋值。 +对于 ODT 来说，区间操作只有这个比较特殊，也是保证复杂度的关键。 +如果 ODT 里全是长度为 $1$ 的区间，就成了暴力，但是有了 `assign` ，可以使 ODT 的大小下降。 +参考代码如下： + +```cpp +void assign(int l, int r, int v) { + auto itr = split(r + 1), itl = split(l); + odt.erase(itl, itr); + odt.insert(Node_t(l, r, v)); +} +``` + +### 其他操作 + +套模板就好了，参考代码如下： + +```cpp +void performance(int l, int r) { + auto itr = split(r + 1), itl = split(l); + for (; itl != itr; ++itl) { + // Perform Operations here + } +} +``` + +## 习题 + +- [「SCOI2010」序列操作](https://www.lydsy.com/JudgeOnline/problem.php?id=1858) +- [「SHOI2015」脑洞治疗仪](https://www.lydsy.com/JudgeOnline/problem.php?id=4592) +- [「Luogu 2787」理理思维](https://www.luogu.org/problemnew/show/P2787) +- [「Luogu 4979」矿洞：坍塌](https://www.luogu.org/problemnew/show/P4979) diff --git a/docs/misc/dsu-on-tree.md b/docs/graph/dsu-on-tree.md similarity index 90% rename from docs/misc/dsu-on-tree.md rename to docs/graph/dsu-on-tree.md index 4385bf41..37cdb84d 100644 --- a/docs/misc/dsu-on-tree.md +++ b/docs/graph/dsu-on-tree.md @@ -31,7 +31,7 @@ void merge(int x, int y) { 给出一棵树，每个节点有颜色，询问一些子树的颜色数量（颜色可重复）。 -![24620.png](./images/24620.png) +![dsu-on-tree-1.png](./images/dsu-on-tree-1.png) 对于这种问题解决方式大多是运用大量的数据结构（树套树等），如果可以离线，询问的量巨大，是不是有更简单的方法？ @@ -57,7 +57,7 @@ void merge(int x, int y) { - 再次遍历其非重儿子及其父亲，用重儿子的 check 对遍历到的节点进行计算，获取整棵子树的 ans； -![24919.png](./images/24919.png) +![dsu-on-tree-2.png](./images/dsu-on-tree-2.png) _上图是一个例子_ @@ -81,7 +81,7 @@ _上图是一个例子_ 又因为如果一个节点是其父亲的重儿子，则他的子树必定在他的兄弟之中最多，所以任意节点到根的路径上所有重边连接的父节点在计算答案是必定不会遍历到这个节点，所以一个节点的被遍历的次数等于他到根节点路径上的轻边树 $+1$ （之所以要 $+1$ 是因为他本身要被遍历到），所以一个节点的被遍历次数 $=\log n+1$ , 总时间复杂度则为 $O(n(\log n+1))=O(n\log n)$ ，输出答案花费 $O(m)$ . -![24909.png](./images/24909.png) +![dsu-on-tree-3.png](./images/dsu-on-tree-3.png) _图中标红的即为重边，重边连向的子节点为重儿子_ @@ -137,11 +137,11 @@ int dfs2(int u, int fa, bool keep, bool isson) { 1. 某些出题人设置的正解是 dsu on tree 的题 -如[CF741D](http://codeforces.com/problemset/problem/741/D)。给一棵树，每个节点的权值是'a'到'v'的字母，每次询问要求在一个子树找一条路径，使该路径包含的字符排序后成为回文串。 +如 [CF741D](http://codeforces.com/problemset/problem/741/D)。给一棵树，每个节点的权值是 'a' 到 'v' 的字母，每次询问要求在一个子树找一条路径，使该路径包含的字符排序后成为回文串。 因为是排列后成为回文串，所以一个字符出现了两次相当于没出现，也就是说，这条路径满足 **最多有一个字符出现奇数次** 。 -正常做法是对每一个节点 dfs，每到一个节点就强行枚举所有字母找到和他异或后结果为 1 的个数<1 的路径，再去最长值，这样 $O(n^2\log n)$ 的，可以用 dsu on tree 优化到 $O(n\log^2n)$ 。关于具体做法，可以参考下面的扩展阅读 +正常做法是对每一个节点 dfs，每到一个节点就强行枚举所有字母找到和他异或后结果为 1 的个数大于 1 的路径，再取最长值，这样是 $O(n^2\log n)$ 的，可以用 dsu on tree 优化到 $O(n\log^2n)$ 。关于具体做法，可以参考下面的扩展阅读 2. 可以用 dsu 乱搞~~吊打 std~~水分的题 diff --git a/docs/misc/images/24620.png b/docs/graph/images/dsu-on-tree-1.png similarity index 100% rename from docs/misc/images/24620.png rename to docs/graph/images/dsu-on-tree-1.png diff --git a/docs/misc/images/24919.png b/docs/graph/images/dsu-on-tree-2.png similarity index 100% rename from docs/misc/images/24919.png rename to docs/graph/images/dsu-on-tree-2.png diff --git a/docs/misc/images/24909.png b/docs/graph/images/dsu-on-tree-3.png similarity index 100% rename from docs/misc/images/24909.png rename to docs/graph/images/dsu-on-tree-3.png diff --git a/docs/graph/images/1341373589_4609.png b/docs/graph/images/topo.png similarity index 100% rename from docs/graph/images/1341373589_4609.png rename to docs/graph/images/topo.png diff --git a/docs/misc/matrix-tree.md b/docs/graph/matrix-tree.md similarity index 92% rename from docs/misc/matrix-tree.md rename to docs/graph/matrix-tree.md index b4a18a0c..68637388 100644 --- a/docs/misc/matrix-tree.md +++ b/docs/graph/matrix-tree.md @@ -2,7 +2,7 @@ Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成 ## 本篇记号声明 - **本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。** + **本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。** ### 无向图情况 @@ -34,7 +34,7 @@ $$ D^{out}_{ii}(G) = \mathrm{deg^{out}}(i), D^{out}_{ij} = 0, i\neq j $$ -类似地定义入度矩阵 $D^{in}(G)$ +类似地定义入度矩阵 $D^{in}(G)$ 设 $\#e(i,j)$ 为点 $i$ 指向点 $j$ 的有向边数，并定义邻接矩阵 $A$ 为： @@ -72,7 +72,7 @@ $$ **定理 2（矩阵树定理，无向图特征值形式）** 设 $\lambda_1, \lambda_2, \cdots, \lambda_{n-1}$ 为 $L(G)$ 的 $n - 1$ 个非零特征值，那么有 - $t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}$ + $t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}$ **定理 3（矩阵树定理，有向图根向形式）** 对于任意的 $k$ ，都有 @@ -103,12 +103,12 @@ $$ ## 例题 ???+ note "例题 1" - HEOI2015: 小 Z 的房间，请参考 + 「HEOI2015」小 Z 的房间，可参考 **解** 矩阵树定理的裸题。将每个空房间看作一个结点，根据输入的信息建图，得到 Laplace 矩阵后，任意删掉 L 的第 $i$ 行第 $i$ 列，求这个子式的行列式即可。求行列式的方法就是高斯消元成上三角阵然后算对角线积。另外本题需要在模 $k$ 的整数子环 $\mathbb{Z}_k$ 上进行高斯消元，采用辗转相除法即可。 ???+ note "例题 2" - FJOI2007: 轮状病毒。请参考 + 「FJOI2007」轮状病毒。可参考 **解** 本题的解法很多，这里用矩阵树定理是最直接的解法。当输入为 $n$ 时，容易写出其 $n+1$ 阶的 Laplace 矩阵为： @@ -183,10 +183,10 @@ $$ 改写成 $(\det M_n+2) = 3(\det M_{n-1}+2) - (\det M_{n-2} + 2)$ 后，采用矩阵快速幂即可求出答案。 ???+ note "例题 3" - BZOJ3659: WHICH DREAMED IT + 「BZOJ3659」WHICH DREAMED IT **解** 本题是 BEST 定理的直接应用，但是要注意，由于题目规定“两种完成任务的方式算作不同当且仅当使用钥匙的顺序不同”，对每个欧拉回路，1 号房间可以沿着任意一条出边出发，从而答案还要乘以 1 号房间的出度。 ## 注释 -根向树形图在一些地方被称为内向树形图，但因为计算内向树形图用的是出度，为了不引起 in 和 out 的混淆，所以采用了根向这一说法。 +根向树形图也被称为内向树形图，但因为计算内向树形图用的是出度，为了不引起 in 和 out 的混淆，所以采用了根向这一说法。 diff --git a/docs/graph/topo.md b/docs/graph/topo.md index fb808f92..c688bdd1 100644 --- a/docs/graph/topo.md +++ b/docs/graph/topo.md @@ -16,7 +16,7 @@ ## Kahn 算法 -将入度为 0 的边组成一个集合 $S$ +将入度为 0 的边组成一个集合 $S$ 每次从 $S$ 里面取出一个顶点 $v$ （可以随便取）放入 $L$ , 然后遍历顶点 $v$ 的所有边 $(u_1, v), (u_2, v), (u_3, v) \cdots$ , 并删除，并判断如果该边的另一个顶点，如果在移除这一条边后入度为 0 , 那么就将这个顶点放入集合 $L$ 中。不断地重复取出顶点然后…… @@ -36,7 +36,7 @@ while S is non-empty do insert m into S if graph has edges then return error (graph has at least onecycle) -else +else return L (a topologically sortedorder) ``` @@ -44,7 +44,7 @@ else 可以参考该图 -![1341373589_4609](images/1341373589_4609.png) +![topo](images/topo.png) 对其排序的结果就是：2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12 @@ -52,7 +52,7 @@ else 假设这个图 $G = (V, E)$ 在初始化入度为 0 的集合 $S$ 的时候就需要遍历整个图，并检查每一条边，因而有 $\mathcal{O}(E+V)$ 的复杂度。然后对该集合进行操作，显然也是需要 $\mathcal{O}(E+V)$ 的时间复杂度。 -因而总的时间复杂度就有 $\mathcal{O}(E+V)$ +因而总的时间复杂度就有 $\mathcal{O}(E+V)$ ### 实现 @@ -109,7 +109,7 @@ bool toposort() { } ``` -时间复杂度： $O(n+m)$ 空间复杂度： $O(n)$ +时间复杂度： $O(n+m)$ 空间复杂度： $O(n)$ ### 合理性证明 diff --git a/docs/misc/odt.md b/docs/misc/odt.md deleted file mode 100644 index 7bd3611a..00000000 --- a/docs/misc/odt.md +++ /dev/null @@ -1,95 +0,0 @@ -## 名称简介 - -老司机树，ODT(Old Driver Tree)，珂朵莉树（Ctholly Tree)。 -起源自[CF896C](https://codeforces.com/problemset/problem/896/C)。 - -## 前置知识 - -会用 STL 的 set 就行。 - -## 核心思想 - -把值相同的区间合并成一个结点保存在 set 里面。 - -## 用处 - -骗分。 -只要是有区间赋值操作的数据结构题都可以用来骗分。 -一般出题人不会 **刻意** 卡，但是不小心卡了就…… - -如果要保证复杂度正确，必须保证数据随机。 -证明在[此](http://codeforces.com/blog/entry/56135?#comment-398940)。 - -## 正文 - -首先，结点的保存方式： - -```cpp -struct node { - int l, r; - mutable int v; - inline bool operator(const node &o) const { return l < o.l; } -}; -``` - -其中， `int v` 是你自己指定的附加数据。 - -然后，我们定义一个 `set odt;` 来维护这些结点。 -为简化代码，可以 `typedef set::iterator IT` 。 - -### split - -最核心的操作之一 `split` ，它用于取得以 $x$ 开头的结点。 -参考代码如下： - -```cpp -IT split(int x) { - if (x > n) - ; - return odt.end(); - IT it = --odt.upper_bound((node){x, 0, 0}); - if (it->l == x) return it; - int l = it->l, r = it->r, v = it->v; - odt.erase(it); - odt.insert((node){l, x - 1, v}); - return odt.insert((node){x, r, v}).first; -} -``` - -这个玩意有什么用呢？ -任何对于 $[l,r]$ 的区间操作，都可以转换成 set 上 $[split(l),split(r + 1))$ 的操作。 - -### assign - -另外一个重要的操作 `assign` 用于对一段区间进行赋值。 -对于 ODT 来说，区间操作只有这个比较特殊，也是保证复杂度的关键。 -如果 ODT 里全是长度为 $1$ 的区间，就成了暴力，但是有了 `assign` ，可以使 ODT 的大小下降。 -参考代码如下： - -```cpp -void assign(int l, int r, int v) { - IT itr = split(r + 1), itl = split(l); - odt.erase(itl, itr); - odt.insert((node){l, r, v}); -} -``` - -### 其他操作 - -套模板就好了，参考代码如下： - -```cpp -void performance(int l, int r) { - IT itr = split(r + 1), itl = split(l); - for (; itl != itr; ++itl) { - // Perform here - } -} -``` - -## 习题 - -- [BZOJ 1858.\[SCOI2010\]序列操作](https://www.lydsy.com/JudgeOnline/problem.php?id=1858) -- [BZOJ 4592.\[SHOI2015\]脑洞治疗仪](https://www.lydsy.com/JudgeOnline/problem.php?id=4592) -- [洛谷 2787. 理理思维](https://www.luogu.org/problemnew/show/P2787) -- [洛谷 4979. 矿洞：坍塌](https://www.luogu.org/problemnew/show/P4979) diff --git a/mkdocs.yml b/mkdocs.yml index 9602eb31..020b4de3 100644 --- a/mkdocs.yml +++ b/mkdocs.yml @@ -197,6 +197,7 @@ nav: - 可持久化块状数组: ds/persistent-block-array.md - 可持久化平衡树: ds/persistent-balanced.md - 可持久化字典树: ds/persistent-trie.md + - 珂朵莉树: ds/odt.md - Link Cut Tree: ds/lct.md - Euler Tour Tree: ds/ett.md - 图论: @@ -211,6 +212,8 @@ nav: - 树链剖分: graph/heavy-light-decomposition.md - 树分治: graph/tree-divide.md - 动态树分治: graph/dynamic-tree-divide.md + - 树上启发式合并: graph/dsu-on-tree.md + - 矩阵树定理: graph/matrix-tree.md - 有向无环图: graph/dag.md - 拓扑排序: graph/topo.md - 最小生成树: graph/mst.md @@ -257,7 +260,6 @@ nav: - 爬山算法: misc/hill-climbing.md - 分数规划: misc/fractional-programming.md - 模拟退火: misc/simulated-annealing.md - - 矩阵树定理: misc/matrix-tree.md - 随机增量法: misc/random-incremental.md - 随机化: misc/random.md - 离线处理: misc/offline.md @@ -267,8 +269,6 @@ nav: - 计算理论基础: misc/cc-basic.md - 读入、输出优化: misc/io.md - 离散化: misc/discrete.md - - 树上启发式合并: misc/dsu-on-tree.md - - 珂朵莉树: misc/odt.md # Theme theme: -- 2.11.0