积性函数，莫比乌斯反演（三）

[[ slider_text ]]

[[ item.c ]]

积性函数，莫比乌斯反演（三）

发布时间 2025-04-07 作者：秋千月 来源：算法小站

线段树 树的重心 莫比乌斯反演 矩阵运算 狄利克雷后缀

## 狄利克雷前缀后缀
### 狄利克雷前缀
```math
\displaystyle
a_i^{\prime} = \sum_{d \mid i} a_d
```
直观地来看，类似欧拉筛，每一次只从素数集合，添加一个**最小素因子**
![](/media/content_img/dirichletPrefix.png)

下面来证明
```math
\displaystyle
\sum_{i_1 = 0}^{\alpha_1}\sum_{i_2 = 0}^{\alpha_2} \cdots \sum_{i_k = 0}^{\alpha_k} a(p_1^{i_1}\cdots p_k^{i_k}) = \sum_{i_1 = 0}^{\alpha_1}\sum_{i_2 = 0}^{\alpha_2} \cdots \sum_{i_k = 0}^{\alpha_k} a\left(\dfrac{n}{p_1^{i_1}p_2^{i_2}\cdots p_k^{i_k}} \right)
```

令$$c(n, j) = \sum\_{i\_1=0}^{\alpha\_1} \cdots \sum\_{i\_j = 0}^{\alpha\_j} a\left( \dfrac{n}{p\_1^{i\_1}\cdots p\_j^{i\_j}} \right)$$

```math
\displaystyle
c(n, j+1) = \sum_{i_1 = 0}^{\alpha_1}\cdots \sum_{i_j = 0}^{\alpha_j} \sum_{i_{j+1} = 0}^{\alpha_{j+1}} a\left(\dfrac{n}{p_1^{i_1}p_2^{i_2}\cdots p_j^{i_j} p_{j+1}^{i_{j+1}} }  \right) = \sum_{i_1 = 0}^{\alpha_1}\cdots \sum_{i_j = 0}^{\alpha_j} \sum_{i_{j+1} = 0}^{\alpha_{j+1}} a\left(\dfrac{n / p_{j+1}^{i_{j+1}}}{p_1^{i_1}p_2^{i_2}\cdots p_j^{i_j} }  \right)

\\ = \sum_{i_{j+1} = 0}^{\alpha_{j+1}} \left( \sum_{i_1 = 0}^{\alpha_1} \cdots \sum_{i_j = 0}^{\alpha_j}  a\left(\dfrac{n / p_{j+1}^{i_{j+1}}}{p_1^{i_1}p_2^{i_2}\cdots p_j^{i_j} }  \right)  \right) = \sum_{i_{j+1} = 0}^{\alpha_{j+1}} c\left( \dfrac{n}{p_{j+1}^{i_j+1}}, j \right) = c(n, j) + \sum_{i_{j+1} = 1}^{\alpha_{j+1}} c\left( \dfrac{n}{p_{j+1}^{i_j+1}}, j \right)

\\ = c(n, j) + c\left( \dfrac{n}{p_{j+1}^{i_j+1}}, j+1 \right)
```
仿照欧拉筛
```bash
void solve() {
	欧拉筛打素数表
	
    for (auto p : primes) {
        for (int d = 1; d * p <= n; d++) {
            a[d * p] += a[d];
        }
    }
}
```

### 狄利克雷后缀
狄利克雷后缀，形如$$\displaystyle b\_d = \sum\_{d \mid n} a\_n$$

从大到小递推，先剔除较小的因子，得到较大的数，然后往小的数递推
```bash
for p = 从小到大遍历素数表
	for d = n/p; d >= 1; d--:
		a(d) += a(d * p)
```
狄利克雷后缀和，用来解决诸如
> 一个数组中，值是$$d$$的倍数的数的数量，或者我们需要枚举$$d$$的倍数，求 dp 转移等等

