有一种考前背书的美
目录有一些太熟悉的例如线段树、树状数组、NTT、FWT 以及 nim 游戏感觉就不写了。注意，要看的是不熟悉的！
感觉基础知识都差不多的了，没有因此而焦虑的必要。
线性代数
行列式
\[\operatorname{det}(A)=\sum_p(-1)^{\operatorname{sgn}(p)}\prod_{i}A[i][p_i]. \]- 交换两行，行列式变号。
- 某一行乘以 \(t\)，行列式值乘以 \(t\)。
- 有两行相同，行列式为 \(0\)。
- 用一行的倍数加到另一行，行列式不变。
矩阵树定理
无向图：邻接矩阵 \(-\) 度数矩阵，划去任意的 \(k\) 的第 \(k\) 行第 \(k\) 列的行列式。
有向图：根向树的度数矩阵是每个点的出度。外向树的度数矩阵是每个点的入度。划去 \(k\) 则根为 \(k\)。
BEST 定理
有向图 \(G\) 的欧拉回路条数为 \(T\prod_{x\in V}(deg_x-1)!\)。其中 \(T\) 是任意一点为根的根向生成树个数，可以证明任意一个答案都相同。\(deg_x\) 是入度和出度随便取一个。需要保证存在欧拉回路。
LGV 引理
\[\begin{vmatrix} e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n) \end{vmatrix}=\sum_{S:A\to B}(-1)^{\operatorname{sgn}(\sigma(S))}\prod_{i=1}^n w(P_i). \]其中 \(S=\{P_1, P_2, \cdots P_n\}\) 为一组不相交的路径。
数论（约数）
积性函数
\[\mu*I=\epsilon \]\[\varphi*I=id \]MR & PR
点击查看代码
mt19937_64 rng{random_device{}()};
LL qmul(LL a, LL b, LL n) { return (__int128)a * b % n; }
LL qpow(LL a, LL b, LL n) {
LL r = 1;
for (; b; b >>= 1, a = qmul(a, a, n)) {
if (b & 1) r = qmul(r, a, n);
}
return r;
}
bool isprime(LL n) {
if (n <= 1) return 0;
auto MR = [&](LL a) -> bool {
LL d = n - 1, r = 0;
while (d % 2 == 0) d >>= 1, ++r;
LL k = qpow(a, d, n);
if (k == 1) return true;
while (r--) {
if (k == n - 1) return true;
k = qmul(k, k, n);
}
return false;
};
constexpr int bases[] = {2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37};
for (int b : bases) {
if (n % b == 0) return n == b;
if (!MR(b)) return false;
}
return true;
}
vector<LL> divide(LL n) {
if (isprime(n)) return {n};
if (n < 2) return {};
static const auto find = [&](LL n) {
auto f = [&, c = (LL)rng() % (n - 1) + 1](LL x) {
return (qmul(x, x, n) + c) % n;
};
LL val = 1, s = 0, t = 0;
for (int gal = 1;; gal <<= 1, s = t, val = 1) {
for (int stp = 1; stp <= gal; stp++) {
t = f(t);
val = qmul(val, abs(t - s), n);
if (stp % 127 == 0 || stp == gal) {
LL d = gcd(val, n);
if (d > 1) return d;
}
}
}
return n;
};
LL p = n;
while (p == n) p = find(n);
int cnt = 0;
while (n % p == 0) n /= p, ++cnt;
auto r1 = divide(n), r2 = divide(p);
for (LL p : r2) r1.insert(r1.end(), cnt, p);
return r1;
}
剩余系划分
在 \(n\) 个点的图中，点集为 \(\{0, 1, \cdots, n-1\}\)。若将 \(i\) 与 \((i+d)\bmod n\) 连边，则得到 \(\gcd(n, d)\) 个长为 \(n/\gcd(n, d)\) 的环。（提示：代入 \(d=1\)）
单位根及反演
设 \(\omega_n\) 为 \(n\) 次本原单位根，则有
\[x^n-1=\prod_{i=0}^{n-1}(x-\omega_n^i) \]（可以代入 \(x=-1\) 等神秘数字）
\[[n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik} \]数论（同余）
二次剩余：Cipolla
给定 \(c, p\)，\(p\) 为奇质数，求解关于 \(x\) 的同余方程 \(x^2\equiv c\pmod p\)。
欧拉判别：对于任意 \(c\)，\(c^{(p-1)/2}\equiv \pm 1\pmod p\)。当且仅当 \(c\) 有二次剩余时，\(c^{(p-1)/2}\equiv 1\pmod p\)。
Cipolla 过程：随机一个 \(a\)，使得 \(a^2-c\) 没有二次剩余（期望 \(O(1)\) 次找到）。定义 \(\mathbf i\)，满足 \(\mathbf i^2 = a^2 - c\)。则 \(x_1=(a+\mathbf i)^{(p+1)/2}\)，另一个解是它的相反数。
扩展欧几里得
LL mod(LL x, LL m) { return (x % m + m) % m; }
LL exgcd(LL a, LL b, LL c, LL& x, LL& y) {
if (!b) return x = c / a, y = 0, a;
LL res = exgcd(b, a % b, c, y, x);
return y -= a / b * x, res;
}
LL solve(LL a, LL b, LL c) {
LL x, y, d = exgcd(a, b, c, x, y);
return c % d == 0 ? mod(x, b / d) : -1;
}
调用 solve(a, b, c) 能求得 \(ax+by=c\) 中 \(x\) 的最小非负整数解，无解返回 \(−1\)。
CRT
适用范围：\(a_1,a_2,\cdots,a_n\) 两两互质。
做法：令 \(M=\prod a_i,m_i=M/a_i\)，然后 \(t_i\) 是 \(m_i\) 在模 \(a_i\) 意义下的逆元。
答案是 \(x=\sum b_im_it_i\)。对 \(M\) 取模。
乘法逆元
线性求逆元：需要逆元存在，\(x^{-1}\equiv -\left\lfloor P/x\right\rfloor(P\bmod x)^{-1}\pmod P\)。
原根
欧拉定理：对于 \((a,m)=1\)，\(a^{\varphi(m)}\equiv 1\pmod m\)。
一个数模 \(m\) 的阶存在，那么它一定是 \(\varphi(m)\) 的约数。
模 \(m\) 的原根：模 \(m\) 的阶为 \(\varphi(m)\) 的数。设为 \(g\)。\(m\) 是质数时，\(g^t\) 和 \([1,m-1]\) 形成双射。
一个数 \(m\) 存在原根当且仅当 \(m=2,4,p^a,2p^a\) 其中 \(p\) 为奇素数。最小原根的大小为 \(O(m^{\frac{1}{4}})\)。
Lucas
对于质数 \(P\) 有
\[\binom n m\equiv \binom{\left\lfloor n/P\right\rfloor}{\left\lfloor m/P\right\rfloor}\binom{n\bmod P}{m\bmod P}\pmod P. \]数论（整除）
整除分块
LL division_block(LL n){
LL res = 0;
for(LL l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
res += n / l * (r - l + 1);
}
return res;
}
杜教筛
若 \(f*g=h\)，则（大写表示前缀和）
\[H(n)=\sum_{i=1}^nf(i)G(n/i) \]如果预处理 \(O(n^{2/3})\) 的函数 \(F\) 点值（注意一定要预处理）那么复杂度为 \(O(n^{2/3})\)。
万能欧几里得
\[\text{solve}(p, q, r, l, U, R) =\begin{cases} \varnothing, \text{when}\ l=0; \\ \text{solve}(p\bmod q, q, r, l, U, U^{\left\lfloor p/q\right\rfloor}R), \text{when}\ p\geq q;\\ \text{let}\ m=\left\lfloor\dfrac{pl+r}{q}\right\rfloor\ \text{in}\begin{cases} R^l, \text{when}\ m=0;\\ R^{\left\lfloor(q-r-1)/p\right\rfloor}U\cdot \text{solve}(q, (q-r-1)\bmod p, p, m-1, R, U)\\ \quad\quad \times R^{l-\left\lfloor(qm-r-1)/p\right\rfloor}, \text{otherwise}. \end{cases} \end{cases} \]组合数学
NTT 模数
- \(167772161 = 5 \times 2^ {25} + 1\) 的原根为 $ g = 3$。
- \(469762049 = 7 \times 2^ {26} + 1\) 的原根为 $ g = 3$。
- \(998244353 = 119 \times 2^ {23} + 1\) 的原根为 $ g = 3$。
- \(1004535809 = 479 \times 2^ {21} + 1\) 的原根为 $ g = 3$。
Chirp Z-Transform
\[ij=\binom{i+j}{2}-\binom i 2-\binom j 2 \]二项式系数恒等式
| 名称 | 公式 | 限制 |
|---|---|---|
| 阶乘展开式 | \(\displaystyle\binom n k=\frac{n!}{k!(n-k)!}\) | 整数 \(n\geq k\geq 0\) |
| 对称恒等式 | \(\displaystyle\binom n k=\binom n {n-k}\) | 整数 \(n\geq 0\)，\(k\) 为整数 |
| 吸收/提取恒等式 | \(\displaystyle\binom n k=\frac{n}{k}\binom{n-1}{k-1}=\frac{k+1}{n+1}\binom{n+1}{k+1}\) | 整数 \(k\neq 0\) |
| 加法/归纳恒等式 | \(\displaystyle\binom n k=\binom{n-1}{k}+\binom{n-1}{k-1}\) | \(k\) 为整数 |
| 上指标反转 | \(\displaystyle\binom {-n} k=(-1)^k\binom{n+k-1}{k}\) | \(k\) 为整数（正负上指标的转换） |
| 三项式版恒等式 | \(\displaystyle\binom n m\binom m k=\binom n k\binom{n-k}{m-k}=\binom{n}{n-m, m-k, k}\) | \(m,k\) 为整数 |
| 二项式定理 | \(\displaystyle\sum_k\binom n k x^k y^{n-k}=(x+y)^n\) | 整数 \(n\geq 0\) 或 \(\text{abs}(x/y)<1\) |
| 平行求和法 | \(\displaystyle\sum_{k\leq m}\binom{k+n}{k}=\binom{n+m+1}{m}\) | \(n\) 为整数 |
| 上指标求和 | \(\displaystyle\sum_{0\leq k\leq n}\binom k m=\binom{n+1}{m+1}\) | 整数 \(n,m\geq 0\) |
| 范德蒙德卷积 | \(\displaystyle\sum_k \binom r k\binom{s}{n-k}=\binom{r+s}{n}\) | \(n\) 为整数 |
| 补充：三项式系数 | \(\displaystyle\binom{n+m+k}{n,m,k}=\frac{(n+m+k)!}{n!\ m!\ k!}\) | \(n, m, k\) 为整数 |
字符串（线性算法）
kmp
void kmp(char *s, int fail[]) {
int n = strlen(s + 1);
fail[1] = 0;
for (int i = 2, j = 0; i <= n; i++) {
while (j && s[j + 1] != s[i]) j = fail[j];
j += s[j + 1] == s[i];
fail[i] = j;
}
}
exkmp
void exkmp(int len) {
z[1] = len;
for (int i = 2, l = 0, r = 0; i <= len; i++) {
if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
while (i + z[i] <= len && a[1 + z[i]] == a[i + z[i]]) ++z[i];
if (i + z[i] - 1 > r) r = i + z[l = i] - 1;
}
}
manacher
void manacher() {
for (int i = 1, mid = 0, r = 0; i <= n; i++) {
if (i <= r) pal[i] = min(pal[mid * 2 - i], r - i + 1);
while (a[i - pal[i]] == a[i + pal[i]]) ++pal[i];
if (i + pal[i] - 1 > r) r = i + pal[mid = i] - 1;
}
}
lyndon 分解
输出所有右端点的异或和。
for (int i = 0; i < n; ) {
int j = i, k = i + 1;
while (k < n && str[j] <= str[k]) {
if (str[j] < str[k]) j = i;
else j++;
k++;
}
while (i <= j) ans ^= i + k - j, i += k - j;
}
字符串（自动机）
| 自动机 | 状态集合 | Link 树（若 \(link_y=x\)） |
|---|---|---|
| SAM | 原串的所有子串 | 则等价类 \(x\) 是等价类 \(y\) 的后缀 |
| ACAM | 所有字符串的前缀 | 则前缀 \(x\) 是前缀 \(y\) 的后缀 |
| PAM | 所有回文串 | 则回文子串 \(x\) 是回文子串 \(y\) 的后缀 |
广义 SAM
广义 SAM 使用 `unordered_map` 存转移边
template <int N>
struct suffixam {
unordered_map<int, int> ch[N << 1];
int tot, link[N << 1], len[N << 1];
suffixam() : tot(1) {
ch[1].clear();
len[1] = link[1] = 0;
}
int split(int p, int q, int r) {
if (len[q] == len[p] + 1) return q;
int u = ++tot;
len[u] = len[p] + 1;
ch[u] = ch[q];
link[u] = link[q];
link[q] = u;
for (; p && ch[p][r] == q; p = link[p]) ch[p][r] = u;
return u;
}
int expand(int p, int r) {
if (ch[p][r]) return split(p, ch[p][r], r);
int u = ++tot;
len[u] = len[p] + 1;
ch[u].clear();
for (; p; p = link[p]) {
if (ch[p][r]) {
link[u] = split(p, ch[p][r], r);
return u;
} else {
ch[p][r] = u;
}
}
link[u] = 1;
return u;
}
template <bool rev>
vector<int> bucketsort() {
vector<int> per(tot), buc(tot + 1);
for (int i = 1; i <= tot; i++) buc[len[i]] += 1;
for (int i = 1; i <= tot; i++) buc[i] += buc[i - 1];
for (int i = 1; i <= tot; i++) per[--buc[len[i]]] = i;
if (rev) reverse(per.begin(), per.end());
return per;
}
};
倍增后缀数组
点击查看代码（完全 vector）
vector<int> get_sa(const string& a) {
int n = a.size();
vector<int> sa(n), rk(a.begin(), a.end()), h(n);
auto bucketsort = [&](const auto& key) {
vector<int> buc(max(n, 128));
reverse(h.begin(), h.end());
for (int i : h) buc[rk[i]] += 1;
partial_sum(buc.begin(), buc.end(), buc.begin());
for (int i : h) sa[--buc[rk[i]]] = i;
vector<int> tmp(n);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) != key(sa[i]));
rk = move(tmp);
};
for (int i = 0; i < n; i++) h[i] = i;
bucketsort([&](int x) { return rk[x]; });
for (int j = 1; j < n; j <<= 1) {
h.clear();
for (int i = n - j; i < n; i++) h.push_back(i);
for (int i = 0; i < n; i++) if (sa[i] >= j) h.push_back(sa[i] - j);
bucketsort([&](int x) { return make_pair(rk[x], x + j < n ? rk[x + j] : -1); });
}
return sa;
}
vector<int> get_lcp(const string& a, const vector<int>& sa) {
int n = a.size();
vector<int> rk(n), lcp(n - 1);
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0, h = 0; i < n; i++) {
if (!rk[i]) continue;
if (h) h -= 1;
int j = sa[rk[i] - 1];
while (max(i, j) + h < n && a[i + h] == a[j + h]) h += 1;
lcp[rk[i] - 1] = h;
}
return lcp;
}
PAM
点击查看代码
template <int N, int M>
struct palindam {
int str[N + 10], cnt, ch[N + 10][M], fail[N + 10], len[N + 10], dep[N + 10], tot;
palindam() : cnt(0), tot(1) {
memset(ch[0], 0, sizeof ch[0]);
memset(ch[1], 0, sizeof ch[1]);
fail[0] = 1;
len[1] = -1; str[0] = -1;
}
int getfail(int p) {
while (cnt - len[p] - 1 < 1 || str[cnt - len[p] - 1] != str[cnt])
p = fail[p];
return p;
}
int expand(int p, int r) {
str[++cnt] = r;
p = getfail(p);
if (ch[p][r]) return ch[p][r];
int u = ++tot;
memset(ch[u], 0, sizeof ch[u]);
len[u] = len[p] + 2;
fail[u] = ch[getfail(fail[p])][r];
dep[u] = dep[fail[u]] + 1;
ch[p][r] = u;
return u;
}
};
// 插入从 lst = 1 或 lst = 0 开始都对
AC 自动机
点击查看代码
```cpp void build() { queue（等号右面的是一样的东西）
数据结构（平衡树）
分裂合并 WBLT
点击查看代码
template <int N>
struct wblt {
int ch[N << 1][2], tsh[N << 1], tot = 0, cnt = 0, siz[N << 1], val[N << 1];
int newnode(int v) {
int p = cnt ? tsh[cnt--] : ++tot;
ch[p][0] = ch[p][1] = 0, siz[p] = 1, val[p] = v, maintain(p);
return p;
}
bool isleaf(int p) { return !ch[p][0]; }
void maintain(int p) {
if (isleaf(p)) return ;
val[p] = val[ch[p][1]], siz[p] = siz[ch[p][0]] + siz[ch[p][1]];
}
int mg(int p, int q) {
if (!p || !q) return p + q;
int lim = 0.292 * (siz[p] + siz[q]);
if (min(siz[p], siz[q]) >= lim) {
int t = newnode(val[p]);
ch[t][0] = p, ch[t][1] = q;
return maintain(t), t;
}
if (siz[p] >= siz[q]) {
// pushdown(p);
auto [x, y] = ch[tsh[++cnt] = p];
if (siz[x] >= lim) return mg(x, mg(y, q));
// pushdown(y);
auto [y0, y1] = ch[tsh[++cnt] = y];
return mg(mg(x, y0), mg(y1, q));
} else {
// pushdown(q);
auto [x, y] = ch[tsh[++cnt] = q];
if (siz[y] >= lim) return mg(mg(p, x), y);
auto [x0, x1] = ch[tsh[++cnt] = x];
// pushdown(x);
return mg(mg(p, x0), mg(x1, y));
}
}
void sp(int p, int k, int& x, int& y) {
if (!k) return x = 0, y = p, void();
if (isleaf(p)) return x = p, y = 0, assert(k == 1);
// pushdown(p);
if (k <= siz[ch[p][0]]) sp(ch[p][0], k, x, y), y = mg(y, ch[p][1]);
else sp(ch[p][1], k - siz[ch[p][0]], x, y), x = mg(ch[p][0], x);
tsh[++cnt] = p;
}
void spv(int p, int v, int& x, int& y) {
if (val[p] <= v) return x = p, y = 0, void();
if (isleaf(p)) return x = 0, y = p, void();
// pushdown(p);
if (v < val[ch[p][0]]) spv(ch[p][0], v, x, y), y = mg(y, ch[p][1]);
else spv(ch[p][1], v, x, y), x = mg(ch[p][0], x);
tsh[++cnt] = p;
}
int getkth(int p, int k) {
while (!isleaf(p)) {
// pushdown(p);
if (k <= siz[ch[p][0]]) p = ch[p][0];
else k -= siz[ch[p][0]], p = ch[p][1];
}
return val[p];
}
void dfs(int p, int &lst) {
if (!isleaf(p)) dfs(ch[p][0], lst), dfs(ch[p][1], lst);
else assert(exchange(lst, val[p]) <= val[p]);
}
};
fhqtreap
点击查看代码
mt19937 rng(random_device{}());
template <int N>
struct fhqtreap {
int ch[N + 10][2], tot, val[N + 10], pri[N + 10], siz[N + 10], x, y, z, root;
int newnode(int v) {
int p = ++tot;
return ch[p][0] = ch[p][1] = 0, pri[p] = rng(), val[p] = v, siz[p] = 1, p;
}
void maintain(int p) { siz[p] = siz[ch[p][0]] + 1 + siz[ch[p][1]]; }
fhqtreap() : tot(-1), root(0) { newnode(0), siz[0] = 0; }
int merge(int p, int q) {
if (!p || !q) return p + q;
if (pri[p] < pri[q])
return ch[p][1] = merge(ch[p][1], q), maintain(p), p;
else
return ch[q][0] = merge(p, ch[q][0]), maintain(q), q;
}
void split(int p, int v, int &x, int &y) {
if (!p) return x = y = 0, void();
if (val[p] <= v)
x = p, split(ch[p][1], v, ch[p][1], y), maintain(p);
else
split(ch[p][0], v, x, ch[p][0]), y = p, maintain(p);
}
int find(int v, int p) {
if (val[p] == v) return p;
return val[p] <= v ? find(v, ch[p][1]) : find(v, ch[p][0]);
}
void insert(int v) {
split(root, v, x, y);
root = merge(x, merge(newnode(v), y));
}
void erase(int v) {
split(root, v - 1, x, y), split(y, v, y, z);
root = merge(merge(x, ch[y][0]), merge(ch[y][1], z));
}
int getrnk(int v) {
split(root, v - 1, x, y);
int res = siz[x] + 1;
root = merge(x, y);
return res;
}
int getkth(int k, int p) {
int c = siz[ch[p][0]] + 1;
if (c == k)
return val[p];
else
return c < k ? getkth(k - c, ch[p][1]) : getkth(k, ch[p][0]);
}
int getpre(int v) {
split(root, v - 1, x, y);
int p = x;
while (ch[p][1]) p = ch[p][1];
root = merge(x, y);
return val[p];
}
int getsuf(int v) {
split(root, v, x, y);
int p = y;
while (ch[p][0]) p = ch[p][0];
root = merge(x, y);
return val[p];
}
};
splay & lct
点击查看代码
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
template <int N>
struct lctree {
int val[N + 10], sum[N + 10], fa[N + 10], ch[N + 10][2], rev[N + 10];
bool getson(int p) { return ch[fa[p]][1] == p; }
bool isroot(int p) { return !p || ch[fa[p]][getson(p)] != p; }
void maintain(int p) { sum[p] = val[p] ^ sum[ch[p][0]] ^ sum[ch[p][1]]; }
void pushdown(int p) {
if (rev[p])
swap(ch[p][0], ch[p][1]), rev[ch[p][0]] ^= 1, rev[ch[p][1]] ^= 1,
rev[p] ^= 1;
}
void update(int p) {
if (!isroot(p)) update(fa[p]);
pushdown(p);
}
void connect(int p, int q, int r) { fa[p] = q, ch[q][r] = p; } // p->q
void rotate(int p) {
int f = fa[p], r = getson(p);
if (fa[p] = fa[f], !isroot(f)) connect(p, fa[f], getson(f));
connect(ch[p][r ^ 1], f, r), connect(f, p, r ^ 1), maintain(f), maintain(p);
}
void splay(int p) {
for (update(p); !isroot(p); rotate(p))
if (!isroot(fa[p])) rotate(getson(p) == getson(fa[p]) ? fa[p] : p);
}
int access(int p) {
int y = 0;
for (; p; p = fa[y = p]) splay(p), ch[p][1] = y, maintain(p);
return y;
}
void makeroot(int p) { access(p), splay(p), rev[p] ^= 1; }
int findroot(int p) {
access(p), splay(p);
while (ch[p][0]) p = ch[p][0];
return p;
}
void split(int x, int y) { makeroot(x), access(y), splay(y); }
void link(int x, int y) { makeroot(x), fa[x] = y; }
void cut(int x, int y) {
split(x, y);
if (fa[x] == y && !ch[x][1]) fa[x] = ch[y][0] = 0;
maintain(y);
}
void modify(int x, int y) { splay(x), val[x] = y, maintain(x); }
int lca(int x, int y) { return access(x), access(y); }
};
int n, m;
lctree<100010> t;
int main() {
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &t.val[i]), t.sum[i] = t.val[i];
for (int i = 1, op, x, y; i <= m; i++) {
scanf("%d%d%d", &op, &x, &y);
switch (op) {
case 0:
t.split(x, y), printf("%d\n", t.sum[y]);
break;
case 1:
if (t.findroot(x) != t.findroot(y)) t.link(x, y);
break;
case 2:
if (t.findroot(x) == t.findroot(y)) t.cut(x, y);
break;
case 3:
t.modify(x, y);
}
}
return 0;
}
数据结构（更多的树）
左偏树
template <int N, class T>
struct leftree {
int ch[N + 10][2], dis[N + 10], tot;
T val[N + 10];
leftree() : tot(0) { dis[0] = -1; }
int newnode(T x) {
int p = ++tot;
return val[p] = x, ch[p][0] = ch[p][1] = 0, dis[p] = 0, p;
}
int merge(int p, int q) {
if (!p || !q) return p + q;
if (val[p].first > val[q].first) swap(p, q);
ch[p][1] = merge(ch[p][1], q);
if (dis[ch[p][0]] < dis[ch[p][1]]) swap(ch[p][0], ch[p][1]);
dis[p] = dis[ch[p][1]] + 1;
return p;
}
};
李超树
template <class T>
struct func {
T k, b;
func(T k = 0, T b = 0) : k(k), b(b) {}
T operator()(T x) { return k * x + b; }
};
template <int N, class T>
struct lcstree {
func<T> tag[N + 10];
int ch[N + 10][2], tot;
lcstree() : tot(-1) { newnode(); }
int newnode() {
int p = ++tot;
return ch[p][0] = ch[p][1] = 0, tag[p] = func<T>(), p;
}
void insert(func<T> f, int &p, int l = 1, int r = 4e8) {
if (!p) p = newnode();
int mid = (l + r) >> 1;
switch ((f(l) <= tag[p](l)) + (f(r) <= tag[p](r))) {
case 0:
tag[p] = f;
break;
case 1:
insert(f, ch[p][0], l, mid), insert(f, ch[p][1], mid + 1, r);
break;
}
}
T query(int x, int &p, int l = 1, int r = 4e8) {
if (!p) return 0;
int mid = (l + r) >> 1;
if (x <= mid)
return max(tag[p](x), query(x, ch[p][0], l, mid));
else
return max(tag[p](x), query(x, ch[p][1], mid + 1, r));
}
};
计算几何
叉乘
T cross(const point &lhs, const point &rhs) { //叉积
return lhs.x * rhs.y - rhs.x * lhs.y;
}
凸包
vector<dot> convexHull(vector<dot> a) { //凸包
static dot stk[1 << 18];
dot cen = *min_element(a.begin(), a.end());
sort(a.begin(), a.end(),
[&](const dot &a, const dot &b) { return cmp(a - cen, b - cen); });
int top = 0;
for (dot v : a) {
while (top >= 2 && cross(stk[top - 1] - stk[top], v - stk[top]) > 0) top--;
stk[++top] = v;
}
return vector<dot>(stk + 1, stk + top + 1);
}
bool operator<(const point &a, const point &b) {
return a.x != b.x ? a.x < b.x : a.y < b.y;
}
auto makeConvex(vector<dot> vec) { // 另一个版本，需要删掉三点共线，得到一侧凸包
// assert(is_sorted(vec.begin(), vec.end()));
vector<dot> ret;
for (dot p : vec) {
while (ret.size() >= 2 && cross(ret.end()[-2] - ret.back(), p - ret.back()) <= 0) ret.pop_back();
ret.push_back(p);
}
return ret;
}
minkowski
vector<dot> minkowski(const vector<dot> &a,
const vector<dot> &b) { //闵可夫斯基和
vector<dot> c = {a[0] + b[0]};
static dot sa[1 << 18], sb[1 << 18];
int n = a.size(), m = b.size();
for (int i = 0; i < n; i++) sa[i] = a[(i + 1) % n] - a[i];
for (int i = 0; i < m; i++) sb[i] = b[(i + 1) % m] - b[i];
int i = 0, j = 0;
for (int k = 1; k < n + m; k++) {
if (i < n && (j >= m || cmp(sa[i], sb[j])))
c.push_back(c.back() + sa[i++]);
else
c.push_back(c.back() + sb[j++]);
}
return c;
}
auto minkowski(vector<dot> a, vector<dot> b) { // 另一个版本，注意必须叉掉三点共线
if (a.empty())
return b;
if (b.empty())
return a;
for (int i = (int)a.size() - 1; i >= 1; i--) a[i] = a[i] - a[i - 1];
for (int i = (int)b.size() - 1; i >= 1; i--) b[i] = b[i] - b[i - 1];
vector<dot> c = { a[0] + b[0] };
merge(a.begin() + 1, a.end(), b.begin() + 1, b.end(), back_inserter(c),
[](dot p, dot q) { return cross(p, q) < 0; });
for (int i = 1; i < (int)c.size(); i++) c[i] = c[i - 1] + c[i];
return c;
}
图论
有向图缩点 / 强连通分量（SCC）
点击查看代码
int dfn[1010],low[1010],stk[1010],col[1010],cnt,top,tot;
void reset(){
cnt=0;
tot=0;
memset(dfn,0,sizeof dfn);
memset(col,0,sizeof col);
}
void tarjan(int u){
low[stk[++top]=u]=dfn[u]=++cnt;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(!col[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
col[u]=++tot;
while(stk[top]!=u) col[stk[top--]]=tot;
top--;
//do col[stk[top]]=css; while(stk[top--]!=u);
}
}
补充：instack 问题。scc 中访问到 dfs 过的点时必须需要判断是否在栈内（不在栈中时更新 low）。点双、边双好像没有这个要求，不过判了更好。
边双连通分量（ECC）
边双的定义：两个点 \(u, v\) 在无向图上连通，若删去图中的任意一条边，都不能使他们不连通，则说 \(u, v\) 边双连通。边双联通具有传递性。
在缩点的基础上，强制不让它走到父亲边即可。\(dfn_u=low_u\)。
我不知道为什么正经的做法都说是 \(low_v>dfn_u\)。但是这个代码真的能过。
点击查看代码
graph<500010,2000010> g;
int dfn[500010],low[500010],stk[500010],cnt,top,col[500010],dcc,siz[500010];
bool vis[2000010<<1];
void tarjan(int u){
dfn[u]=low[stk[++top]=u]=++cnt;
for(int i=g.head[u];i;i=g.nxt[i]){
if(vis[i]||vis[i^1]) continue;
int v=g[i].v;
if(!dfn[v]) vis[i]=vis[i^1]=1,tarjan(v),low[u]=min(low[u],low[v]);
else low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
col[u]=++dcc;
do col[stk[top]]=dcc; while(stk[top--]!=u);
}
}
点双连通分量（BCC）
点双的定义：两个点 \(u, v\) 在无向图上连通，若删去图中的任意一个不是 \(u, v\) 的点，都不能使他们不连通，则说 \(u, v\) 点双连通。点双联通不一定有传递性。
无向图割点的条件为：\(low_v\geq dfn_u\)，这样 \(v\) 这个儿子就走不到 \(u\)，割掉 \(u\)，\(v\) 就过不来了。
点双和割点一样的。但是为了求出点双连通分量需要开一个栈，还要注意一个点可能在多个点双内。
点击查看代码
graph<500010,2000010> g,t;
int dfn[500010],low[500010],stk[500010],cnt,top;
int dcc,cut[500010],siz[500010];
void tarjan(int u){
dfn[u]=low[stk[++top]=u]=++cnt,cut[u]=1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(!dfn[v]){
tarjan(v),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
cut[u]++,dcc++;
do t.add(dcc,stk[top]); while(stk[top--]!=v);
t.add(dcc,u);
}
}else low[u]=min(low[u],dfn[v]);
}
if(!g.head[u]) t.add(++dcc,u);
}
树论
虚树
void buildVTree(vector<int> h) {
static int vis[1 << 18], tim = 0, stk[1 << 18];
if (h.empty()) return;
++tim;
sort(h.begin(), h.end(), [&](int u, int v) { return dfn[u] < dfn[v]; });
bool flag = 0;
if (h[0] != 1)
h.insert(h.begin(), 1);
else
flag = 1;
h.erase(unique(h.begin(), h.end()), h.end());
auto link = [&](int u, int v) {
if (vis[u] < tim) vis[u] = tim, t[u].clear();
if (vis[v] < tim) vis[v] = tim, t[v].clear();
t[u].emplace_back(v, getDist(u, v));
t[v].emplace_back(u, getDist(u, v));
};
int top = 0;
stk[++top] = h[0];
for (int i = 1; i < h.size(); i++) {
int k = getLca(stk[top], h[i]);
if (k != stk[top]) {
while (top >= 2 && dfn[stk[top - 1]] > dfn[k])
link(stk[top - 1], stk[top]), --top;
if (stk[top - 1] == k)
link(stk[top], k), --top;
else
link(stk[top], k), stk[top] = k;
}
stk[++top] = h[i];
}
while (top >= 3) link(stk[top - 1], stk[top]), --top;
if (top >= 2 && (flag || vis[1] == tim)) link(stk[top - 1], stk[top]);
}
void build(int h[], int m) {
t.tag++, t.cnt = 0;
for (int i = 1; i <= m; i++) vis[h[i]] = t.tag;
auto link = [&](int u, int v) { if (dep[u] < dep[v]) swap(u, v); t.link(u, v, query(u, dep[u] - dep[v])); };
h[++m] = 1;
sort(h + 1, h + m + 1, [&](int i, int j) { return dfn[i] < dfn[j]; });
for (int i = 1; i < m; i++) h[m + i] = lca(h[i], h[i + 1]);
m += m - 1;
sort(h + 1, h + m + 1, [&](int i, int j) { return dfn[i] < dfn[j]; });
m = unique(h + 1, h + m + 1) - h - 1;
for (int i = 2; i <= m; i++) link(h[i], lca(h[i], h[i - 1]));
}
LCA
int n, m, dfn[100010], ST[20][100010], dep[100010], rnk[100010], cnt;
basic_string<int> g[100010];
bool cmp(int u, int v) { return dfn[u] < dfn[v]; }
void dfs(int u, int fa) {
dfn[u] = ++cnt, rnk[cnt] = u, ST[0][cnt] = fa, dep[u] = dep[fa] + 1;
for (int v : g[u]) if (v != fa) dfs(v, u);
}
int lca(int u, int v) {
if (u == v) return u;
auto [l, r] = minmax(dfn[u], dfn[v]);
int k = 31 - __builtin_clz(r - l);
return min(ST[k][l + 1], ST[k][r - (1 << k) + 1], cmp);
}
int main() {
cin >> n >> m;
for (int i = 1, u, v; i < n; i++) cin >> u >> v, g[u] += v, g[v] += u;
dfs(1, 0);
for (int j = 1; 1 << j <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
ST[j][i] = min(ST[j - 1][i], ST[j - 1][i + (1 << (j - 1))], cmp);
}
}
// ...
}