本文将介绍一种平衡树

复杂度我不会证

实现非常简单

首先，树上差分是从子节点推到根节点，定义 $d$ 差分数组

若修改 $(x,y)$ 路径上的点权，则 $d_x, d_y \mathrel{+}= k, d_{\mathrm{lca}}, d_{\mathrm{fa}_{\mathrm{lca}}} \mathrel{-}= k$

1
2
3
4
5
6

void dfs(int u){
    val[u] = d[u];
    for (auto v : g[u]){
        dfs(v), val[u] += val[v];
    }
}

若修改 $(x,y)$ 路径上的边权，则 $d_x, d_y \mathrel{+}= k, d_{\mathrm{lca}}\mathrel{-}= 2k$

1
2
3
4
5
6
7
8

int dfs(int u){
    int ret = d[u];
    for (auto i : g[u]){
        i.w = dfs(i.v);
        ret += i.w;
    }
    return ret;
}

P3128 最大流

这是一个复杂度为 $O(n+q)$ 的离线求 LCA 算法

用 dfs 进行遍历并打 tag

假设遍历到 $u$，则已回溯的节点标为 $2$，遍历到但未回溯的节点（即 $u$ 和 $u$ 的祖先）标 $1$，其余为 $0$

现在假设 $u$ 的子树处理完毕，考虑 $u$ 的处理

询问节点为 $(u, v)$

此时，若 $\mathrm{tag}_v = 2$，则可以保证 $v$ 向根走遇到的第一个 $\mathrm{tag} = 1$ 的节点即为 $\mathrm{LCA}(u,v)$，可以用反证法证明

下面的程序复杂度应该没有问题，但是要卡一下常，吸一口氧才能过

¶ 数学

¶ 费马小定理

对于素数 $p$ 必存在

所以可以随机选取 $a\in[2,n-1]$ 检验是否满足上式，若不满足，则必然是合数

遗憾的是，存在无穷多个 $n$，可以满足

也就是说使费马判素失效

¶ 二次探测定理

素数 $p$ 必满足方程

有且仅有两个解

¶ 实现

把 $n-1$ 分解成 $d\cdot2^t$ 使 $t$ 尽量大

然后 $x\equiv base^{d} \pmod{n}$

然后不断进行二次探测

即如果满足 $x\not\equiv 1$ 且 $x\not\equiv n-1$ 且 $x^2\equiv 1$ 那么这个数解不是素数了

最后进行费马判素

1
2
3
4
5
6
7
8
9
10
11
12
13

bool miller_rabin(ll n) {
    if (n <= 2) return n == 2;
    int d = n - 1, t = 0;
    while (d % 2 == 0) d /= 2, ++t;
    rep(i, 0, T) { // T 是测试次数, p 是测试基
        ll x = ksm(p[i] % (n - 2) + 2, d, n);
        if (x == 1 || x == n - 1) continue; // 无效的二次探测
        for (int j = 0; j < t; ++j, x = x * x % n)
            if (x != n - 1 && x != 1 && x * x % n == 1) return 0;
        if (x != 1) return 0; // 费马判素
    }
    return 1;
}

这是测试基选择的推荐

¶ 概述

这是一种随机算法

模仿鸟类捕食

在定义域中随机撒 $n$ 个点，需要维护（以二维定义域为例）

• 坐标 $p(x,y)$
• 速度 $v$ ，一个二维向量
• 历史最优值 $pb$ 和其坐标

同时还要维护全局最优解及其坐标

¶ 概述

你有一个字符串 $s$ 你有一个神奇的函数 $f$ 可以使

• $f(s)\in R$
• $s_1 \neq s_2$ 时基本上不会出现 $f(s_1)=f(s_2)$

一种常见的 $f$ 构造方法是

简介

对于这样一类题目：给定一棵 $n$ 点树，有 $q$ 个询问，每个询问关于树上 $k_i$ 个点， $n,q,\sum k \leq 10^5$

朴素做法 $O(qn)$

由于一些题目的特殊，发现求解只需保留树的结构，故可以重构一棵虚树

虚树包含了所有的 $k$ 个关键点和它们两两之间的 LCA，这样可以保证这虚树的节点个数 $< 2k$，保证了复杂度

¶ 前置技能

¶ 虚数

¶ 复数

任意复数 $z$ 都可表示为 $a+bi(a,b\in R)$

$a$ 叫做实部，定义 $\mathrm{Re}(z) = a$

$b​$ 叫做虚部，定义 $\mathrm{Im}(z) = b​$

线段树原理非常简单，但如何优雅的实现却是一个问题

¶ 线段树简介

线段树就是把一个序列原有 $n$ 个点扩充为 $n\log n$ 个点，保持一定结构进行加速

每个点有

• 自己管辖的区域
• 两个拼起来是自己的子节点（ $self = lson \cup rson$ ）
• 子节点不交（ $lson \cap rson = \varnothing$ ）
• 可以快速的区间合并

Edmonds-Karp 算法是用来解决最大流和最小费用最大流的常用算法。

¶ 原理

对于一个图（流量/容量）

显然最大流为 $2$