## Codeforces Round 973 (Div. 2)
### E
**[E. Prefix GCD](https://codeforces.com/contest/2013/problem/E)**
这题要求最小化
```math
\displaystyle
\sum_{i = 1}^{n} gcd(a_1, a_2, \cdots, a_i)
```
![](/media/content_img/dirichlet-suf01_pCjYqey.png)
![](/media/content_img/dirichlet-suf02_FKVbyqX.png)

```bash
void solve(int cas) {
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

int G = a[1];
    for (int i = 2; i <= n; i++) G = std::gcd(G, a[i]);
    for (int i = 1; i <= n; i++) a[i] /= G;

int M = *max_element(a.begin()+1, a.end());
    vector<int> exist(M+5, 0);
    for (int i = 1; i <= n; i++) exist[a[i]] += 1;

vector<vector<int> > fac(M+5);
    vector<int> cnt(M+5, 0);
    for (int y = 1; y <= M; y++) {
        for (int x = y; x <= M; x += y) {
            fac[x].emplace_back(y);
            if (exist[x]) cnt[y] += 1;
        }
    }

vector<i64> dp(M+5, inf<i64>), last(M+5, inf<i64>);
    vector<int> g(M+5, 0);

for (int x = 1; x <= M; x++) if (exist[x]) dp[x] = x;
    i64 ans = inf<i64>;
    chmin(ans, dp[1] + n - 1);

const int LOG = 15;
    for (int i = 2; i <= min(LOG, n); i++) {
        last = dp, dp.assign(M+5, inf<i64>);
        
        for (int x = 1; x <= M; x++) {
            if (last[x] >= inf<i64>) continue;

for (auto y : fac[x]) g[y] = cnt[y];
            for (int k = fac[x].size()-1; k >= 0; k--) {
                auto y = fac[x][k];

if (g[y] > 0) {
                    chmin(dp[y], last[x] + y);
                }

for (auto d : fac[y]) {
                    if (d == y) continue;
                    g[d] -= g[y];
                }
            }
        }

i64 res = dp[1] + n - i;
        chmin(ans, res);
    }

//debug(G);
    ans *= G;

cout << ans << "\n";
}
```

> 不难发现，狄利克雷后缀的关键在于 g 函数如何求
求狄利克雷后缀，不如说就是求 g

对于当前正在考虑的前缀 gcd 假设是$$x$$，考虑什么时候 gcd 能从$$x \to y$$
注意到$$y \mid x$$，$$y$$一定是$$x$$的一个因子
1）初始化，`for y in (x 的所有的因子)`，$$g(y) \leftarrow cnt(y)$$
2）**从大到小检查可能的**$$y$$，如果`g(y) > 0`，说明存在合法的$$a_i$$，能够让 gcd 从$$x \to y$$
转移$$dp(x) \to dp(y)$$
然后考虑 **update**，枚举$$y$$的所有因子$$d$$，`for d in (y 的所有因子)`，$$g(d) = g(d) - g(y)$$

## Codeforces Round 757 (Div. 2)
### D2
**[D2. Divan and Kostomuksha (hard version)](https://codeforces.com/contest/1614/problem/D2)**
**问题描述**
给定数组$$a$$，可以对它重新排序，要求**最大化**前缀 gcd 和
```math
\sum_{i = 1}^{n} \text{gcd}(a_1, a_2, \cdots, a_i)
```

**算法分析**
不难发现，$$\text{gcd}(a_1, a_2) \geqslant \text{gcd}(a_1, a_2, a_3)$$，可以发现，前缀`gcd`是非严格单调递降的
我们枚举`gcd = d`，那么不难发现，前缀$$\\{a_1, a_2, \cdots a_i\\} = \\{md, (m-1)d, \cdots, d\\}$$
其中$$i \geqslant m$$，因为中间可能有若干个相同的$$\\{md, \cdots, ?d, ?d, \cdots, d\\}$$

也就是说，前缀`gcd`的和大致可以表示成$$\displaystyle \sum\_{d \mid d^{\prime}, 1\leqslant d^{\prime} \leqslant maxv} dp(d^{\prime})$$

> 可以枚举$$d$$作为`gcd`，那么它对答案的贡献是多少？

不难发现，前缀`gcd`**非严格单调减**，那么`d 的贡献 = d * [以 d 作为 gcd 的个数]`
假设前缀$$a[1, l] \cdots a[1, r]$$均以$$d$$作为`gcd`，那么$$[1\cdots l-1]$$的`gcd`大致是$$[md, \cdots, 3d, 2d]$$
另外，$$[r+1\cdots n]$$这些位置以`d`的因子作为`gcd`

> 能不能用狄利克雷后缀求解？

考虑狄利克雷后缀，记$$cnt(d)$$表示**有多少个数是$$d$$的倍数**，那么可以扫描前缀的时候维护出来
我们有$$\sum\_{d \mid d'} cnt(d')$$
```bash
// 初始化
for i = 1 to n:
	cnt[ a[i] ] += 1
	
// 求解狄利克雷后缀
for p in primes:
	for d = maxv/p,  d >= 1, d--
		cnt[d] += cnt[d * p]
```

那么，以$$d$$作为`gcd`的数的个数，考虑**从大到小枚举$$d$$**，考虑 Dirichlet 后缀
每次转移的时候，只剔除一个最小素因子，然后转移，具体来说
```bash
for d 从大到小枚举
	for p in primes, p 是未被考虑过的最小素数
		cnt(d) - cnt(d * p) 就是 [d 作为 gcd 的个数]
```

这样，就可以根据 **Dirichlet 后缀**求解了
一开始的时候$$dp(d) = d \cdot cnt[d]$$，这个时候$$d$$填满了整个前缀

```math
\displaystyle
dp(d) = \max_{d \mid d'} \left( dp(d') + d \cdot ([l\cdots r]\text{均以 d 作为 gcd 的个数}) \right)
\\ = \max_{d \mid d'}(dp(d') + d \cdot (cnt[d] - cnt[d \cdot p]))
```
需要注意的是**Dirichlet 后缀**要从**大到小**枚举

### 狄利克雷后缀算法实现 2
> 这种写法，适用于`a[i]`比较大的情况，一般`a[i] <= 2e7`可以考虑以下写法

```bash
// 接下来的方法适用于值域比较大的情况 |a[i]| <= 2e7 
void solve(int cas) {
    eulerSeive(M);

for (int i = 1; i <= n; i++) g[a[i]] += 1;
    for (auto p : primes) {
        for (int x = M/p; x >= 1; x--) g[x] += g[x * p];
    }

for (int x = M; x >= 1; x--) {
        if (!g[x]) continue;

dp[x] = 1LL * x * g[x];
        for (auto p : primes) {
            if (p * x > M) break;

auto y = p * x;
            i64 w = g[x] - g[x * p];
            chmax(dp[x], dp[y] + x * w);
        }
    }

i64 res = dp[1] * G;
    cout << res << "\n";
}
```

## AGC038 C
**[AGC038 C- LCMs](https://ac.nowcoder.com/acm/contest/22769/D)**
给定一个长度为$$N$$的序列，求$$\displaystyle \sum\_{i = 0}^{N-2}\sum\_{j = i+1}^{N-1}\text{lcm}(a_i, a_j)$$

**算法分析**

> 怎么化简，注意到求和式子，实际上要求$$i \neq j$$，我们可以尝试把$$i = j$$这一项给补上

```math
\displaystyle
\sum_{i = 0}^{n-2} \sum_{j = i+1}^{n-1} lcm(a_i, a_j) = ans \\
\sum_{i = 1}^{n-1} \sum_{j = 0}^{i-1} lcm(a_i, a_j) = ans
```
尝试补上$$i = j$$的项，就有
```math
\displaystyle
\sum_{i = 0}^{n-1} \sum_{j = i+1}^{n-1} lcm(a_i, a_j) = ans + \delta \\
\sum_{i = 0}^{n-1} \sum_{j = 0}^{i-1} lcm(a_i, a_j) = ans + \delta \\
\Rightarrow \sum_{i = 0}^{n-1}\sum_{j = 0}^{n-1} lcm(a_i, a_j) = 2\cdot ans + \sum_{i = 0}^{n-1} a_i
```

> 于是问题转换成求解$$\displaystyle \sum\_{i = 0}^{n-1}\sum\_{j = 0}^{n-1} \text{lcm}(a_i, a_j)$$

怎么求解呢？

### 莫比乌斯反演中的套路化简

> 莫比乌斯反演中的套路化简，对形如特定形式的表达式，**做倍数和**

```math
\displaystyle
f(d) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} A_iA_j \cdot [gcd(A_i, A_j) = d]
```
考虑对$$d$$**做倍数和**
```math
\displaystyle
g(d) = \sum_{d \mid d'} f(d') = \left( \sum_{i = 1}^{n}A_i  [d \mid A_i]  \right) \cdot \left(\sum_{j = 1}^{n} A_j [d \mid A_j] \right) \\
= \left( \sum_{i = 1}^{n}A_i  [d \mid A_i]  \right)^2
```

考虑**莫比乌斯反演**
```math
\displaystyle
f(d) = \sum_{d \mid d'} \mu(\frac{d'}{d}) \cdot \left( \sum_{i = 1}^{n} A_i \cdot [d' \mid A_i] \right)^2
```
这样就化成了每一部分都可以$$O(n \log n)$$求解的表达式

## Educational Codeforces Round 172
### C
**[C. Competitive Fishing](https://codeforces.com/contest/2042/problem/C)**
Alice 和 Bob 比赛钓鱼，0 表示鱼是 alice 钓到的，1 表示是 Bob 钓到的，你要将鱼分成若干个连续的段
对于每一段，鱼的价值就是这一段的下标，比如第一段价值是 0，第二段是 1，第$$i$$段是$$i-1$$
现在问你最少要多少段，使得 Bob 得分超过 Alice $$k$$分

**算法分析**
> 首先，可以怎么转换

考虑后缀和，如果是`1`，后缀和`+= 1`，如果是`0`，后缀和`-1`，这样问题转化为，找到最小的$$m$$（切$$m$$刀）
假设切的位置依次是`1, 2, ..., m`，使得
```math
(s_m \cdot m) + (s_{m-1} - s_m) \cdot (m-1) + (s_{m-2} - s_{m-1}) \cdot (m-2) + \cdots + (s_1 - s_2) \cdot 1 
```
尽量大，并且要$$\geqslant k$$，那考虑**一次拆一个`1`**

先都拆出一个`1`，那么答案是 $$(s\_1 - s\_2)+(s\_2 - s\_3) + \cdots + (s\_{m-1} - s\_m) + s\_m = s\_1$$

然后接着还剩下$$(s\_2 - s\_3) \cdot 1 + (s\_3 - s\_4) \cdot 2 + \cdots + (s\_{m-1} - s\_m)\cdot (m-2) +  s\_m \cdot (m-1)$$
再拆出一个$$1$$，求和是$$s_2$$

> 形如上述形式，发现答案就是后缀和

不难发现，我们就是要使得$$s_0 + s_1 + \cdots + s_m \geqslant k$$，那我们只需要找到最大的$$m$$个$$s$$，使得加起来$$\geqslant k$$即可

> 注意形式

以后如果遇到
```math
\displaystyle
s_m \cdot m + \sum_{i = 1}^{m-1} (s_i - s_{i+1}) \cdot i
```
可以直接写成后缀和$$\sum_i s_i$$

### D
**[D. Recommendations](https://codeforces.com/contest/2042/problem/D)**
每个用户有一个喜欢的曲目，是连续的一段$$[l, r]$$，如果用户$$j$$喜欢用户$$i$$的所有曲目
那么$$j$$是$$i$$的预测者
对于每个$$i$$，计算推荐曲目的数量
推荐曲目是**每一个预测者**喜欢的，但是却不在$$i$$曲目列表里的歌曲

**算法分析**
> 先简化题意

对于每一个$$[l_i, r_i]$$，先从集合中删去$$[l_i, r_i]$$，然后再在集合中放入所有满足
```math
\begin{cases}
l \leqslant l_i \\
r \geqslant r_i
\end{cases}
```
的区间$$[l, r]$$，你需要在这样的$$[l, r]$$中，找到$$maxl, minr$$
最后$$|(minr - maxl) - (r_i - l_i)|$$就是答案

> 能不能排序

两个限制，先排序一遍，求右端点最优解，然后再排序一遍，求左端点最优解
1）左端点小到大排序，相同的话按右端点大到小排序
这样考虑到$$i$$的时候，只需要考虑当前的**前缀**，当前前缀一定是满足$$l \leqslant l_i$$的限制的

那么我们只需要关心，怎么求`minr`，可以用`mutiset`维护集合，再用一个指针$$j$$，从`i`开始，
只要区间和$$i$$相同，那么我们就`j++`，因为左端点相同，右端点是递减的，所以满足条件的$$r$$
一定在$$[1\cdots j-1]$$这样的前缀中
用`multiset`**维护前缀**（注意`j`双指针往前走的时候，也要同步维护前缀），把`r`插入到集合中

这样，对于`[li, ri]`，我们先在`multiset`中删掉`ri`，然后**二分查找**第一个$$\geqslant r_i$$的元素
这样`ri[ idx ] = 二分查找到的值`，做完之后要把`ri`给`insert`回来

2）右端点从大到小排序，相同的话，左端点从小到大排，对称地做一遍，求出`le[ idx ]`

> 注意的点

1）在`set, map`中执行二分查找，要调用它们本身的`lower_bound`，即`st.lower_bound(ri)`
这样才是在平衡树上二分，复杂度才对
2）在`multiset`中删除元素的时候，必须`st.erase(st.find(x))`，这样才是**只删除一个值为`x`的元素**
否则就会把所有值为`x`的元素删除

### F
**[F. Two Subarrays](https://codeforces.com/contest/2042/problem/F)**
**问题描述**
给定两个序列$$a, b$$，定义代价$$[l,r] = a\_l + a\_{l+1} + \cdots + a\_{r-1} + a\_r + b\_l + b\_r$$，如果$$l = r$$，代价为$$a_l + 2b_l$$
执行若干询问
```bash
1 p x		赋值 a[p] = x
2 p x 		赋值 b[p] = x
3 l r		 在区间 [l, r] 中找两个非空的，并且不重叠的，子数组（要连续），使得两个数组的代价和最大，输出这个最大代价

3 -1 4 -3 2 4 0
0 6 1 0 -3 -2 -1

比如询问 [1, 7]
```
```math
\displaystyle
\begin{pmatrix}
-1 \\
6
\end{pmatrix}
\begin{pmatrix}
4 & -3 & 2 & 4 & 0 \\
1 & 0 & -3 & -2 & -1
\end{pmatrix}
```
这样取是最优的，代价是$$11 + 7 = 18$$

#### 算法分析
> 不考虑$$[l, r]$$，假设说就是普通的线性序列$$[1, n]$$，该怎么做

![](/media/content_img/EDU172F.png)

> 考虑在区间上怎么做？

不妨考虑线段树，假设$$[l, r]$$使得状态从$$i \to j$$，那么左子树$$i \to k$$，右子树$$k \to j$$
那么$$(i \to j) = \max(le(i \to k), ri(k \to j))$$
其中$$i \to k$$之类的，表示在当前区间内，状态从$$i \to k$$的最优代价

那么对于叶子结点，比如说$$a_l, b_l$$，就要考虑$$l$$这个位置，可能处在**哪两个状态变化之间**？
举个例子，比如$$[\cdots l-1]$$是状态`1`，$$l$$仍然保持状态`1`，那么$$(1 \to 1) = a_l$$
如果$$[\cdots l-1]$$是状态`0`，$$l$$变成了状态`1`，那么$$(0 \to 1) = a_l + b_l$$
用这样的方法来构造矩阵，不难发现
```bash
0 -> 0,  2 -> 2, 4 -> 4:		+0
1 -> 1,  3 -> 3:	a

0 -> 1, 1 -> 2:		a+b
2 -> 3, 3 -> 4:		a+b
```
另外，这里的状态，允许**只选一个数**，比如你选的子区间都是$$[i, i]$$，实际上你只选了$$a_i$$这一个数
```bash
// 只选了一个数，那么存在转移
0 -> 2:		a + 2b
2 -> 4:		a + 2b
// 此时 b[l] 既是左边界，又是右边界
```
至此，这个问题差不多就做完了，考虑用线段树维护即可

#### 算法实现
```bash
const int M = 5;
using mat = array<array<i64, M>, M>;

mat op(mat a, mat b) {
    mat res;
    for (auto &arr : res) for (auto &x : arr) x = -inf<i64>;

for (int i = 0; i < M; i++) for (int j = i; j < M; j++) for (int k = i; k <= j; k++) {
        chmax(res[i][j], a[i][k] + b[k][j]);
    }

return res;
}

void solve(int cas) {
    auto setval = [&](i64 a, i64 b) -> mat {
        mat res;
        for (auto &arr : res) for (auto &x : arr) x = -inf<i64>;

res[0][0] = res[2][2] = res[4][4] = 0;
        res[1][1] = res[3][3] = a;

res[0][1] = res[1][2] = res[2][3] = res[3][4] = a + b;
        res[0][2] = res[2][4] = a + b + b;

return res;
    };

int n;
    cin >> n;
    vector<i64> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<i64> b(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> b[i];

vector<mat> c(n+1);
    for (int i = 1; i <= n; i++) c[i] = setval(a[i], b[i]);

segtree<mat, op> tr(c, n);

int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;

if (op == 1) {
            int p, x;
            cin >> p >> x;
            
            a[p] = x;
            auto now = setval(a[p], b[p]);
            tr.change(1, 1, n, p, now);
        }
        else if (op == 2) {
            int p, x;
            cin >> p >> x;

b[p] = x;
            auto now = setval(a[p], b[p]);
            tr.change(1, 1, n, p, now);
        }
        else {
            int l, r;
            cin >> l >> r;
            auto res = tr.query(1, 1, n, l, r);

i64 ans = res[0][4];
            cout << ans << "\n";
        }
    }
}
```

### 飞马祝福语
**[飞马祝福语](https://ac.nowcoder.com/acm/contest/16520/D)**
**问题描述**
给定`Feima`，和一条祝福语，祝福语的子串（不需要连续）也被认为是一条祝福语
如果一条祝福语和`Feima`完全相同（包括大小写），就被认为是飞马祝福语，现在有区间修改
把`[l, r]`都改成`ch`，问修改后还有多少飞马祝福语

**算法分析**
考虑`Feima`，$$(l, r)$$维护$$l \to r$$子串出现的次数，比如`[0, 2]`就表示，区间内`Fei`出现的次数
对于线段树某一个区间$$[l, r]$$，打表矩阵`mat`，其中，`mat(i, j)`就表示区间的串，含有多少个`Feima[i...j]`的子串

这样就不难设计线段树了
1）对于叶子结点`str[l]`，看一下`str[l]`和`Feima`的哪个位置（比如说`i`）匹配，`mat(i, i) = 1`
2）子节点的合并，因为是统计出现次数
```math
res += le(0 \to 4) + ri(0 \to 4) \\
\text{for } k \in [0, 4]:\quad res += le(0 \to k) \cdot ri(k+1 \to 4)
```
这样就维护完成了，那么还有一个问题，就是区间修改，其实这个问题，区间修改只要改`mat`即可
1）`#`作为`id()`
2）标记的复合，`comp(f, g) 直接返回 f`，`mapping(F f, mat x)`呢？
看一下`f`这个字符对应`Feima`中的哪个位置？不妨设`k`，直接令`x[k][k] = 区间长度 len`

#### 算法实现
```bash
// 只给出线段树操作的核心代码
struct S {
    mat info;
    int len;
};

S op(S a, S b) {
    S res;
    res.len = a.len + b.len;

auto &info = res.info;
    for (auto &arr : info) for (auto &x : arr) x = 0;

for (int i = 0; i < M; i++) for (int j = i; j < M; j++) {
        info[i][j] += a.info[i][j], info[i][j] += b.info[i][j];
    }
    for (int i = 0; i < M; i++) for (int j = i; j < M; j++) {
        if (i == j) continue;
        for (int k = i; k + 1 <= j; k++) {
            info[i][j] += a.info[i][k] * b.info[k+1][j];
        }
    }

return res;
}

char id() {
    return '#';
}

char comp(char f, char g) {
    return f;
}

S mapping(char f, S x) {
    S res = x;
    auto len = res.len;

auto &info = res.info;
    for (auto &arr : info) for (auto &x : arr) x = 0;

auto found = [&]() -> int {
        for (int i = 0; i < 5; i++) {
            if (pat[i] == f) return i;
        }
        return -1;
    };

auto k = found();
    //debug(k);
    if (k == -1) return res;

info[k][k] = mint(len);

return res;
}
```

### E
**[E. Vertex Pairs](https://codeforces.com/contest/2042/problem/E)**
**问题描述**
给定一个$$2n$$个点组成的树，每个顶点都有一个整数$$1 \sim n$$，并且每一个$$1 \sim n$$的整数
都恰好写在$$2$$个顶点上，顶点$$i$$的代价是$$2^i$$
现在需要选择一个子集，满足
1）子集是连通的
2）数$$1 \sim n$$至少写在子集的一个顶点上
找到这样的子集，同时使得顶点总代价最小，但是点的数量不一定要求最小

#### 算法分析
> 不难发现，从$$2n$$个点中选$$n$$个点，重心一定会被选上

找出重心，然后以重心为根进行 dfs，问题就可以转化成，某个点到根的路径上都要被选
还有哪些点一定要选？不难发现，值为`x`的节点编号，分别是`ver(x, 0), ver(x, 1)`
那么`lca( ver(x,0), ver(x, 1) )`也是一定要选的

这些东西都可以预处理
找重心，然后以重心为根进行 HLD，考虑$$x \in [1, n]$$每一个值，`lca( ver(x,0), ver(x, 1) )`先选上
每个`lca`暴力往根节点爬就可以，只不过要用一个`choose`标记一下，如果爬过了就不要继续爬了
这样每条路径都只会被经过一次

> 接下来考虑值为`x`的两个点，选哪个呢？选节点编号较小的那个
并且因为 lca 都选上了，这里是可以决策到较小编号的点的

可以**从大到小**遍历每个节点，这一次可以确定决策，**该选的选，不该选的不选**
对于节点编号`u`，实际上，该选的点是`need = ver( a(u), 0 ) ^ ver( a(u), 1 ) ^ x`，从大到小遍历，我们就确定了`need`

注意到，我们决策`u`的时候，**可以把 u 所有的子树也决策了**，（此时 u 就是子树的 lca）这点可以用 HLD 的 dfs 序实现
对$$[l_u, r_u]$$，决策$$u$$子树之后，用**并查集**合并子树，做完之后将整个子树分支和下一个分支合并
这样对于$$u = 2n \to 1$$，一次就可以**成对确定**，哪些点该选，哪些点不该选
之后对于已经被选上的点，跳过即可

#### 算法实现
```bash
void solve(int cas) {
    int _n, n;
    cin >> _n;
    n = _n * 2;

vector<int> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

vector<vector<int> > g(n+1);
    for (int i = 0; i < n-1; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
    }

vector<array<int, 2> > ver(_n+1, {0, 0});
    for (int i = 1; i <= n; i++) {
        auto x = a[i];
        if (ver[x][0] == 0) ver[x][0] = i;
        else ver[x][1] = i;
    }

// center
    vector<int> sz(n+1, 0), ctr, fa(n+1, 0);
    auto dfs = [&](auto &dfs, int u, int pa) -> void {
        sz[u] = 1, fa[u] = pa;
        bool sgn = true;
        for (auto v : g[u]) {
            if (v == pa) continue;
            dfs(dfs, v, u);
            sz[u] += sz[v];

if (sz[v] > n / 2) sgn = false;
        }
        if (n - sz[u] > n / 2) sgn = false;
        if (sgn) ctr.push_back(u);
    };
    dfs(dfs, 1, 0);

assert(ctr.size() > 0 && ctr.size() <= 2);

// new tree
    int NIL = n + 1;
    vector<vector<int> > tr(n+2);
    
    if (ctr.size() == 1) {
        for (int i = 1; i <= n; i++) {
            if (fa[i] == 0) continue;
            auto x = i, y = fa[i];
            tr[x].push_back(y), tr[y].push_back(x);
        }
        tr[NIL].push_back(ctr[0]), tr[ctr[0]].push_back(NIL);
    }
    else {
        auto c1 = ctr[0], c2 = ctr[1];
        if (fa[c1] == c2) swap(c1, c2);
        
        for (int i = 1; i <= n; i++) {
            if (fa[i] == 0 || i == c2) continue;
            auto x = i, y = fa[i];
            tr[x].push_back(y), tr[y].push_back(x);
        }
        tr[NIL].push_back(c1), tr[c1].push_back(NIL);
        tr[NIL].push_back(c2), tr[c2].push_back(NIL);
    }

// HLD
    HLD hld(NIL, tr);
    vector<int> chose(n+5, 0);
    auto toroot = [&](int u) -> void {
        while (u < NIL && !chose[u]) {
            chose[u] = 1, u = hld.pa[u];
        }
    };

for (int x = 1; x <= _n; x++) {
        auto v1 = ver[x][0], v2 = ver[x][1];
        auto lca = hld.LCA(v1, v2);
        toroot(lca);
    }

// subtree, choose n->1 , dsu
    DSU<int> dsu(n+5);
    
    for (int i = n; i >= 1; i--) {
        if (chose[i]) continue;
        auto le = hld.l[i], ri = hld.r[i];

for (int j = dsu.find(le); j <= ri; j = dsu.find(j)) {
            int u = hld.ord[j];
            auto need = (ver[a[u]][0] ^ ver[a[u]][1] ^ u);
            toroot(need);

dsu.merge(j+1, j);
        }
    }

vector<int> ans;
    for (int i = 1; i <= n; i++) if (chose[i]) ans.push_back(i);

cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << " \n"[i == (int)ans.size() - 1];
}
```

## Codeforces Round 990 (Div. 2)
### D
**[D. Move Back at a Cost](https://codeforces.com/contest/2047/problem/D)**
**问题描述**
给定一个序列，你可以执行下面操作若干次，每一次都任意选一个位置$$i$$，把$$a_i + 1$$之后
移动到数组末尾，问你若干次之后，得到的数组**最小字典序**

**算法分析**
**观察一**
1）最终的数组一定是非严格单调递增的
2）最终，第一个数一定是序列的**后缀最小值**，维护最小值$$mn$$以及最小值出现的位置$$p$$（线段树）
前缀$$[1\cdots p-1]$$全部$$+1$$移动到后面（用`vector tail`维护）
原先取到后缀最小值的数，不要去动它，$$mn \to res$$，`res`维护不要改变的那些数
3）接着呢？依次考虑**后缀最小值位置**$$\\{p_1, p_2\cdots p_m\\}$$
如果$$p > i$$，那么$$[i\cdots p-1]$$的数全部`+1`之后，移到`tail`中
如果$$p = i$$，$$a_i$$可以直接放到`res`中

**观察二**
1）注意到，扔到`tail`中的数，位置是任选的
2）需要扔到`tail`中的数，也是确定的，只是你可以任意选择什么时候扔掉
贪心地做，**小的先扔，大的后扔**，这样需要扔掉的数，每个都只会被`+1`一次，是最优的
在`tail`中，对这些数排序即可

**观察三**
那么`tail`和`res`能否拼接？注意到整个序列要单调增，类似**单调栈**
如果`res.back() > tail[0]`，那么就要继续把`res`中的数给扔到`tail`中
最后对`tail`排序，就可以拼接起来
为什么呢？因为这样操作下来，可以保证`res`一定是有序的，并且一定是原序列中最小的那几个数

实际上，整个过程也可以**单调栈**
> 对于一个序列，如果需要打表`（最小的数、第二小的数、第三小，.....）`
这也可以**单调栈**，维护一个单调递增的前缀栈即可

## Codeforces Round 991 (Div. 3)
### B
**[B. Transfusion](https://codeforces.com/contest/2050/problem/B)**
有两种操作，第一种，可以令$$a\_{i-1} + 1, a\_{i+1} - 1$$
第二种，可以令$$a\_{i-1} - 1, a\_{i+1} + 1$$
问能不能通过任意次这样的操作，使得$$a$$所有数都相同
操作过程要保证序列非负

**算法分析**
有一种很重要的思想，**势能分析**
以第一种操作为例子，对于`a[0, 2, 4, ..., 2m]`，你可以把$$a_0 \to 0$$，然后把$$a_0$$的值计算在$$a_2$$上

接着把$$a\_2 \to 0$$，以此类推，这样$$a\_{2m} = \sum\_{\text{even}} a$$
这样最后一个数就拥有了所有**偶数下标的和**，而其他位置都是$$0$$

然后**重新分配**，重新分配之后，每个数都相等，也就是说每个数的值$$v_1 = sum_1 / c_1$$
（其中$$sum_1, c_1$$分别表示偶数下标的和，以及有多少个偶数）

重新分配也很简单，从$$a\_{2m}$$开始，只给$$2m$$位置留下$$d\_1$$个数，然后把剩下的数转移到$$a\_{2m-1}$$
对于$$a\_{2m-1}$$也是如此，以此类推

### 差分数组类似的应用
**[空调](https://www.acwing.com/problem/content/4265/)**
给你一个数组$$t$$，要把它变成数组$$a$$，一次操作可以任选一个区间，把区间中的数都`+1 or -1`
问最小的操作次数

**算法分析**
问题转化成`d`数组，令$$d_i = t_i - a_i$$，目标就是选择$$d$$数组任意一个区间，`+1 or -1`
使得`d`数组全部变成`0`

1）不难想到转化成`d`的**差分数组**，`d`数组全为`0`，等价于其差分数组都要是`0`
这个是一定可以做到的，最坏的情况，可以用差分数组的势能
将$$a\_i -1, a\_{i+1} + 1$$，从而让`a[1...n-1] = 都等于 0`，而`a[n] = 原数组的和 sum`
这时候再做`sum`次操作，将`a[n]`变成`0`即可

2）考虑怎么优化？
因为差分数组具有**势能**，可以**正数和负数配对**
这样正数`-1`，负数`+1`，最大化这样的配对，实际上需要的操作次数就是$$\delta=\min(|neg|,|pos|)$$
即正数，负数和的绝对值较小的那个

这样，只需要$$\delta$$次操作，每一次操作就可以令两个元素变得尽量接近 0
剩下的呢？就是没有配对的部分，这部分我们只能一个一个`-1 or +1`删掉

这部分可以理解成**势能**，但是没有配对的数，来消除这部分的势能，所以最后的代价是必须的

## AtCoder Grand Contest 041
**[D - Problem Scores](https://atcoder.jp/contests/agc041/tasks/agc041_d)**
给定$$n$$，现在给你一个限制，$$a_1 \leqslant a_2 \leqslant \cdots \leqslant a_n$$
另外，还要满足任意$$k$$个数的和**严格小于**任意$$k+1$$个数的和，问$$a_1, a_2\cdots, a_n$$取值方案数
其中每个$$1\leqslant a_i \leqslant a_n$$

**算法分析**
> 考虑转化条件，怎么来表示条件呢？

实际上，要求任意$$k+1$$个最小值$$>$$任意$$k$$个最大值，注意到$$a$$是排好序的
也就是说$$a\_1 + a\_2 + \cdots + a\_{k+1} > a\_{k+2} + a\_{k+3} \cdots + a\_n$$

后半段实际上有$$n - k - 1 \leqslant k$$个数，那么$$2k \geqslant n - 1, \ k \geqslant \lfloor \dfrac{n-1}{2} \rfloor$$
那么对于$$k = \lfloor \dfrac{n-1}{2} \rfloor$$，我们要满足$$a\_1 + a\_2 + \cdots + a\_{k+1} > a\_{k+2} + a\_{k+3} \cdots + a\_n$$

> 那么，满足上述限制的前提下，$$a_1 \leqslant a_2 \leqslant \cdots \leqslant a_n$$有多少种？
其中，$$1 \leqslant a_i \leqslant n$$

这个怎么做？
> 实际上，递推的时候，维护$$k = \lfloor \dfrac{n-1}{2} \rfloor$$，$$a\_1 + a\_2 +\cdots + a\_{k+1} > a\_{k+2} + \cdots + a\_n$$

一开始令所有的$$a$$都是$$n$$，这样一开始一定是满足的，然后呢？
**一次递推，只减去一个前缀**，因为$$a_i \in [1, n]$$，最多需要减去$$n$$个前缀，迭代$$n$$次
一定能够计算出所有情况，只不过呢，每一次减去的前缀位置不同，为了保证$$a_1 \leqslant a_2 \leqslant \cdots \leqslant a_n$$
假设减去的前缀位置是$$p_1, p_2, \cdots, p_n$$，那么一定有$$p_1 \leqslant p_2 \cdots \leqslant p_n$$

可以考虑把**减去的前缀**作为阶段来 dp
```math
dp(i+1, a', b') \leftarrow dp(i, a, b) \\
\text{condition:  } a > b, \ a'>b' \\
a', b' \text{ 分别为 } a, b \text{ 减去前缀 i 之后 }，[1\cdots k+1] \ [k+2\cdots, n] \text{的前(后)缀和}
```

那怎么优化呢？注意到条件$$a > b$$，我们可以记$$\delta = a - b$$，这样考虑$$dp(i, \delta) \to dp(i+1, \delta')$$
其中$$\delta \geqslant 0$$，统计答案的时候我们只算$$\delta > 0$$部分的答案，$$ans = \sum\_{\delta} dp(n, \delta)$$

> 考虑$$\delta$$是怎么变化的，转移方程

1）如果$$i \leqslant \dfrac{n-1}{2}+1 = \dfrac{n+1}{2}$$，考虑减去前缀$$i$$，$$\delta' = (a - i) - b = \delta - i$$

2）如果$$i > \dfrac{n+1}{2}$$，那么$$\delta' = (a - \dfrac{n+1}{2}) - \left(b - (i - \dfrac{n+1}{2}) \right) = \delta - (n+1-i)$$

> 问题到这里就很明朗了

维护$$a\_1 + a\_2 + \cdots + a\_{k+1} > a\_{k+2} + \cdots a\_n$$，令$$\delta = (a\_1 + \cdots + a\_{k+1}) - (a\_{k+2} + \cdots + a\_n)$$
其中$$\delta \in (0, n]$$，是背包的容量
对于每个前缀$$i$$，如果$$i \leqslant \dfrac{n+1}{2}$$，那么前缀$$i$$的体积是$$i$$，否则就是$$n +  1 - i$$
转换成**完全背包**问题即可

```bash
for i = 1 to n 考虑每一个前缀 i
	for d = n downto 1 考虑当前背包的容量
		dp(d - w[i]) += dp(d)
		
for d = 1 to n:		ans += dp[d]
```

> 总结，这个问题和 EDU172 C 有异曲同工之妙
![](/media/content_img/agc041.png)

## 01-bfs 和 bfs 求最短路

> bfs 求最短路，有一个技巧很常见，先把所有的$$\text{dis} \leftarrow +\infty$$
用队列来扩展的时候，只需要将`dis(y) > dis(x) + 1`的点进队列即可

> 01-bfs 也比较常用

下面考虑 01-bfs
1）01-bfs 考虑用`deque`，双端队列，考虑$$x \to y$$，如果边权是`0`，那么`push_front(y)`
否则边权是`1`，`push_back(y)`
实现的时候，有时候可以预处理所有的点，标记一下`zero[ (x, y) ]`
判断一下$$(x, y)$$边是不是边权为$$0$$的边

2）队列扩展的时候，取的是`que.front()`队首元素

**[2024百度之星决赛 冰柱](https://www.matiji.net/exam/brushquestion/27/4498/F16DA07A4D99E21DFFEF46BD18FF68AD)**

给定起点$$(x_1, y_1)$$，终点$$(x_2, y_2)$$，有一些冰柱，也给定冰柱的坐标
破坏冰柱，需要消耗 1 个单位体力，走没冰柱的格点，不需要体力，问走到终点最小的体力消耗

**算法分析**
01-bfs 直接做即可

上一篇：2025年四月算法竞赛选题（一）下一篇：最大流，最小割和匹配（一）

看完文章有啥想法