codeforces数据结构专题（四）

[[ slider_text ]]

[[ item.c ]]

codeforces数据结构专题（四）

发布时间 2023-07-29 作者：fogsail 来源：算法小站

树上问题 dfs序 树的重心

## Codeforces Round 874 (Div. 3)
**[F. Ira and Flamenco](https://codeforces.com/problemset/problem/1833/F)**
**问题描述**
在长度为$$n$$的数组$$a$$，从中选出$$m$$个数，满足以下要求
*  恰好选择$$m$$个数

*  选出的数互不相同

*  最大的数和最小的数差值严格**小于**$$m$$

问有多少种选择方法

**算法分析**
实际上，可以发现选出的数恰好构成了$$1 \sim m$$的一个排列，换句话说，选出的数一定形如
$$\left< x, x+1, x+2, \cdots, x+m-1 \right>$$

并且，这些数**至少需要选$$1$$次**，记$$cnt_x$$表示$$x$$出现了多少次，那么
可以这样做，先对原数组排序

枚举下标$$i$$，考虑$$a\_i \sim a\_{i+m-1}$$能否构成公差为$$1$$的等差数列，如果可以
那么令$$x = a\_i$$，考虑区间$$i \in [x, x+m-1]$$，$$\prod_{i = x}^{i = x+m-1} cnt_i$$ 加到答案中

区间乘积，可以用线段树维护$$cnt$$数组

**特别注意**
对数组$$a$$离散化后的数组$$b$$， 令 $$[b_i, b_i + m) \xrightarrow{get} [l, r)$$
（注意到可能我们要找的$$b_i+m-1$$这个数并不存在，所以右区间取开区间$$b_i+m$$）
此时要判一下$$[l, r)$$之间有没有`m`个数？即`r-l < m ?`

```bash
mint ans = 0;
for (int i = 0; i < b.size(); i++) {
	int x = b[i], y = b[i]+m;
	int l = get(b[i]);
	int r = get(y);

if (r-l < m) continue;

mint res = tr.prod(l, r);
	ans += res;
}
```

## leetcode 353场周赛
**[2772. 使数组中的所有元素都等于零](https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/)**

给定数组$$a$$和正整数$$k$$，你可以按以下操作任意次
从数组中选出长度为$$k$$的一段，这一段所有数都$$-1$$，问能不能使得数组中所有元素都是$$0$$

**算法分析**
将一段数都增加/减去$$d$$，很典型的**差分**思想
构造原数组的差分数组$$d$$，同时$$x$$维护差分数组的前缀和
对于$$i$$位置，$$x$$就等于**修改后的**$$a_i$$的值，那么
*  如果$$x < 0$$，返回`false`

*  如果$$i+k > n$$，也返回`false`

*  否则令$$\Delta = x$$，令`x -= x, d[i+k] += x`

## leetcode 355场周赛
**[树中可以形成回文的路径数](https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/)**
**问题描述**
给定一棵树和一个字符串$$s$$，其中$$s_i$$表示$$(pa_i, i)$$之间的边的权值
现在要找出**回文节点对**的数目，回文节点对$$(u, v)$$满足
$$u < v$$，并且$$u \to v$$路径上的字符可以**重新排列**成一个回文串

**算法分析**
树上路径问题，不难想到考虑路径$$u \to lca \to v$$，要求这样的路径上的边的字符
*  仅有一个字符出现次数为奇数，剩下的都是偶数
*  所有字符出现的次数都是偶数

树上路径+奇偶统计，不难想到用**异或解决**，如果字符为$$c$$，那么考虑`w = 1 << (c-'a')`
从根节点到$$u$$的异或和记为$$xor_u$$，那么$$u \to v$$的异或和为
```math
(xor_u \oplus xor_{lca}) \oplus (xor_{lca} \oplus xor_v) = xor_u \oplus xor_v
```
最后的异或和路径，只有可能为$$0$$，或者$$2^0, 2^1, \cdots, 2^{25}$$

假设当前`dfs`考虑的点是$$u$$，此时$$u$$这个分支的路径异或值是$$sum$$
已经访问过的点集是$$v \in V$$，异或值用$$xor$$来表示
要找到有多少个$$v$$，满足$$xor \oplus sum = 0$$
或者$$xor \oplus sum = \left<2^0, 2^1, \cdots, 2^{25} \right>$$

依次遍历$$need \in \left<0, 2^0, \cdots, 2^{25} \right>$$，统计 `cnt[ need ^ sum  ]`
然后再把`u`扔到哈希表中，即令`sum ^= w, cnt[w] += 1`，继续`dfs`

**[长度递增组的最大数目](https://leetcode.cn/problems/maximum-number-of-groups-with-increasing-length/)**
**问题描述**
给定一个长度为$$n$$的数组$$lim$$，你有数字$$0 \sim n-1$$，要创建若干组数据
每个数字$$i$$使用次数不超过$$lim_i$$次，另外，每个组还必须满足
*  每个组中的数字**不同**
*  每个组的长度必须**严格大于**前一个组

返回能够得到的最大组数（不需要返回每个组到底有哪些元素）

**算法分析**
采用贪心策略，**使用次数越多的**数，应该尽可能**靠前**
可以用反证法，如果$$x$$很小，并且只能使用`1`次，尝试构造`[x]`
如果存在一个数比如`9 > x`，`9`可以使用多次，那么`[9], [x, 9]` **更优**

直接模拟这个过程，会超时，因为涉及到一个数使用次数$$-1$$这种修改操作，考虑用**线段树模拟**

将`lim`数组按照使用次数**从小到大**排序（我们并不关心具体的数，只关心**能使用的次数**）
并用线段树维护排序好的`lim`数组

假设当前构造的组的长度为$$i, \ i \in [1 \sim n]$$，也就是说，我需要**最大**的$$i$$个数
需要在$$i-1$$的基础上，再放入一个数，这个数下标在$$n-i+1$$处（我们从小到大排序的）
获取这个数的值`val`，表示当前放入的这个数可以用`val`次

在**线段树上二分**，分别找到右边第一个$$\geqslant val, > val$$的位置$$l, r$$
（必须保证线段树维护的`val`**单调增**）
那么下标在$$[l, r)$$的数都可以使用`val`次，$$[r, n]$$的数可以使用**至少**`val+1`次
贪心策略是，在第$$i$$轮，先把第$$i-1$$轮的数**都选过来**，也就是说
$$[r, n]$$这些数都可以在第$$i$$轮被选上，那么应该区间修改$$[r, n] - 1$$
还需要几个数呢？还需要$$need = i - (n-r+1)$$个数

那么这$$need$$个数，只能选择$$[l, r)$$中出现次数为`val`次的数了
为了保证**单调性**，将下标$$[l, l+need-1]$$范围内的数都选上
（这样单调性不变，为`[val-1, val-1,....., val, >=val, >=val, ......]`）
执行区间修改$$[l, l+need-1] - 1$$

线段树需要维护第一个$$\geqslant x$$的数，实际上维护区间最小值，最大值即可
如果左边`maxv < x`，那么往右走，否则往左

> 还有没有更好的做法？

最好的情况，肯定是能够凑出$$n$$组的，此时每一组数的个数，恰好构成等差数列
以$$n = 5$$为例

```bash
[1, 2, 3, 4, 5]
    [2, 3, 4, 5]
	    [3, 4, 5]
		    [4, 5]
			    [5]
```
依出现次数**从小到大**排序，用`need`记一下**要填几个数**？`c`记一下当前的数**能使用的次数**
假设当前考虑$$i$$，`c = usageLimit[i]`，最好情况下
`c -= need, need++`
（以上面为例，`1`需要填`need=1`次，`2`需要填`need=2`次，以此类推）
如果能够一直这样做下去，最好情况是能够构造出$$n$$组

但是，最好方案不一定可行，对于$$i \to i+1$$

*  如果`usageLimit[i] >= need`，那么出现次数为`usageLimit[i]`的数**还没有用完**
   下一轮还可以用，将`usageLimit[i]`和`usageLimit[i+1]`合并，即`usageLimit[i+1] += usageLimit[i]`
   接着令`need += 1`
   
*  如果到某一时刻，`usageLimit[i] < need`了，那么就不能再构造了，一共构造了
   $$need - 1$$ 组（最后一组是开区间），答案就是$$need-1$$
   
## Codeforces Round 873 (Div. 1)
**[D. Two Centroids](https://codeforces.com/contest/1827/problem/D)**
**问题描述**
给定一棵树，一开始只有$$1$$个编号是$$1$$的节点，接下来有$$n-1$$次操作
第$$i$$次操作添加一个编号是$$i+1$$的节点，并且在节点$$i+1$$和$$p_i$$之间连边

现在需要问，每一次操作之后，还需要**至少**进行多少次**新建一个点并且连边**（注意可以和任意点连）的操作
才能使得这棵树有**两个重心**

**算法分析**
考虑一个问题**[CSP2019 树的重心](https://www.ringalgo.com/article/11/)**
如果根节点不是重心，那么重心一定在**重儿子**中，也就是说，需要沿着**重链**走
假设沿着重链有$$\cdots u\_i \to u\_{i+1} \to \cdots$$，如果$$u_i$$是**重心**，那么
```math
sz(u_i) \geqslant \lceil n/2 \rceil, \ sz(u_{i+1}) \leqslant \lfloor n/2 \rfloor
```
双重心的时候，只要考虑$$u_i$$父亲$$fa$$是不是重心就可以了

已经知道了重心一定在**重儿子子树中**，那么假设当前节点数是$$tot$$，当前的重心是$$cent$$
当加入一个点的时候，重心是怎么变化的呢？
注意到沿着重链，$$sz$$是**单调递减**的
> 假设当前重心$$c1 = u\_i$$，那么另一个重心$$c2 = u\_{i+1}$$是否成立呢？

如果$$c1$$是当前重心，那么新的重心$$c2 = hv$$，即$$c2$$一定等于$$c1$$的**重儿子**
因为重链$$sz$$单调递减，$$sz\_{c1} \geqslant \lceil tot / 2 \rceil, sz\_{hv} \leqslant \lfloor tot / 2 \rfloor$$
考虑往**重儿子子树**中加点，那么$$sz\_{hv}$$是最有可能先满足$$\geqslant \lceil tot /2\rceil$$的点

那么如果会产生新的重心，一定是$$sz\_{hv}$$**恰好刚满足**$$\geqslant \lceil tot/2 \rceil$$的时候
假设需要在重儿子子树中加入$$x$$个点，那么有$$sz\_{hv} + x \geqslant \lceil (n+x)/2 \rceil$$
也就是说，$$x = n - 2 \cdot sz\_{hv}$$
也就是说，我们只要记一下当前的重心$$cent$$，以及重心的**重儿子**$$hv$$的子树大小$$sz$$
$$tot - 2\cdot sz$$ 就是答案

> 那么怎么去完成加点，并维护？

可以考虑先离线，先把整棵树都建好，但是每一个点的$$sz = 0$$，也就是虚拟节点，
添加一个点$$u$$的时候，令`sz[u] += 1`即可
另外，我们要考虑维护**子树的大小**，可以考虑`dfs`序，在`[l(u), r(u)]`上求`sz`区间和
以上操作，都可以用树状数组，维护`dfs`序的`size[...]`数组来实现

> 假设当前的节点个数是$$tot$$，当前的重心是$$c1$$

假设当前需要添加的点是$$u$$，那么有如下情况

* $$u$$在$$c1$$的**子树中**，先单点增加`sz[u] += 1`，然后要找到$$c1$$的**重儿子**$$hv$$
   `sz[hv]`很容易求，就是`dfs`序区间查询`[l(hv), r(hv)]`，那现在问题是$$hv$$怎么求？
   
   一种方法是重链剖分，沿着`u`往下跳，但是这个点是动态增加的，动态维护是很难做的
   好在本例中并不需要知道**重心的重儿子**到底是哪一个，只需要知道**重心重儿子的子树大小**
   由于我们点是一个一个加入的，可以边加入，边维护**重心重儿子子树大小**$$hvsz$$
   
   具体来说，我们需要**倍增**，将$$u$$往上跳到$$c1$$下面的一个点$$w$$
   然后查询$$w$$的子树大小$$sz_w$$（树状数组可以做到），将它和$$hvsz$$取一个$$\max$$
   **特别地**，如果$$sz_w \geqslant \lceil n / 2 \rceil$$，那么$$w$$成为了**新的重心**
   记录$$c1 = w, \ hvsz = \lfloor n/2 \rfloor$$
   
   最后的答案就是$$tot - 2 \cdot hvsz$$

*  如果$$u$$不在$$c1$$的子树中，那么第二个重心可能是$$c1$$的父亲$$fa$$
   这个就简单了，直接查询`fa`所在的树的大小为$$s = tot - sz[c1]$$
   
   和上一种情况一样去更新，如果发现$$s \geqslant \lceil n / 2 \rceil$$，那么标记`fa`为新重心
   同时记一下$$hvsz = \lfloor n/2 \rfloor$$
   
   否则的话，重心并不会变，只需要将$$s$$和$$hvsz$$取$$\max$$即可
   
```bash
void upd(int tot, int w, int sz) {
	if (sz >= (tot+1) / 2)  cent = w,  hvsz = tot/2;
	else hvsz = max(hvsz, sz);
}
```

上一篇：codeforces数据结构专题（三）下一篇：codeforces数据结构专题（五）

看完文章有啥想法