codeforces数据结构专题（五）

[[ slider_text ]]

[[ item.c ]]

codeforces数据结构专题（五）

发布时间 2023-08-20 作者：zhangminchen 来源：算法小站

主席树 树上问题 排列与置换 区间贪心

## Good Bye 2022: 2023 is NEAR
**[D. Koxia and Game](https://codeforces.com/contest/1770/problem/D)**
**问题描述**
Koxia 和 Mahiru正在玩一个游戏，游戏使用$$3$$个长度为$$n$$的数组，分别是$$\left< a, b, c\right>$$
每一个位置的元素分别是$$a_i, b_i, c_i$$
每一轮中，Koxia 先在$$a_i, b_i, c_i$$中选一个数字，Mahiru 再从剩下的两个数字中选一个

如果$$n$$轮后，Mahiru 选择的数字刚好构成$$1 \sim n$$的排列，Koxia 胜利，否则Mahiru 获胜
假设双方都采取最优策略，求出使得 Koxia 必胜的$$c$$数组的个数

想要解决这个问题，要知道一些前置内容
###  排列与置换
**性质一**
奇偶性，记一个**置换序列**，比如$$(5, 2, 3, 1, 4)$$**逆序对数目**为$$\sigma(n)$$
置换的符号记为$$(-1)^{\sigma (n)}$$

**性质二 置换的环分解**
![](/media/content_img/functional-graph.jpg)

如果置换$$T$$是一个大小为$$n$$的环，那么$$T^k$$分解后是大小为$$\displaystyle \frac{n}{ \text{gcd}(n, k) }$$的环
并且这样的环有$$\text{gcd}(n, k)$$个

> 相当于步长是$$k$$，原来需要$$n$$次走完，现在只需要$$\displaystyle \frac{n}{\text{gcd}(n, k)}$$次
   即新的环的长度是$$\displaystyle \frac{n}{\text{gcd}(n, k)}$$

> 这样不断轮换下去，每一个环对应原来序列$$T$$中的**下标**
   $$i \bmod \text{gcd}(n, k) = 0, 1, 2, \cdots$$的元素组成
   
>  $$T = (1, 3, 5, 2, 4, 6)$$
    $$T^2 = (1, 5, 4)(3, 2, 6)$$，注意到此时$$\text{gcd} = \text{gcd}(2, 6) = 2$$
	每个循环节的下标怎么求？按照$$\bmod 2$$的余数，对$$T$$的**下标**进行分类
	$$[0]:\left<0, 2, 4 \right>, [1]: \left<1, 3, 5 \right>$$
	所以可以分解成$$T^2 = (1, 5, 4)(3, 2, 6)$$
	
>  继续轮换下去，还可以发现$$T^7 = T$$，所以我们有
    $$T^k = T^{(k-1) \bmod n + 1}$$
	
**性质三**
对于$$\text{gcd}(n, k) = 1$$的情形，同样令$$a = T, a^{\prime} = T^k$$，初始时有$$a_0 = a^{\prime}_0$$

然后开始考虑沿着轨道走，步长尾$$k$$，这样就有$$a^{\prime}[i] = a[ik \bmod n]$$

**性质四 置换图**
置换图和**Functional Graph**是很常见的两种结构，大意就是给定一个$$1 \to n$$的排列
不妨设它表示人的编号，$$(i, x(i))$$表示编号是$$i$$的人和编号是$$x(i)$$的人有关系
对于$$(i, x(i), x(x(i)), \cdots)$$
如果考虑建一条有向边$$(i \to x(i))$$，对应的图就是**Functional Graph**

**Functional Graph**有如下性质，假设图$$G$$包含$$K$$个连通分量
$$C_1, C_2, \cdots, C_k$$，每一个连通分量**有且仅有一个环**

> **证明**，如果每个点的入度也都是$$1$$，那么这样的图就对应是**置换图**
  置换图，对于每个连通分量而言，$$|V| = |E|$$（边的数量等于顶点数量）
  这可以看作是一棵树加上一条边构成，并且这样的图**有且仅有一个简单环**
  
> 否则的话，我们可以尝试找到一个入度为$$0$$的点，删除这个点和它的出边
   类似拓扑排序，可以不断执行这个过程，直到剩下的图构成一个**置换图**
   
### 考虑该问题怎么求解
首先，Koxia **先手**，那么留给 Mahiru 的两个数一定要**都相同的**，这样 Mahiru 才**没有选择**，不影响结果

> 证明，因为选$$n$$轮，最后如果要成为排列，那么 Mahiru 每一轮能选的数必须是**确定的**
   这些数恰好构成排列，比如 $$T = (2, 3, 1, 4, 5)$$
   如果不这样选，那么 Mahiru 一定有办法使得选出来的数不构成排列
   
![](/media/content_img/CFgoodbye2022_2023isnear-D.jpg)

下面考虑，什么情况下 Koxia 才有可能获胜？
**引理**  如上图所示，令$$p$$是一个长度是$$n$$的数组，$$p_i = a_i \ \text{or} \ b_i$$
koxia 能获胜当且仅当$$p$$是一个排列

> 证明，如果$$p$$是一个排列，我们可以令$$c_i = p_i$$，这样每一轮 Mahiru **都没得选**，Koxia 获胜
   否则的话，不存在这样的数组$$c_i$$使得 Koxia 获胜
   因为即使我们构造出了数组$$c_i$$成为排列，但 Mahiru 可以选剩下的$$a_i$$或者$$b_i$$
   如上图所示，比如第一轮，Mahiru 选 $$A_1$$ 就失败了，但他可以选 $$B_1$$ 或者 $$C_1$$
   
那么我们需要实现一个算法，来判断**引理**是否成立
判断$$p$$是否是一个排列，可以从**置换图**的角度来考虑
每个点的入度为$$1$$，并且对于每个连通分量，$$|V| = |E|$$，有且仅有一个简单环

> 先看简单一点的，如何判断一个序列$$P$$是否是排列？

尝试去构造一个图，使得$$1 \sim n$$每个节点都**恰好被一条边**所指
对于序列$$p_i$$，可以考虑连边$$(i \to p_i)$$，判断每个连通分量是否满足$$|V| = |E|$$
或者判断每个点的入度是否为$$1$$即可

> 那么回到本问题，$$p_i$$既可以选$$a_i$$，又可以选$$b_i$$，怎么保证选出来的是排列？
   能够成排列的点$$i$$，要被一条边所指向
   那么$$a_i$$或者$$b_i$$要被一条边所指向，可以考虑连**无向边**$$(a_i, b_i)$$
   
连双向边$$(a_i, b_i)$$，如果对于每个连通分量，能满足$$2|V| = |E|$$（双向边）
那么就可以构造出满足题目要求的$$c$$，否则答案不存在

对于满足题目要求的情况，对**每个连通分量**，它有且仅有一个简单环
*  如果简单环是自环，那么$$a_i = b_i$$，此时$$c_i$$可以取$$1 \sim n$$任意数
   （这时候 Koxia 把$$c_i$$ 选走，Mahiru 就没得选了）
   此时有 `ans *= n`

*  否则，$$a_i \neq b_i$$，此时对于每个连通分量，假设环的起点是$$i$$，那么有
   $$c_i = a_i$$ 或者 $$c_i = b_i$$
   
   如果选 $$a_i$$，相当于绕着环顺时针走，否则相当于逆时针，之后能选的数都是**确定的**
   此时每个连通分量仅有$$2$$种选择，那么`ans *= 2`
   
## Codeforces Round 837 (Div. 2)
### D

**[D. Hossam and (sub-)palindromic tree](https://codeforces.com/problemset/problem/1771/D)**
**问题描述**
给定一个$$n$$个节点的树，每个节点有一个字符
定义$$S(u, v)$$，为$$u \to v$$的唯一路径上，所有字符构成的字符串
现在要求$$S$$中，最长回文子序列的长度

回文子序列，为$$S$$中，满足回文关系的子序列（子序列不一定连续）

**算法分析**
根据数据范围，不难想到可以用$$O(n^2)$$的算法来实现
考虑线性的最长回文子序列怎么写，记$$dp(i, j)$$表示$$a[i, j]$$的最长回文子序列长度

$$dp(i, j) = \max(dp(i+1, j), dp(i, j-1), dp(i+1, j-1) + 2[a_i = a_j])$$

回到树上，这里考虑用**换根**，$$fa_r(x)$$ 表示以$$r$$为根的树，$$x$$的父亲
那么有 $$dp(x, y) = \max(\ dp(fa_y(x), y), dp(x, fa_x(y)),  dp(fa_y(x), fa_x(y)) + 2[c_x = c_y] \ )$$
其中$$c_x$$表示节点$$x$$处的字符

这可以用`dfs`预处理换根，记忆化搜索解决

### F

**[F. Hossam and Range Minimum Query](https://codeforces.com/problemset/problem/1771/F)**
**问题描述**
给定一个长度为$$n$$的非负整数序列$$a$$，给定$$q$$个询问
每次询问$$[l, r]$$中，满足出现次数为**奇数**的数中间，**最小**的那个数是多少？
该问题强制在线

**算法分析**
区间中，求满足给定条件的权值问题，可以考虑**主席树**
奇偶问题，又可以考虑用**异或**来求解

可以对每一个数$$a_i$$给一个随机权值$$r(a_i)$$，这样就可以考虑用主席树求解
具体来说，建树的时候，在第$$i-1$$个版本基础上，令$$a_i$$这个叶节点$$val \oplus r(a_i)$$

这样，当一个数在区间$$[l, r]$$出现奇数次，考虑$$tr\_r \oplus tr\_{l-1}$$
当且仅当这个数对应的叶节点的$$val \neq 0$$

在主席树中，令$$x = (l_x \oplus r_x)$$，其中$$x$$表示区间权值，$$l_x$$表示$$x$$的左子树区间权值
这样就可以考虑**主席树二分**

如果一个区间左子树$$val$$都为$$0$$，那么考虑去右子树中找
否则就在左子树找，直到找到叶子节点，这样就能找到满足条件的最小的权值

## 区间贪心
### 最大不相交区间
**问题描述**
给定$$n$$个开区间$$(a_i, b_i)$$，选择**尽量多**的区间，使得这些区间两两没有公共点。

**算法实现**
按区间**右端点从小到大排序**，右端点相同按左端点**从小到大**排序，每一次取满足条件的**第一个区间**
即记录已选区间的**最右端**$$r$$，每一次选左端点$$l_i \geqslant r$$的第一个区间$$[l_i, r_i]$$
然后令$$r = \max(r, r_i)$$

**证明**
> 首先，如果区间$$1$$被区间$$2$$**包含**，那么一定选区间$$1$$
  即区间包含，**选小不选大**
  
如果区间$$X \subseteq Y$$，那么$$X, Y$$只能二选一，选$$X$$（小区间），不但不会减少区间数量
还会给之后的区间**留出空位**，之后才可能有更多的选择，所以选$$X$$是较优的

> 满足条件的第一个区间一定会被选

因为已知$$b_1 \leqslant b_2$$，考虑$$[a_1, b_1], [a_2, b_2]$$
首先$$[a_1, b_1], \ [a_2, b_2]$$的**公共部分**一定会被选，它是$$[a_2, b_2]$$的一个子区间
根据第一个结论，有了公共部分，并且它是子区间（小区间），那么$$[a_2, b_2]$$就一定不会被选
而**非公共部分**，只有区间$$1$$覆盖到了，因此选择区间$$1$$是较优的

### 区间选点问题
**问题描述**
给定$$n$$个闭区间$$[a_i, b_i]$$，选**尽可能少的点**，使得每个区间内至少有一个点

**算法实现**
将区间**按右端点从小到大排序**，右端点相同时，按**左端点从大到小**排序
每一次取区间$$[a_i, b_i]$$的**最后一个点**$$p = b_i$$，然后找第一个$$l_j > p$$的区间$$[a_j, b_j]$$
再取$$p = b_j$$，以此类推

（说明，这里右端点相同的时候，应该要尽量取小区间，所以按**左端点从大到小**排序）

**证明**

> 考虑包含的情况，取小不取大

如果存在包含情况，那么能满足小区间的，一定也会满足大区间，所以点只会在小区间上选

> 非包含的情况，考虑 $$b_1 \leqslant b_2 \leqslant \cdots$$，$$a_1 \leqslant a_2 \leqslant \cdots$$

如果取的不是$$b_1$$，而是中间的点$$p_0$$，我们发现令$$p = b_1$$会比原来的$$p_0$$更优
原先被这个点覆盖到的区间不会减少，并且**被满足的区间增加了**
（原来的$$[p_0+1, b_1]$$不被满足，现在被满足了）

这样的贪心策略是正确的

### 区间覆盖问题
**问题描述**
给定$$n$$个闭区间$$[a_i, b_i]$$，选择**尽量少的**区间覆盖一条指定线段$$[s, t]$$

**算法实现**
预处理，把所有区间在$$[s, t]$$之外的**切掉**
各区间按**左端点从小到大排序**，左端点相同，按右端点**从大到小排序**

如果区间$$1$$的起点不是$$s$$，无解
否则选择起点在$$s$$的最长区间，假设选择区间$$[a_i, b_i]$$，新的起点设为$$s = b_i$$
并且忽略所有区间在$$b_i$$之前的部分，继续扫描

```bash
typedef array<int, 3> Arr;

// we use [l, r) to store each segment

auto get_overlap = [&](vector<Arr> &seg, const int len) -> vector<PII> {
    sort(seg.begin(), seg.end(), [=](const Arr &a, const Arr &b) {
        if (a[0] != b[0]) return a[0] < b[0];
        else return a[1] < b[1];
    });

bool fail = false, ok = false;
    int st = 0;
    vector<PII> res;

for (int i = 0; i < seg.size(); i++) {
        int j = i, ed = -1e9;

int idx = j;
        while (j < seg.size() && seg[j][0] <= st) {
            if (chmax(ed, seg[j][1])) idx = j;
            j += 1;
        }

if (ed <= st) {
            fail = true;
            break;
        }

res.push_back(PII(seg[idx][2], seg[idx][0]));
        if (ed >= len) {
            ok = true;
            break;
        }

st = max(st, ed), i = j-1;
    }

if (fail || !ok) {
        vector<PII> t;
        t.push_back(PII(-1, -1));
        return t;
    }
    else return res;
};
```

上一篇：codeforces数据结构专题（四）下一篇：FHQ Treap 一种常用的平衡树

看完文章有啥想法