满足「结合律」的静态信息 CF1175E Minimal Segment Cover 预处理 $rt_x$ 表示点 $x$ 经过一条线段能到达的最右边的点。 跳区间显然是满足结合律的，可以倍增之，复杂度 $O(n \log_2 n)$。 这类题目有一个重要的小技巧：为了满足最优性，倍增时跳到不能到达 $y$ 的最远的点 $p$，然后判断能一次跳过 …

多项式哈希 把元素看作数字，把哈希对象看作关于 $P$ 的多项式，得到多项式哈希，亦称为进制哈希。 主要用于有序对象的哈希。 一般使用unsigned long long自然溢出，相当于对 $2^{64}$ 取模。 关于 $P$ 的选取，尽量避免常用的大质数。下文统一使用1610612741，其在 $[2^{30},2^{31}]$ 中。 void…

Trie luogu2922 [USACO08DEC]Secret Message G 给定两个字符串序列 $a$ 与 $b$，对于 $b$ 中每个字符串 $t$，求 $a$ 中有多少个字符串 $s$，满足以下两个条件之一 $s$ 是 $t$ 的前缀。 $t$ 是 $s$ 的前缀。 两个字符串序列中所有字符串长度之和不超过 $500000$。 把 …

突破口永远在环上。 找环是常用操作，但是并没有一个合适的模板。 笔者在写这篇文章之前就做过一些基环树的简单题，但是每一次写的找环都不尽相同。仅仅用dfs的回溯模拟一个栈，显然是不够公式化的，且容易出 bug，因此我们需要确定一种可靠的写法。 关于dfn的那套理论再合适不过了。 当然这玩意只能找一个环。 int cnt, num, fa[N]…

树形 DP 计数。 luogu8867 建造军营 对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。 然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 $f_x$ 为军营只在以 $x$ 为根的子树中出现，且至少存在 $1$ 个军营的方案数。 转移时对于边 $(x,y)$，如果…

树链剖分能够将一棵树按照某种法则剖分为若干条链，从而便于维护树上路径的信息。 按照剖出链的法则不同，其性质也不同，大体可将树剖分成重链剖分，长链剖分和用于 Link-Cut Tree 的剖分（实链剖分）。 其中重链剖分用途最广泛，本文也只介绍重链剖分。 重链剖分 定义与部分性质 给出如下定义 重儿子。对于一个非叶子节点，其重儿子为其以它的所有儿子为…

线段树上二分 用形式化的语言讲，线段树上二分求解的是这一类问题。 给定 $L$，找到一个 $R \in [L,n]$ 满足$$f \Big( op\big([L,R-1]\big) \Big) = 1$$$$f\Big( op\big(R\big) \Big)=0$$ 其中 $f$ 为某种合法性函数，$op$ 是将区间信息合并为 $f$ 能处理的信…

中国剩余定理（CRT） 由于扩展中国剩余定理和中国剩余定理没啥关系，所以我们先来复习一下中国剩余定理。 同余方程组 $$\begin{cases}x \equiv a_1 \pmod {m_1} \equiv a_2 \pmod {m_2} \quad \vdots \equiv a_n \pmod {m_n} \end{cases}$$ 当 $m…