浅谈线段树合并 观前提示：本文主要介绍线段树合并的浅层应用和较为简单的写法。 权值线段树 我们线段树的很多操作都是基于动态开点权值线段树进行实现的，空间是 $O(n \log n \times K)$ 其中 $K$ 是每次询问进行线段树操作的个数。当然我们有优化到 $O(n)$ 空间的做法，这个我们后面再谈。 维护方式 我们通常将其用来维护一些可以通过全局表示的信息，最显然的就是一段值域，或者是深度等。 线段树合并也可以在线进行维护信息的，也就是我们对于每个线段树都要保留下来，我们像可持久化一样，每次进行操作的时候就复制一份节点，这个空间就是 $O(n\text{ polylog(n)})$。 具体做法 考虑合并的时候贪心一下，如果说两棵树其中有一个是空的，那么我们直接接到另外一个树上即可。 这里推荐一种写法： 123456789101112131415int merge(int u,int v) { if(!u || !v) return u | v; if(isleaf(u)) { Add(v, val[u]); ...

CF1453E Dog Snacks CF1453E Dog Snacks 可能一开始会简单地考虑将深度最大的作为 $k$，但是样例已经很显然得告诉可以通过跳到一个稍微浅一点的位置。 那么显然有一个很明显的贪心，就是我们设 $f(i)$ 表示子树 $i$ 的结尾叶子，也就是深度最浅的叶子节点和 $i$ 的距离。那么我们显然肯定最终是选择到一个深度最浅的点。 我们具体跳的过程肯定是优先跳深度大的，之后逐渐向小的跳跃。我们考虑这里不可避免的贡献，也就是如果是深度最大的需要跳到别的子树，就是其深度 $+1$。 我们特殊考虑一下根节点，也就是我们跳完时候还要回到根节点，那么我们可以考虑在根节点的时候最后到深度最大的子树，这样我们的贡献就只有最大深度了，显然更优秀。 我们总结一下： 不是根节点： 不是一条链：$mxdep + 1$。 是一条链：不更新，因为我们会在根节点的时候同一计算。 根节点： 是一条链：直接就是最大深度。 不是一条链：$\max($最大深度，次大深度 $+1)$。 123456789101112131415161718192021222324252627 ...

CF1494D Dogeforces CF1494D Dogeforces 发现我们最终维护出来的树肯定是一个大根堆的样子，也就是父亲节点的权值严格大于子树的任意节点的权值，那么既然所有叶子节点的关系边权都已经给出了，我们不妨考虑使用 $\tt Kruscal$ 重构树进行构造。 但是重构树可能存在一种情况，也就是父亲节点的权值和儿子节点的权值是相同的，我们不妨考虑将这两个点缩成同一个点。 我们考虑这种构造是否合法，也就是是否仍然满足二叉树的性质，如果当前的点和父亲节点缩到一起的话，可以保证每个节点至少有两个儿子，正好和题目的要求相契合。 显然如果说恰好只有 $2$ 个儿子的话显然不能用构造，考虑树： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#i ...

论小部分的图树论转化 Graph 直接将模型抽象到图上：比如说题目说了相互之间的关联，可以直接看做边之类的。 同类（相同集合）建图：如果说需要求一个集合满足 $\forall a \in S$ 都存在一个不同的 $f(a) \in S$，对于这种我们可以考虑将 $a \to f(a)$ 这样的话如果出现了环就说明是本质相同的。 我们也不一定要局限于这样的函数，比如说求 $\sum_{i \in S} i - a_i = 0$ 中的 $S$，我们不妨考虑将其分开来考虑 $\sum_{i \in S} i = \sum_{i \in S} a_i$ 那么限制的本质就是一个满射，而且属于同一个域（封闭性）。那么我们考虑建边 $i \to a_i$ 找到合法的环即可。 前缀和优化建图：如果需要考虑连边关系的时候，我们考虑将 $i$ 可以到 $j$ 转化成**存在一条 **$i \to j$ 的路径即可，不一定需要直接连边。换句话说，只要我们建立的图进行传递闭包之后满足上述条件即可。 前缀和作差建图：不妨考虑题目中给定进行一个操作的限制是，区间和为 $0$。那么我们不妨尝试建立前 ...

CF1601C Optimal Insertion [CF1601C](C. Optimal Insertion) 我们不妨考虑让 $b$ 先进行排序从小到大进行插入。 考虑相邻两个位置的 $b$，不妨考虑为 $i, i + 1$。显然 $pos_i < pos_{i + 1}$，不然交换之后肯定可以得到更优的答案。 我们考虑既然有单调性，就可以进行分治。 我们考虑进行像 $\tt Dp$ 一样进行决策单调性分治，之后需要在 $O(n)$ 内算出 $b_{mid}$ 的最优位置。 我们不妨考虑钦定一个逆序对的基准值，之后每次移动 $b_{mid}$ 的位置都修改贡献，具体来说： $a_i < b_{mid}$ 就需要减少贡献。 $a_i > b_{mid}$ 就需要增加贡献。 之后我们只要建出序列直接进行计算即可。 复杂度 $O((n + m) \log n)$。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535 ...

三元环计数 就是考试的时候整了一个这个科技，我没想出来，然后无了… 具体来说就是计算图中三元团的个数。 有一个 $O(m\sqrt m)$ 的算法： 让度数大的点连接度数小的点。 枚举每个点并将其相邻的点记录匹配点为当前点 $i$。 枚举当前点邻居的邻居，看匹配点是否是点 $i$。 每个三元团只会被计算一次。 分析一下复杂度： 每个点的入度度数最大是 $O(\sqrt m)$，这里可以考虑反证： 如果大于 $\sqrt m$，那么连边就是不合法的。 所以打标记是 $O(m\sqrt m)$ 的。 为了保证图是一个 $DAG$ ，我们还需要钦定如果度数相同要从值小的连接向大的即可。 这样可以保证一个三元环 $(u, v, w)$ 被计算当且仅当存在边：$u \to v, u \to w, v \to w$。 $Code$ 12345678910111213141516for(int i = 1; i <= m; ++ i) r1(eu[i], ev[i]), ++ deg[eu[i]], ++ deg[ev[i]];auto cmp = [&](int a, ...

P3366 【模板】最小生成树这个算法就是考虑每一次合并 $n$ 个联通块，变成 $\frac{n}{2}$ 个。所以总共合并的次数是 $\log_2 n$ 次。 我们还是使用并查集来维护每一个联通块，这个算法的好处就是因为其合并次数是 $\log n$ 级别的，所以我们可以在里面进行 $O(n)$ 的处理。来处理一些不能直接进行最小生成树的情况。 比如说要维护两点 $\tt And$ 值为 $0$ 的图。我们直接使用 $\tt prim$ 复杂度会直接爆炸。但是我们用 $\tt Boruvka$ 可以每一次 $O(n)$ 级别处理各种联通块的信息，然后进行生成树。 对于模板题具体来说，我们对于每一个联通块维护一个最小的边权，边的另外一头是与其所属联通块不同的点。 这边注意每一次操作应该考虑的是所属联通块，然后这边有一个很好的性质 可能也没有那么有性质。 $\color{red}\tt \text{在进行合并联通块之前，联通块的根是不会变的}$。 这样我们可以直接在预处理的时候存储每个集合的根，看起来这个性质不起眼，但是在题目中可以方便许多。 123456789101112131 ...

浅谈AC自动机 建议学过 AC 自动机的人来看。 注意我们一开始直接建立串的时候是 $\tt Trie$ 图，之后建立 $\tt fail$ 指针的时候才是真正的 $AC$ 自动机。 具体来说对于 $\tt Trie$ 上深度从小到大的一条链，对应的是一个曾经在某个或者多个串中出现过的子串。 如果说是一条从根到底的链那本质就是代表一个串，显然对于一条链之间的点，本质上深度小的是深度大的前缀串。 用处： 我们可以通过遍历 $\tt Trie$ 图来不重复地遍历每个字符串（不会有相交）。 还有一个东西叫 $\tt fail$ 树，这个东西的定义和 $\tt nxt$ 数组很类似，就是与当前串公共后缀最长的点。 那么我们一直沿着 $\tt fail$ 树跳的话是可以遍历到所有与当前串后缀部分有交的串，而且是交是从大到小的。 注意： 我们进行找 $\tt fail$ 指针的时候需要使用路径压缩，但是即使使用了路径压缩，我们直接建立 $\tt fail$ 树的时候完全不会有影响。 如果说拿节点 $1$ 当做超级源点的话，对于周围一圈的不存在的点，需要路径压缩至点 $1$。 用 ...