小明の雜貨鋪

树具有天然的合并性质，即某节点的子树信息全部来自于它子节点的子树信息。因此先计算子节点，再计算父节点，在树上 DFS 的过程中，将子树的信息合并到父节点上。 线段树合并暂时不支持区间修改。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667template<class info>struct SMT { int L, R, pcnt; vector<info> t; vector<int> ls, rs; vector<int> rt; SMT() { init(0, 0); t.resize(N << 2); ls.resize(N << 2); rs.resize(N << 2); ...

两次 DFS 求树直径 时空复杂度 Θ(n)\Theta(n)Θ(n)。 123456789101112131415161718192021vector<int> p(n), path;auto find = [&](int s) { vector<int> dep(n, -1); auto dfs = [&](this auto&& dfs, int u) -> void { for (auto v : E[u]) { if (~dep[v]) continue; dep[v] = dep[u] + 1; // 如果带点权 dep[v] = dep[u] + val[v]; // 如果带边权 dep[v] = dep[u] + w; p[v] = u; dfs(v); } }; ...

Strings 子序列 将若干元素提取出来并不改变相对位置形成的序列，不一定连续。 子串 连续的子序列。 后缀 （Suffix）从某位置到整个串末尾结束的子串。 前缀 （Prefix）从串首开始到某位置结束的子串。 字典序 以第 iii 个字符作为第 iii 关键字进行大小比较，空字符小于字符集内任何字符。

Manacher Algorithm Find the longest substring which is palindrome. 在搜索到 iii 时， cc,ll,rr 已经找到的右边界最大的回文串的中心、左端和右端。 p[i] 以 iii 为中心的最长回文串长度。如果 iii 在最长回文串之中，p[i] 至少是它对称位置的 p[mirror]。利用此性质快速计算 p[i]。 123456789101112131415161718vector<int> manacher(const string& s) { string t = "#"; for (auto c : s) t += c, t += '#'; const int n = t.size(); vector<int> r(n);  // 存储每个字符作为中心的最长回文子串的半径 for (int i = 0, j = 0; i < n; i++) { if (2...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ulll = __uint128_t;constexpr int N = 1e6 + 8;constexpr ull mod = (1ull << 61) - 1;mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());uniform_int_distribution<ull> dist(mod / 2, mod - 1);const ull H = dist(rnd);struct mull { ull x; constexpr...

char ascii 0 48 9 57 A 65 Z 90 a 97 z 122 经典字典树 主机场 给定一组字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_ns1​,s2​,⋯,sn​，任选 kkk 个 sa1,sa2,⋯ ,sak (ai≠aj)s_{a_1},s_{a_2},\cdots,s_{a_k}\ (a_{i}\ne a_{j})sa1​​,sa2​​,⋯,sak​​ (ai​=aj​)，最小化 max⁡1⩽i,j⩽k,i≠jlcp⁡(sai,saj)\max\limits_{1 \leqslant i,j \leqslant k,i\ne j}^{}\operatorname{lcp}(s_{a_i},s_{a_j})1⩽i,j⩽k,i=jmax​lcp(sai​​,saj​​)。其中 lcp⁡(p,q)\operatorname{lcp}(p,q)lcp(p,q) 是字符串 ppp 和字符串 qqq...

判断无根树是否同构，时间复杂度 Θ(∑n)\Theta\left(\sum n \right)Θ(∑n)。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;mt19937_64 rng{ chrono::steady_clock::now().time_since_epoch().count() };const int N = 3e5 + 8;ull hsh[N];int main() { for (int i = 0; i < N; i++) { hsh[i] = rng(); ...

Given a text s[] and a pattern p[], print all occurrences of p[] in s[]. Brute force solution 最坏时间复杂度 Θ(mn)\Theta(mn)Θ(mn)。 12345678910int i = 0, j = 0;while (i < s.length()) { if (s[i] == T[j]) ++i, ++j; else i = i-j+1, j = 0; if (j == T.length()) { // 匹配成功 printf("[%d-%d] ", i-j, i-1); i = i - j + 1; j = 0; }} KMP Algorithm ——Knuth-Morris-Pratt 字符串查找算法 PMT（Partial Match Table，部分匹配表...

二分图 Stop the Castle There are n castles and m obstacles on a chessboard. Each castle or obstacle occupies exactly one cell and all occupied cells are distinct. Two castles can attack each other, if they’re on the same row or the same column, and there are no obstacles or other castles between them. Find a way to place the minimum number of additional obstacles onto the chessboard, so that no two castles can attack each...

后缀数组 后缀数组 (Suffix Array, SA) 是把字符串的所有 后缀 按 字典序 排序后得到的数组。 定义： 排名数组 rk⁡w(i)\operatorname{rk}_w(i)rkw​(i)：从第 iii 位开始、长度为 www 的子串在所有长度为 www 的子串中的排名； 编号数组 sa⁡w(i)\operatorname{sa}_w(i)saw​(i)：长度为 www 的子串中字典序第 iii 小的一个的开始位置，与排名数组互逆，即 sa⁡(rk⁡(i))=i\operatorname{sa}(\operatorname{rk}(i))=isa(rk(i))=i，rk⁡(sa⁡(i))=i\operatorname{rk}(\operatorname{sa}(i))=irk(sa(i))=i。 用倍增法在 Θ(nlog⁡n)\Theta(n\log n)Θ(nlogn)...