codeforces数据结构专题（二）

[[ slider_text ]]

[[ item.c ]]

codeforces数据结构专题（二）

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

dp 单调栈

## Educational Codeforces Round 150
### E
**[E. Fill the Matrix](https://codeforces.com/problemset/problem/1841/E)**
**问题描述**
给定一个$$n \times n$$的方阵，行和列都是$$1 \to n$$编号，对于第$$i$$列
$$1 \sim a_i$$ 个格子是黑色的，其余格子是白色的
下面把$$1 \sim m$$共$$m$$个整数放入矩阵中，必须满足
*  每个格子**最多**包含一个整数
*  黑色格子不能包含整数

一个矩阵的美丽程度是满足这样的格子个数，该格子自身包含一个数$$x$$，且它右边相邻的格子包含的整数值为$$x+1$$
（不填数的格子定义为**空格**）

求出最大的美丽值

**算法分析**

> 首先想到的是，什么情况下格子不合法

如果$$a\_{i+1} > a\_i$$，那么$$[a\_i + 1 \sim a\_{i+1}]$$ 这个位置填的数对答案没有贡献
对于$$n \times l$$ 区域，对答案的贡献**最多**可能有
```math
\displaystyle
n \times l - \sum_{i = 1}^{n-1} |a_{i+1}  - a_i| \cdot  [a_{i+1} > a_i]
```

> 但问题是，我们一共只能填$$m$$个数啊，如果按照$$n \times l$$来分块的话
   假设第`1`块填了 $$s$$ 个数，那么第`2`块就需要填$$m - s$$个数
   但有可能第`2`块可以把$$m$$个数都填上，这样可能更优
   
> 注意到，美丽值要想尽量大，就应该让**数格旁边尽量不要有黑色的格子**
   并且**连续的白色格子越长越好**
   
我们想，有一段连续的白色格子，长度是$$l_i$$，那么长为$$l_i$$的段，答案是多少？
长度为$$l_i$$的段对答案的贡献是 $$(l_i - 1) \cdot cnt(l_i)$$
其中$$cnt(l_i)$$表示长度为$$l_i$$的**白色格子段**的个数

那么根据之前的分析，可以尝试将之前分的不同的块，进行**合并**，具体来说
就是长度都为$$l_i$$的**白色段**合并到一起（按长度合并），`cnt[li] += xxx`

> 这启发我们用单调栈，找到左边或者右边第一个$$\geqslant a_i$$的元素的位置

![](/media/content_img/CF-EDU150-E-01.jpg)

如图所示，可以用**两次单调栈**

* 第一次扫描$$r = 0 \sim n+1$$（两侧需要补上边界 `a[0] = a[n+1] = n`）
  找到左边第一个 $$\geqslant a_r$$ 的位置$$l$$，（这里是为了填补凹陷部分）
  然后尝试找到区间最大值 $$mx = \max(l+1, r-1)$$
  令 `cnt[ r-l-1 ] += a[r] - mx`

* 第二次扫描，令$$l = 0 \sim n+1$$，注意此时如果中间隔着若干 $$= a_l$$ 的位置$$k$$，
  需要“跨过”这些位置，怎么跨过呢？实际上我们要找到右边第一个$$> a_l$$ 的位置$$r$$
  （这样实际上取 $$\max$$ 的时候，这些位置的值恰好是$$a_k = \max = a_l$$）
  这样就填补了“不平整的空缺”，令`cnt[ r-l-1 ] += a[l] - mx`
  
 > 为什么这样做是对的呢？
    因为对于所有隔在$$[l+1, r-1]$$的，满足$$a_k = a_l$$ 的位置$$k$$
    此时 $$a_l - mx = a_l -a_k = 0$$，没有贡献
	只有在**最右边**的$$a_l$$，也就是说$$a_r$$严格大于$$a_l$$，且中间没有隔着$$= a_l$$的数的时候
	$$a_l - mx \neq 0$$，这样恰好能填补**不平整的空缺**
	
这样基本就做完了，找区间最值$$mx = \max(l+1, r-1)$$可以用**ST表**

### D
**[D. Pairs of Segments](https://codeforces.com/problemset/problem/1841/D)**
**问题描述**
给定$$n$$个线段$$[l_i, r_i]$$，从中删除尽量少的线段，使得
*  剩余的线段数量是偶数
*  剩余的线段可以两两配对，满足
   - 属于同一对的两个线段可以有交
   - 任意不属于同一对的两个线段无交
   
请你求出最少删除多少个线段才能满足要求
$$n \leqslant 2000, 0 \leqslant l_i < r_i \leqslant 10^9$$

**算法分析**
先回顾一下**区间选点问题**，和**最大不相交区间数**

**区间选点问题**
给定若干个区间，取尽量少的点，使得每个区间内最少都有$$1$$个点

> 贪心策略
   *  将所有区间按**右端点**从**小到大**排序，**右端点**相同按左端点小到大排序
   *  依次枚举每个区间，每个区间检查区间的**最右端点**，选择的点的集合记为 `vec`
      如果当前的区间已经包含上次选的点 `vec.back()`，跳过该区间
	  否则就需要把该区间的**最右端点选上**，`vec.push_back(seg.r)`
	  
贪心策略的证明
根据贪心策略的排序，可以发现，对于某个区间$$[l_i, r_i]$$，当我们把选的点的位置移动，
$$k \to r_i$$，可以发现，被满足的区间只可能增加
其他区间在 $$[k+1, r_i]$$这一段，原先不满足，现在满足了，而之前已经满足的呢？

根据数学归纳法，在$$i-1$$阶段$$[l\_{i-1},r\_{i-1}] \to [l\_i, r\_i]$$
其中$$[r\_{i-1} + 1, l\_i]$$ 这一段，因为我们选的点就是$$r\_{i-1}$$，所以这一段已经被**满足了**

现在要在$$[r\_{i-1}+1, r\_i]$$中选一个点，因为我们是按右端点排序的
所以$$j \in [i+1\cdots n]$$这些线段的右端点都$$\geqslant r_i$$，左端点$$l_j < r_i$$
选择$$r_i$$这个点，一定能够覆盖到$$j > i$$，并且和$$[l_i, r_i]$$**相交的所有线段**

这样贪心答案是不劣的

**最大不相交区间的数量**
给定$$n$$个闭区间，选择若干个区间，使得被选中的区间之间互不相交
问**最多能选几个区间**？

注意到，相交的几个区间，只能选一个，同时，相交的区间可以用一个**公共点**表示
按**区间选点**的做法，得到的答案就是最优解

> 和区间选点问题一模一样
   *  如果几个区间都被一个点覆盖，那么代表这些区间相交
   *  由此，选几个点就代表有几个不相交区间
   
下面证明，这个答案就是最优解，假设区间选点求出的答案是`res`，而最优解是`ans`

* 显然$$res \leqslant ans$$，因为$$ans$$是**最大**不相交区间数

* 下面证明$$res \geqslant ans$$，因为$$ans = m$$是最大不相交区间数
  所以对于**不相交区间** $$\left< [l_1, r_1], \cdots [l_m, r_m] \right>$$
  每个区间$$[l_i, r_i]$$都**一定要选一个点**，才能够使得每个区间都至少有一个点
  而剩下的，与这些$$[l_i, r_i]$$**相交**的区间，可以不选点
  所以选择的点的个数一定会$$\geqslant m$$，也就是$$res \geqslant ans$$
  
综上所述，$$res = ans$$

**算法实现方法一**
本例的算法实现，删除尽可能少的线段，实际上就是选择**尽可能多的段**
考虑$$n \leqslant 1000$$，可以通过$$O(n^2)$$的预处理，对于每一个位置$$i$$的线段$$s_i$$
尝试找到线段$$s_j$$，使得$$s_j$$与$$s_i$$**相交**
如果找到了，将$$s_i$$与$$s_j$$线段的并放入集合$$V$$中

这样我们就得到了一些线段集合$$V$$，在集合$$V$$中，找到**最大不相交区间数量**
就是答案

**算法实现方法二，动态规划**
所有线段按右端点排序
用$$f_i$$表示选择线段$$s_i$$，此时满足条件的最大线段**数量**，那么可以$$O(n^2)$$预处理
找到这样的$$j$$，满足$$j < i$$，并且$$r_j \geqslant l_i$$
对每一个满足条件的$$j$$，算出答案`res`，和`ans`取一个`max`即可

> 那么答案`res`如何计算？

尝试找到**最后一个满足右端点**$$< \min(l_i, l_j)$$的位置$$pos$$，那么
```math
\displaystyle
f_i = \left(\max_{k = 1}^{pos} f_k\right) + 2
```
其中$$\max$$部分是前缀最大值，可以一边扫描一边维护，用`g[pos]`来表示
那么实际上 `f[i] = max(f[i],  g[pos] + 2)`
计算完成之后，更新前缀最大值，`g[i] = max(g[i-1], f[i])`，同时用`f[i]`来更新`ans`

## Codeforces Round 878 (Div. 3)
**[E. Character Blocking](https://codeforces.com/problemset/problem/1840/E)**
**问题描述**
给定两个相同长度的字符串 $$s_1, s_2$$，和一个计时器$$t$$，下面有$$q$$个询问
第$$i$$个询问在第$$i$$秒发生

*  `1 pos`，表示 $$s_1[pos]$$处的字符被封禁，封禁持续时间$$t$$秒
   假设这个询问是$$q_j$$，那么在$$j+t$$个询问处，这个字符解封

* `2 1/2 pos1 1/2 pos2`，表示将第`1 or 2`个字符串的`pos1`位置的字符，
   和第`1 or 2`个字符串的`pos2`位置的字符交换（保证这两个字符都没有被封禁）
   
*  `3` 查询操作，问除去被封禁的字符外，两个字符串是否相等

**算法分析**
字符串的**单点修改**，注意到本例中，$$s_1, s_2$$ 的`block`**位置是一样的**
所以对于`block`操作，可以**字符串哈希**来维护，假设`block`的位置是`i`
$$sha = sha - s[i] \cdot P^i$$，解除`release`操作也是如此，把对应的字符加回来即可

`2` 操作，`c1->c2`，只需要对相应的位置`del(pos, c1), add(pos, c2)`就可以了
**值的注意的是**，`s1, s2`原串相应的位置也需要更改

`3`操作，判断相等，只需要判断`sha`值是不是一样就可以了

## Codeforces Round 876 (Div. 2)
**[D. Ball Sorting](https://codeforces.com/contest/1839/problem/D)**
**问题描述**
$$n$$个球排成一列，每个球的颜色都互不相同，并且都在$$[1, n]$$范围内
换句话说，给定一个$$1 \sim n$$的排列
第$$i$$个球的颜色为$$c_i$$，现在你需要重新排序，使得第$$i$$个球的颜色为$$i$$
另外你还有$$k$$个颜色为$$0$$的球，这些球在排序的时候可以用到

你可以通过以下两种方式将球排序
*  将颜色为`0`的球插入到序列中任意位置，你只能执行这种操作$$k$$次

*  选择一个和`0`的球相邻的非`0`球，将其取出并且放到序列中任意位置，执行这一操作花费为$$1$$

执行完这些操作之后，所有颜色为$$0$$的球会消失，问最少会有多少花费
对所有的$$k \in [1, n]$$求出答案

**算法分析**

> 注意到原序列中可能已经有**完整的段了**

不妨设原序列中有一些单调递增的段$$S$$
比如 `[..., 2, 3, 4, 5, ...]` 或者 `[..., 2, 3, 4, 9, ...]`，这些段是**不需要动**的
要么这些段**完整**，刚好满足`a[i] = a[i-1] + 1`
要么缺一些元素，其他位置元素**错位了**
此时错位的元素需要通过操作`2`移入对应的$$s$$中，每一个错位元素代价是`1`
但不论如何，单调递增的一段是不需要动的，这样的段叫做**递增段**，段中的元素可以认为是**合理的**

> 可以尝试把序列划分成若干个**递增段**，段与段之间用操作`2`，把错位元素**归位**

考虑`dp`，$$dp_{i, k}$$ 表示$$i$$**在递增段中**，到$$i$$为止（包括$$i$$）
用了$$k$$次**操作`2`**，此时的最小代价

*  $$a\_{i-1} < a\_i$$，存在转移$$dp\_{i, k} \leftarrow dp\_{i-1, k}$$（因为$$a\_{i-1}$$不需要断开成新的段）
此外，还有以下转移

*  不论什么情况，都存在转移，满足
   ```math
   \displaystyle
   \begin{cases}
   [1 \leqslant j \leqslant i-1][a_j < a_i] \\
   dp_{i, k} \leftarrow dp_{j, k-1} + (i-j-1)
   \end{cases}
   ```
   此时在 $$a_j < a_i$$ 的位置，需要将$$j$$所在的段和$$i$$所在的段**合并**，
   并且把$$[j+1, i-1]$$中的元素通过操作`2`，移动到合适的位置
   额外产生代价$$(i-j-1)$$
   
> 这样做为什么是正确的呢

因为一段序列，要么 $$[\cdots, 2, 3, 4, 5, 6 \cdots]$$ 是完整的一段，要么 
$$[\cdots, {\color{red}{2, 3,} { \color{blue}{7, 8, 9} } }] \to [\cdots, { \color{red}{2, 3} }, {\color{blue}{7, 8, 9}}, { \color{red}{4, 5, 6} }] \to [\cdots, 2, 3, 4, 5, 6] \cup [7, 8, 9]$$

也就是说，对于$$i-1 \to i$$，要么$$a\_{i-1}, a\_i$$ 都属于一个段
要么$$a\_{i-1}$$原来是在$$a_j$$处，把$$[j+1, i-1]$$的元素都移走，拼接而成
这两种情况都对应$$j < i, a_j < a_i$$

另外，因为序列是一个排列，最后做到 $$dp_{n+1, k}$$ 的时候，总能找到一个合法的解

**边界需要处理**，令$$a\_0 = 0, a\_{n+1} = n+1$$
特别注意，需要另外加上边界$$a\_{n+1} =n+1$$，因为可能**整个序列**就是完整序列
此时$$dp\_{n+1, k}$$就表示$$[1\cdots n]$$都作为完整的一段的情况

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

看完文章有啥想法