codeforces 721，数据结构优化问题

[[ slider_text ]]

[[ item.c ]]

codeforces 721，数据结构优化问题

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

线段树 莫队 数据结构优化dp dp

## codeforces 721 E. Partition Game
**[Partition Game](https://codeforces.com/contest/1527/problem/E)**
给定一个序列，**划分成若干段**，每一段看成一个集合，这一段的权值定义为
```math
\displaystyle
cost(t) = \sum_{x \in set(t)} last(x) - first(x)
```
即所有数最后一次出现的位置，减去它第一次出现的位置，得到的值加起来
现在问，将序列划分成若干段，能得到的**最小权值**是多少？

**算法分析**
直接 `dp` 的话，假设当前的位置是 $$i$$，我们根据**最后一段**的划分情况来 `dp`
记 $$dp(i, j)$$ 表示，当前在位置$$i$$，划分成$$j$$段所得到的最小值，考虑最后一段如何划分
```math
\displaystyle
dp(i, j) = \min_{\substack{0 \leqslant k < i \\ 0 \leqslant j-1 \leqslant k}} \left(dp(k, j-1) + w(k+1, i) \right)
```
其中$$w$$表示权值，直接做时间复杂度是 $$O(n^2 k)$$

**算法优化**

> 注意到 $$0 \leqslant j-1 \leqslant k$$ 这一维很小，只有 $$100$$，可以根据这一维**分层**
   对于答案数组，**每一层**都用一个数据结构来维护，具体来说
   ```bash
   for j in 0 -> k:
       用数据结构维护 min{ .... } 的结果
   ```
   
注意到，$$j$$ 的结果仅和 $$j-1$$ 有关，根据滚动数组
令 `f2(*) = dp(*, j), f1(*) = dp(*, j-1)`，这样有 $$dp(i, j) = f2(i), \ dp(k, j-1) = f1(k)$$
```math
\displaystyle
f2(i) = \min_{0 \leqslant k < i} \left( f1(k) + w(k+1, i) \right)
```
令 $$g(k) = f1(k) + w(k+1, i), \quad k \in [0, i-1]$$
（假设现在考虑第$$j$$层）

> 注意到$$k$$的范围是$$i$$的**前缀**，这**很重要**
   这样只要在遍历 `for i = [1, n]` 的时候，用**线段树**来维护$$g$$数组
   求出 $$[0, i-1]$$ 的**前缀最小值**，来作为 $$f2(i)$$ 的答案
   
>  查询答案解决了，怎么修改和维护呢？注意到当我们检查$$i$$位置的时候
   $$f1(k) = dp(k, j-1)$$，这个值实际上我们在考虑$$j-1$$层的时候已经**算出来了**
   $$f1(k)$$ 是相对不变的，变的只有 $$w(k+1, i)$$
   当 $$i-1 \to i$$ 的时候，区间变化 $$[k+1, i-1] \to [k+1, i]$$，$$w$$值会怎么变？
   
>  如果 $$a_i$$ 没有在 $$[k+1, i-1]$$ 中出现过，值不变
    如果 $$a_i$$ 在 $$[k+1, i-1]$$ 中出现过了，即 $$last(i) \geqslant k+1$$
	`ans = ans - (last - first) + (i - first)`，`ans = ans + (i - last)`，值增加了$$i - last$$
	
>  注意到，实际计算中，我们先遍历 $$j \in [1, k]$$，依次计算每一层
   **每一层**计算的结果都保存在`f2`数组中
   然后根据上一次 `f2` 的值，计算当前$$j$$的答案，**覆盖**`f2`
   所以可以直接用线段树维护`f2`数组，每一层**计算之前**，先根据上一次`f2`的结果建线段树维护

**算法实现**
		
**初始化**时，$$f2$$ 数组除了 $$f2(0) = 0$$ 之外，其他位置一开始都是 $$+\infty$$

遍历$$(j-1) \in [0, k]$$这一层，并根据$$f2$$数组**建一颗线段树**维护
	
对于$$j$$，`for i in [1, n]`，找到$$a_i$$上一次出现位置$$last(i)$$
对于所有的 $$k \in [0\cdots last(i)-1]$$，这些数都要加上 $$i-last$$
也就是说，对于当前$$i$$**前缀修改**，令$$[0, last(i)-1]$$ 区间**最小值加**$$i-last$$

对当前的$$i$$，执行 $$\displaystyle f2(i) = \min_{0 \leqslant k \leqslant i-1} g(k)$$
> **实际上**$$g(k)$$的信息保存在了$$j-1$$层计算出的$$f2$$数组中
  而线段树此时维护的恰好是`f2`数组

执行 $$[0, i-1]$$ 的**区间最小值**查询，就是 $$f2(i)$$ 的答案

扫描到最后，$$f2(n)$$ 就是题目所求的最终答案

## 最大和上升子序列
**问题描述**
给定 $$a_1, \cdots, a_n$$，找到 $$m$$ 个位置 $$p_1, p_2, \cdots, p_m$$
满足 $$1 \leqslant p_1 < p_2 < \cdots < p_m \leqslant n$$，并且
```math
a_{p_1} < a_{p_2} < \cdots < a_{p_m}
```
使得 $$a\_{p\_1} + a\_{p\_2} + \cdots + a\_{p\_m}$$ 最大

**算法分析**
最大和上升子序列有 dp 做法，记 $$dp(i)$$ 表示
以下标 $$i$$ 结尾的**最大和上升子序列**，那么我们有
```math
\displaystyle
dp(i) = \max_{ \substack{1\leqslant j < i \\ a_j < a_i } } \left( dp(j) \right) + a_i
```
**算法设计**
> 直接实现时间复杂度是 $$O(n^2)$$，其实主要的开销在于求 $$\displaystyle \max\_{\substack{1\leqslant j < i, a_j <a_i} } dp(j)$$ 的开销

> 最好能在 $$O(1)$$ 或者 $$O(\log n)$$ 的时间复杂度内求出 $$\max dp(j)$$

实际上，我们在求 $$dp(i)$$ 的时候，$$dp(1\cdots j)$$ 也已经都求出来了
对于 $$a_j < a_i$$ 这个条件，能不能把 $$a_j$$ 看作下标？不妨假设用数组 $$P$$ 维护
这样实际上我们只需要求 $$[1\cdots a_i - 1]$$ 下标范围内的**前缀最大值**

用一个数组 $$P$$ 来维护$$\text{dp}$$值
记 $$P(x)$$ 表示所有满足 $$j < i, \ a_j = x$$ 的最大的 $$dp(j)$$ 的值，这样
```math
dp(i) = \displaystyle \max_{1 \leqslant x < a_i} P(x) + a_i
```
计算出 $$dp(i)$$ 之后，维护 $$P(a_i) = \max(P(a_i), dp(i))$$

这对应的操作是**单点修改，前缀查询**，可以考虑线段树或者树状数组来解决
实际上单点修改是修改下标 $$a_i$$ 这个位置，前缀查询对应 $$[1, a_i-1]$$

> 特别说明，线段树维护最大值是肯定可以的，但是树状数组不一定可以
   只有单点修改，对 $$a_x \ \uparrow$$，即将 $$a_x$$ 值**变大**，树状数组才可以正确维护
   否则的话，对 $$a_x \ \downarrow$$，值**变小**，是不可以的
   因为如果单点修改，**值变大**，只需要将树状数组**前缀max**和修改后的值取一个**max**即可
   但是**值变小**，我们并不知道值变小之后，树状数组新的$$\max$$值是多少
   
## 区间 lower bound 查询
**问题描述**
给定 $$n$$ 个数 $$a\_1, \cdots, a\_n$$ 和 $$q$$ 个询问
`l r x` 询问 $$a\_l, a\_{l+1}, \cdots, a_r$$ 中 $$\geqslant x$$ 的**最小的数**

**算法分析**
> 首先满足 $$\geqslant x$$ 这个条件，第一时间都会想到线段树二分
   如果线段树维护区间**最大值** $$\max$$，如果区间 $$\max \geqslant x$$
   就说明区间**肯定有一个值满足条件**
   我们先往左子树找，看能不能找到，找不到就去右子树找
   
> 这样做的问题在哪里呢？这样我们可以找到**区间**最左边**满足** $$\geqslant x$$ 的数
   即**下标最靠左**的满足条件的位置，但是呢？
   我们找不到满足 $$\geqslant x$$ 的**值最小的数**，下标有单调性，但是本例中值没有单调性
   
 > 既然只能找到**下标最小**，不能找到**值最小**，那么能不能考虑对值域建线段树，将值变成下标？
 ![](/media/content_img/interval_lower_bound.png)
 
 如图所示，可以考虑将询问**离线**，对于某个询问 $$(l, r, x)$$，有一种想法是
 > 在询问$$x$$的时候，我们能不能使得，**区间中只有**$$\geqslant x$$**的数的信息**
 > 这样要询问区间最小的数，只要在线段树中维护区间**最小值**即可
 
 由此，可以借助**扫描线**的思想，用**事件**来表示询问和**既定点**
 询问用 $$(x, id, l, r)$$ 来表示，**既定点**用 $$(a_i, 0, i)$$ 来表示
 （第二维取$$0$$是因为，我们要保证**既定点**比查询**先插入**）
 
 假设线段树维护序列$$P$$，一开始的时候，令$$P$$中所有元素都是$$+ \infty$$
 **按第一维（值域坐标）从大到小**对事件排序，**第二维**从小到大排序（保证既定点先处理）
 
 遇到一个**询问事件**，可以保证线段树维护的数一定都是$$\geqslant x$$的
 （$$x$$在第一维，我们从大到小扫描）
 直接取询问区间$$[l, r]$$最小值即可
 
 遇到一个**既定点**，执行单点修改，`set(i, a[i])`，将`a[i]`加入线段树中

## 第 k 大查询
**问题描述**
给定$$a_1, \cdots, a_n$$，对于所有满足 $$r-l+1 \geqslant k$$ 的区间$$[l, r]$$，求这样的区间里的第$$k$$大元素
输出这些元素的和

**算法分析**
> 扫描线能做吗？对于$$r = 1 \to n$$，维护`ans[l]`表示$$[l, r]$$的第$$k$$大

> 很难做，扫描线维护最大值和最小值比较简单，但这样做需要套$$k$$层单调栈
   对于第$$k-1$$大的数$$x$$，继续维护左边第一个$$> x$$的元素
   也就是说，`stk(k, x)`表示第`k`个单调栈，`x`左边第一个$$> x$$的元素位置
   这样的时间复杂度是$$O(nk \log n)$$，不能通过题目数据
   
考虑每个数对**答案的贡献**，对于数$$x$$，考虑它在哪些区间是第$$k$$大的？
这样可以把 $$x \cdot cntl \cdot cntr$$ 加到答案中
其中$$cntl$$表示区间左端点能选择多少个数

> 举个例子，$$k = 1$$时，找到$$x$$左边第一个$$> x$$的位置$$l$$
   和右边第一个大于它的位置$$r$$，那么所求的区间，必须只能包含一个$$x$$
   左端点可以选$$[l+1, pos_x]$$，右端点可以选$$[pos_x, r-1]$$
   
> 
  $$k=2$$ 时也类似，区间除了$$x$$之外还需要再选择$$k-1 = 1$$ 个元素
   往左找 $$2$$ 个$$> x$$ 的位置$$(l_1, l_2)$$，右端点同理$$(r_1, r_2)$$
   如果左端点取$$[l_2+1, l_1]$$，那么右端点只能取$$[pos_x, r_1-1]$$
   同理，左端点取$$[l_1+1, pos_x]$$，右端点能取$$[r_1, r_2-1]$$
   
> 那么取 $$k$$ 个的时候呢？能归纳一下吗？

记 $$l\_0 = r\_0 = pos\_x$$，左区间最远能取$$[l\_k+1, l\_{k-1}]$$，那么右边呢？
只能取$$[r_0, r_1 - 1]$$了，那么左端点考虑 $$j = 1 \to k$$ 这一段
```math
L \in [l_{j}+1, l_{j-1}]
```
此时右端点
```math
R \in [r_{k-j}, r_{k-j+1} - 1]
```
所以对于数$$x$$，分别往左，往右找$$k$$个$$> x$$的数，对答案的贡献就是
```math
x \cdot (l_{j-1} - l_j) \cdot (r_{k-j+1} - r_{k-j})
```

> 现在的问题就是，怎么找$$k$$个$$> x$$的数？

>   有一种想法是，从**大到小**遍历，`for x = n -> 1`，并且用`set`来维护**数的下标**
    这样遍历到`x`的时候，`set`维护的都是$$>x$$的数的下标
	这样在`set`中找到第一个$$\geqslant pos_x$$ 的位置
	找$$k$$个前驱，$$k$$ 个后继，这样就可以做了，但是复杂度是$$\log$$的
	
> 我们需要一个快速找前驱，后继的算法，什么呢？**链表！**
  因为`set`的做法我们从**从大到小插入数**来想，如果反过来，**从小到大删除**呢？
  
可以一开始从小到大**遍历值域**，`for x = 1 -> n`，其中`x`的下标记为`pos[x]`
求解完成后，将值为`x`的位置从链表中**删除**

这样对于`x`，可以保证`x`往左，往右的元素都$$> x$$
只要沿着链表往左，往右走$$k$$步，将**下标结果**分别存在`left[...], right[...]`中
> 说明，分别对应之前分析的`l[j], r[j]`

按之前分析的计算即可

## 序列维护
**问题描述**
维护$$n$$个序列$$p_1, \cdots, p_n$$，一开始都是空的，下标从$$0$$开始，维护$$q$$个操作

`1 x y`，往序列$$p_x$$末尾插入一个数$$y$$，序列下标都是$$0$$开始
`2 z`，对于所有**非空**序列$$p_i$$，求
```math
p_{i, z\bmod |p_i|}
```
  其中，$$|p_i|$$表示序列$$|p_i|$$的长度
  
**算法分析**
> 先考虑**静态**问题，假设我们没有插入操作吗，怎么做？

可以根据序列长度**分类**， 对于长度为$$len$$的序列，是可以合并的
假设序列$$|p_i| = |p_j| = len$$，那么我们要求的，实际上是
对所有**长度**为$$len$$的序列，下标$$(z \ \bmod \ len)$$ 的和

对于$$|p_i| = |p_j| = len$$ 的序列，可以考虑维护 `for k = [0, len-1]`
```math
s(len, k) = p_i(k) + p_j(k)
```
这样查询操作就解决了

> 那么插入呢？

假设对$$p_i$$插入一个数$$y$$，实际上，我们要从$$s(len)$$中减掉$$p_i$$，然后插入
$$p_i(len+1) = y$$，并且令 $$len \leftarrow len+1$$，再继续令 $$s(len) += p_i$$
这样做**序列加减**需要`for k = [0, len-1]`，时间复杂度是$$O(len)$$

> 对于 $$len$$ 很小的情况，这样做是没有问题的

实际上，因为最多只能插入$$q$$个数，所以$$|p_1| + |p_2| + \cdots + |p_n| = q$$
那么 $$|p_i|$$ 最多只能有 $$\sqrt{q}$$ 个不同的取值
换言之，如果$$len$$都很小，实际上只有$$O(\sqrt{q})$$个不同的序列
我们只需要合并 $$O(\sqrt{q})$$ 次，代价是$$O(len \cdot \sqrt{q})$$

> 那么对于$$O(len)$$ 很大的情况呢？

肯定是不能合并了，但注意到$$len$$很大的序列一定不会很多，否则$$|p_i|$$的和就超过$$q$$了
实际上，如果按照$$len \leqslant \sqrt{q}$$ 来**分块**，$$len$$ 很大的序列最多只有$$n / \sqrt{q}$$个

这个时候，对于$$|p_i|$$ 很大的 $$i$$，直接暴力，具体来说
把这些$$i$$单独用`Large`标记出来，然后插入就是$$p(i)$$的`push_back`操作
统计的时候，`for i in Large`，暴力令`ans += p[i] [ z mod |p[i]| ]`

## 小米邀请赛 E. Phone Network

上一篇：莫队算法与根号分治下一篇：可持久化权值线段树

看完文章有啥想法