codeforces数据结构专题（三）

[[ slider_text ]]

[[ item.c ]]

codeforces数据结构专题（三）

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

线段树

## Codeforces Round 877 (Div. 2)
**[D. Bracket Walk](https://codeforces.com/problemset/problem/1838/D)**
**问题描述**
给定一个长度为$$n$$的括号序列，从序列的左端点出发，可以向右走或者向左走，但不能走出界。你可以访问一个字符（包括起点和终点）任意次。
当你走到一个字符的时候，你写下当前的字符，如果存在一种方案，使得
你记录走过的括号形成的括号序列，可以**括号匹配**，称这个括号序列是**可行走的**

你有多个询问，每个询问会修改一个位置的状态，（左括号变成右括号）
你需要判断修改后的括号序列是否为可行走的，询问之间**互相影响**，每次询问都会影响到接下来的询问

**算法分析**
首先，括号序列长度是奇数，一定不行

> 什么情况下一个括号序列是合法的？

如果令`( = 1`，`) = -1`，对于括号串$$s$$
任意位置$$\forall i \in [1, n]$$，有$$S_i \geqslant 0$$（$$S$$是前缀和）
并且，$$S_n = 0$$

> 贪心地想，在任意位置$$\forall i$$，要令`(`尽可能多，这样才能保证$$S \geqslant 0$$

形如`...((...`的序列，都可以通过**来回游走**，构造出想要的`(`数量
假设`(((((`的长度是`len`，可以通过$$d \leqslant len$$，由$$d+2k$$次行走，构造出想要的`(`
而 `)` 呢？同理，和`(`是对称的，只需要翻转序列，并且令`(`和`)`**互换**即可

那么对于`()`的段呢？注意`()`的段不应该去破坏它，因为正好是匹配的括号
可以直接**跨过**这个子段，去考虑接下来的段
（另外，这样的段也无法通过**来回游走**来产生更多的`(`）

> 那么接下来怎么去实现呢？

可以这么来设计算法，找到**连续**的形如`...((...`的`(`位置，不妨设这个位置是$$p$$
那么需要考虑$$[1, p-1]$$这一段是否合法（下标从$$1$$开始），怎么**判合法呢**

可以考虑使用**线段树**，`for`一遍整个字符串
如果$$s_i = ($$，那么相当于$$[i\cdots n]$$ 每个数都$$+1$$
反之如果$$s_i = )$$，那么$$[i\cdots n]$$每个数都$$-1$$
这样，一个位置$$i$$是否**合法**，只要判断这个**位置的值**是否满足$$val(i) \geqslant 0$$

那么一个**子段**$$[l, r]$$是合法括号串的话，必须满足$$i \in [l, r]$$每一个位置
都有$$val(i) \geqslant 0$$恒成立，也就是说，只要维护$$[l, r]$$的**区间最小值**
看看是否满足$$minv \geqslant 0$$即可

> 这样的话就可以做了

用线段树维护区间最小值，对于`s[i] = (`，区间修改`[i, n] += 1`，否则`[i, n] -= 1`
另外用`set`维护连续的`((`的位置，并按问题描述进行修改
比如`i`位置从`(`改成`)`，那么会影响`i-1, i`两个位置，这两个位置现在都不是连续`(`了
要从`set`中删掉

同时，`i`位置`(`改成`)`，需要区间修改`[i, n] -= 1, [i, n] += (-1)`
也就是`[i, n] -= 2`

最后判断一下`set`中最小的值，也就是下标$$p$$，查询$$[1, p-1]$$是否$$\geqslant 0$$，返回`ans1`

翻转字符串再做一遍，得到结果`ans2`，当`ans1 && ans2 = true`的时候，结果为可行的
**特别注意**，翻转字符串的时候，对于每一个`query`，每个询问会修改一个下标处的值
这个**下标位置也要反转**，`p = n-1-p`

## Educational Codeforces Round 149
### F
**[F. Editorial for Two](https://codeforces.com/problemset/problem/1837/F)**
**问题描述**
给定一个长度为$$n$$的序列，从中找出长度为$$k$$的子序列，子序列可以不连续，
需要将这个子序列划分成前后两个部分，分别求出前一半子序列的元素和，后一半的元素和
要求这两个元素和的**最大值尽可能小**，输出这个**尽可能小的值**

**算法分析**
> 最大值最小，不难想到**二分答案**

假设这个**使得最大值最小**的值是$$mid$$，我们把序列划分成左右两段$$A, B$$
记$$SA, SB$$分别表示左右段的**元素值的和**，$$cA, cB$$分别表示左右两段**元素个数**
那么必须满足 $$SA \leqslant mid, SB \leqslant mid, cA + cB \geqslant k$$

> 那这样我们还是没法做，因为我们不知道$$A, B$$有哪些元素，$$SA, SB, cA, cB$$无从求得

贪心策略是，如果使得$$SA$$尽量小，那么$$cA$$就可以取得更多，更有可能满足$$\geqslant k$$
因为**不能改变**元素顺序，需要用一种数据结构来维护$$SA$$

> 这样好像可以做了

扫描一遍整个序列，用$$sum$$来维护**元素值的和**，选取尽量多的元素
如果$$sum > mid$$，需要**从大到小**删除**值太大的元素**，直到恰好$$\leqslant mid$$ 为止

这样做的话，每一个位置都有一个值$$dp_i$$，表示$$[0, i]$$前缀中
最多能选取$$dp_i$$个数，实际上，$$dp_i$$就是**堆中元素的个数**

用**大根堆**可以实现添加和删除操作，这样$$A$$这半段就解决了

考虑$$B$$这后半段，只需要**倒着做一遍**，对于每一个位置，维护当前$$[i, n]$$后缀中
能选的最大的数，实际上就是堆中元素的个数`sz = heap.size()`
当且仅当$$sz + dp(i-1) \geqslant k$$ 的时候，$$mid$$是一个合法解

**注意**，代码实现的时候，$$dp_i$$表示考虑$$a_i$$这个数**一定要选**，并且将其放入堆中
所以维护堆的操作应该是
```bash
for i = 1 to n:
	sum += a[i], heap.insert(a[i]);
	while (sum > mid && heap.size()) sum -= heap.top(), heap.pop();
	dp[i] = heap.size();
```

> 这样才能保证考虑到所有情况，因为如果你不选$$i$$，那么你最后一个选的数，
假设是$$i-1$$，这种情况会在$$dp\_{i-1}$$的时候考虑到

## Codeforces Round 879 (Div. 2)
### E
**[E. MEX of LCM](https://codeforces.com/problemset/problem/1834/E)**
**问题描述**
一个长度为$$n$$的序列$$a$$，我们称一个数$$x$$是**好数**，当且仅当
在序列$$a$$中**不存在**任何一个子段$$[l, r]$$使得$$[l, r]$$的最小公倍数等于$$x$$
现在要求最小的**好数**

**算法分析**

> 想一想区间 mex 问题是怎么做的？
  区间`mex`问题中，可以分析出`mex`的值不会超过$$n+1$$

对于每个区间$$[l, r]$$，遍历$$r$$，考虑$$l$$，找到$$pos_x < l$$的最小的数$$x$$
然后记 $$pos_r = r$$
也就是说，此类问题从**值域**角度考虑，记一下每个数$$x$$的**最后一次出现**，是这种问题的常用方法

> 在本例中，能不能也这样分析呢？不妨用`mp`记一个数**出现**
   $$\text{mp}\left<a, b \right> = 1$$ 表示$$a, b$$都出现

考虑一段区间$$[\cdots i] = \text{lcm}$$，对于$$\forall i, \ [1\cdots i]$$，有
$$\text{mp}\left< a_i, \text{lcm}/a_i  \right> = 1$$，这启发我们考虑

> $$[l, r] \to [l, r+1]$$，$$\text{lcm}$$是怎么变化的，考虑$$lcm \to lcm2$$ 
   
*  $$(lcm, a\_{r+1}) = 1$$，有$$lcm2 = lcm \cdot a\_{r+1}$$

*  否则，我们有 $$\displaystyle lcm2 = \frac{lcm \cdot a\_{r+1}}{gcd}$$

那么来分析最后的答案$$x$$

*  $$x$$如果是质数，那么质数一定不可能成为$$lcm$$的，最坏的情况
   $$[1\cdots n]$$子序列$$lcm$$取遍$$< x$$的所有数，包括**质数**
   那么$$x$$是就一定是第$$n+1$$个质数，答案一定不会超过$$p\_{n+1}$$，可以打表求出这个上界

* 如果$$x$$是合数，那么考虑$$lcm \to lcm2 \to \cdots$$，根据之前的分析
  要么$$lcm$$不变，要么$$lcm2 = lcm \times (a\_{r+1} / gcd) = O(2 \cdot lcm)$$
  也就是说，满足$$< x$$的，**已出现过**的$$lcm$$，有 $$\left< lcm, 2lcm, 2^2 lcm \cdots \right> < x$$
  出现过的$$lcm$$最多有$$O(\log x)$$个
  
> 这样好像就可以做了，记$$A$$为已经出现过的$$lcm$$值的集合

```math
lcm(a_l, a_{l+1}, \cdots, a_r) = lcm \left(a_l, lcm(a_{l+1}, a_{l+2}, \cdots, a_r)\right) \\
\cdots = lcm(a_l, A)
```
**注意到**，假设$$[l\cdots j \cdots r]$$，我们要求$$lcm[l, j]$$，实际上从后往前遍历
$$lcm(a\_{l+1}, \cdots, a_j)$$ 已经计算出来并且用$$A$$维护好了
只需要将$$a_l$$和$$A$$中的元素取$$lcm$$就可以了

> 算法实现

先打表求出答案的上界，第$$n+1$$个素数$$N$$，最后的答案一定$$\leqslant N$$
考虑$$r = n \to 1$$，暴力维护$$r \to r-1$$时候可能的值是如何变化的

用一个`set`来维护`[r, n]`已经出现过的`lcm`的集合，记为$$A$$，当`r = r-1`的时候
考虑$$A \to tA$$，先将`a[r]`放入集合$$tA$$中，然后遍历集合$$A$$中的每个元素$$v$$
求出$$v = lcm(v, a_r)$$，再将新的$$v$$插入集合$$tA$$中

这样我们就得到了**新的集合**$$tA$$，将$$tA$$中的元素放入集合$$res$$中
$$res$$记录的就是$$[r\cdots n]$$的任意连续子区间出现的$$lcm$$
然后再将$$A \leftarrow tA$$

最后只需要暴力统计$$res$$中的`mex`即可，由于集合中最多只有$$O(\log N)$$个元素
复杂度为$$O(n \log ^2 N)$$

## Codeforces Round 879 (Div. 2)
### D
**[D. Survey in Class](https://codeforces.com/problemset/problem/1834/D)**
**问题描述**
有$$n$$个学生对课堂的问题进行了预习，有$$m$$个问题，第$$i$$个人预习的问题是一个区间$$[l_i, r_i]$$
老师可以问一些问题，这个问题编号$$k \in [1, m]$$，没有规定需要问几次
**但是**，每一个问题只能被提问一次
对于这$$n$$个同学，如果一个人不会，那么它的分数$$-1$$，否则$$+1$$
现在需要**最大化**学生得分的**极差**，并且输出这个值

**算法分析**
> 先考虑如何计算两条线段$$[l_i, r_i], [l_j, r_j]$$，考虑线段$$i$$

不难发现，对于线段$$i$$（$$lap$$表示两条线段的覆盖长度）
```math
\displaystyle
f_i = \max_j \left( len_i - lap_{i, j} \right) = len_i - \min_j (lap_j)
```
**对答案的贡献**是$$2f_i$$

* 考虑线段和$$[l_i, r_i]$$是**相交但不包含**的关系，那么极差只会在$$i$$和与其相离最远的线段中产生
   即令$$lj = \max(l_j), rj = \min(r_j)$$
   那么 $$lap_j = \min (|rj-l_i+1|, |r_i-lj+1|)$$（如果是负数，和`0`取`max`）

* 否则，如果存在包含关系，那么在$$[l_i, r_i]$$区间内，取**最小覆盖**，即区间最小值
  这可以用**线段树**维护，线段树一开始区间值都是$$+\infty$$，尝试找到
  $$l_j \in [l_i, r_i]$$ 内，最小的$$lap_j = len_j$$
  如果将所有线段按照**右端点排序**，当考虑$$r_i$$的时候，先做一次区间查询
  查询$$[l_i, r_i]$$最小的$$len$$，然后再将线段$$i$$插入线段树中即可
  
  本例涉及离散化，用$$(l_i, r_i, len_i)$$表示线段，$$len_i$$为线段**初始长度**
  只需要将所有线段**挂载**到左端点，线段树**叶节点**$$i$$的值表示，所有以$$i$$为左端点的线段的**最小长度**
  这样只需要做一次区间查询$$[l_i, r_i]$$就可以知道这个最小的$$lap_j$$
  然后**单点修改**，$$l_i \to \min(v(l_i), len_i)$$（其中$$v(l_i)$$表示线段树$$l_i$$叶节点的值）

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

看完文章有啥想法