codeforces数据结构专题（一）

[[ slider_text ]]

[[ item.c ]]

codeforces数据结构专题（一）

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

线段树 数据结构优化dp dp 树链剖分

## Educational Codeforces Round 151
**[D. Rating System](https://codeforces.com/problemset/problem/1845/D)**
**问题描述**
给定一个长度为$$n$$的序列$$a$$，保证每一项都不是$$0$$，一开始$$x = 0$$
对于$$1 \leqslant i \leqslant n$$，执行以下操作

如果$$x \geqslant k$$，那么 $$x = \max(k, x + a_i)$$，否则$$x = x + a_i$$
	
现在求$$k$$，使得$$x$$的值尽量大

**算法分析**
一般情况下，这类问题**拐点**很重要，本例中的拐点就是，前缀和$$S_i$$恰好等于$$k$$
> 什么情况下答案最优呢？假设$$a$$的每一项都$$> 0$$

此时$$k$$等于$$a$$的某个前缀和$$S_i$$，并且最终的最大值为 $$k + S_n - S_i, \ k = S_i$$

> 但实际上$$[i+1, n]$$这一段后缀，可能在某一个位置使得 $$S < k$$
  此时后缀 $$S[i+1, n] \neq S_n - S_i$$，而是 $$k + Ssuf$$
  其中 $$Ssuf$$ 为$$[i+1, n]$$的某一个**后缀和**，以此类推

那么我们可以尝试**枚举后缀**，假设当前枚举的后缀是$$[i+1, n]$$，后缀记为$$Ssuf$$
根据之前的分析，最优答案为$$k + Ssuf$$

注意到$$S[1\cdots i] \leqslant mx$$（`mx`是`[1, i]`的**最大前缀**）
另外我们要选取一个 $$k$$ 尽量大，使得 $$S[1\cdots i] \geqslant k$$
从而 $$k \leqslant S[1\cdots i] \leqslant mx$$，那么$$k = mx$$

也就是说，枚举后缀 $$[i+1, n]$$，$$Ssuf = S_n - S_i$$，此时取$$k = mx$$
$$mx$$为**前缀最大值**，`for` 一遍，考虑使得 `mx + S[n] - S[i]`最大，记一下`k = mx`即可

## codeforces round 881 (div3)
### F1, F2
**[F2. Omsk Metro (hard version)](https://codeforces.com/problemset/problem/1843/F2)**
**问题描述**
$$t$$组数据，每一组$$n$$个询问
初始的时候只有节点 $$1$$，权值为$$1$$，记当前的节点数为`cnt`，`cnt`初始值为`1`
* `+ v x`会在`v`下增加一个节点，编号为`cnt+1`，同时`cnt += 1`
   另外这个新节点只和`v`相连，权值为 `x = { +1 or -1}`
   
* `? x y k` 取出`x -> y`的路径，取出权值序列，问该序列是否存在**权值和**为$$k$$的子段？
  可以是空子段，此时权值和为`0`，存在输出`YES`，否则输出`NO`
  
**算法分析**

> 能否离线

很显然该问题可以离线，先将所有的`+`操作离线下来，然后建树，新建的节点权值为`0`
对于询问，每一个询问需要挂载之前的修改操作，每一个`+`操作对应$$(u, wgt)$$
即将节点`u`的权值修改成`wgt`

这样的话，一个询问`? x y k`，可以考虑其 `dfs` 序 $$[l(x), l(y)]$$

*  遍历这个询问挂载的所有修改操作`(u, wgt)`，对应单点增加，`add(l(u), wgt)`

*  求出 $$[l(x), l(y)]$$ 区间内的最大子段和和最小子段和`maxss, minss`
   如果 `minss <= k <= maxss`，那么存在，否则不存在
   
以上两个问题都可以在`dfs`序上建单点修改的线段树，用线段树求 $$[l(x), l(y)]$$ 的最小/最大子段和

> 但很遗憾，这样做**并不正确**，因为$$u \to v$$的**路径**并不是线段树`dfs`序中连续的一段
  **树链剖分**可以吗？注意到树链剖分将$$u \to v$$**路径划分成若干段区间**
  `[l1, r1], [l2, r2], ...`，但是相邻区间怎么合并呢？合并的规则用线段树`op`来定义
  
> 现在的问题是，若干条链比如`[li, ri]`，可能并不是线段树`dfs`序中连续的一段
   比如 `[li...hs...ri]`，中间可能**隔着其他条分支链**，这样怎么处理`minss, maxss`的合并呢？
   
**树链剖分**仍然是可行的，只不过对路径要**拆分成上升链和下降链**，`LCA`单独处理

*  首先离线所有操作，对修改操作，标记`change[u] = wgt`，这样在线段树中，
   可以用结构体`S( change[LCA] )`来表示，用于线段树节点合并
   
*  线段树求区间最大/最小子段和并不难
   ```bash
   S op(S a, S b) {
       S res;
	   res.maxp = max(a.maxp, a.sum + b.maxp);
	   res.maxs = max(b.maxs, b.sum + a.maxs);
	   res.maxss = max( { a.maxss, b.maxss, a.maxs+b.maxp } );
	   return res;
   }
   ```
   
*  现在需要把$$u \to v$$的路径拆成 $$[u, lca), \ lca, \ (lca, v]$$
   （$$lca$$单独处理，所以在一段路径中，$$lca$$是开区间）
   假设我们求出来`su = hld.path(u, lca), sv = hld.path(v, lca)`
   
   值得注意的是，树链剖分是**往上跳的**，最后求出来的路径是**向上**往$$lca$$走的，许多段重链
   `su, sv`都需要**`reverse`**一下，统一变成从`LCA`**往下走**的许多段路径
   
   另外因为`LCA`是开区间，`su[0] = [lca, xxx]`，要令`su[0][0] += 1, sv[0][0] += 1`
   从而变成考虑区间`(lca, xxx]`
   
* `for [ql, qr] : su, then res = op(res, [ql, qr])`，**注意**此时的结果
   是`LCA -> u`，而实际上我们的路径是`u->LCA`的，怎么办呢？很简单
   **翻转`maxp, maxs`**即可（最大前缀和最大后缀交换，最小前缀和最小后缀交换）
   `swap(maxp, maxs), swap(minp, mins)`
   
   然后再依次和`S(change[lca])`，**下降链**合并即可
   `res = op(res, S(change[lca]))`
   `for [ql, qr]: su, then  res = op(res, [ql, qr])`

### E
**[E. Tracking Segments](https://codeforces.com/problemset/problem/1843/E)**
**问题描述**
给定一个长度为$$n$$，初始值全为$$0$$的序列，我们定义一个区间是美丽的
当且仅当区间内$$1$$的个数**严格大于**$$0$$的个数，换言之，就是区间和$$S > len / 2$$
现给定$$m$$个区间和$$q$$次修改，每一次修改操作给定一个数$$x$$，能够将$$a_x $$从`0`改为`1`

下面问至少几次修改之后，$$m$$个区间中，至少一个区间是美丽的

**算法分析**
> 先想极端情况，把$$q$$次修改都用掉，如果还没有区间是美丽的，那么就不可能把区间变成美丽的

再想，如果能够在$$k$$次修改使得区间变成美丽的，那么$$k+1, k+2, \cdots$$之后
区间也一定是美丽的，因为一次修改是`0->1`，你只可能引入更多的`1`，贪心地，更多的区间就有机会变美丽

这就可以考虑**二分答案**，假设当前应用了`[1...mid]`这些修改操作，那么
`check(mid)`只需要暴力改前`mid`个位置就可以了，改完之后检查一下满不满足
然后**还原现场**，改过的再改回来
（实际上暴力`[1...n]`，把整个数组都置为`0`更方便一些）

## CodeTON Round 5
**[E. Tenzing and Triangle](https://codeforces.com/problemset/problem/1842/E)**
**问题描述**
给定$$n, k, A$$，平面上有$$n$$个不同的点，每个点用$$(x_i, y_i, w_i)$$表示
同时平面上有一条直线$$x+y = k$$，现在需要删除平面内**所有的点**，有`2`种操作

*  直接删去第$$i$$个点，代价是$$w_i$$

*  任意选择$$a, b$$，其中$$0 \leqslant a, b$$，同时$$a+b < k$$，即点$$(a, b)$$在$$x+y=k$$的下方
   考虑以$$(a, b)$$为顶点，$$x=a, y=b$$和$$x+y = k$$围成**等腰直角三角形**
   其**腰长**为$$l$$，你可以删除三角形区域内（包括边上）所有的点，代价为$$l\cdot A$$
   
下面问删除所有点的**最小代价**

**算法分析**
![](/media/content_img/Tenzing-and-Triangle.jpg)

可以证明的是，如果用到**三角形删点**，那么这些三角形必然**没有公共部分**
假设两个三角形边长为$$a, b$$，并有公共部分$$\text{overlap}$$
可以用一个边长为 $$l = a+b-\text{overlap}(a, b)$$的三角形来代替，结果不劣

如图所示，考虑 $$y \in [k \to 0]$$，对于某一个位置$$y = i$$，一种比较好的情况是，
删除$$y \geqslant i$$ 往上的所有点，不需要单独删点，只需要用一个三角形就可以了

这样可以启发我们，要想删除$$y \geqslant i$$往上的所有点，有三种决策
（1）用三角形来删，（2）暴力删除，（3）用三角形+暴力删点
其中全部用暴力删除的情况，可以看作**用面积为`0`的三角形** + 暴力删点
所以综上所述，有`2`种决策，如图所示
（1）只用一个三角形删点，（2）用三角形，配合暴力来删点

这样就可以考虑**动态规划**了

如图所示，用$$f_i$$表示**已经删除**$$y \geqslant i$$往上**所有**点的**最小**代价，有两种转移

> 第一种转移很简单，$$f_i \leftarrow (k-i) \cdot A$$
   考虑第二种转移
   
第二种转移需要三角形+暴力配合
假设当前尝试删除$$y = i$$，那么这个三角形**往上的顶点**在哪里呢？不知道
只能枚举$$j > i$$的位置，其中$$\geqslant j$$往上的点已经全部删完了
如图所示，用底边$$y = i$$的三角形删一片区域，同时**红色矩形**的离散点暴力删除

```math
\displaystyle
f_i = \min_{i < j \leqslant k } \left\{ f_j + A \cdot (j-1-i) + \sum_{x, y \in \text{ red}} [i \leqslant y \leqslant j-1][0 \leqslant x \leqslant k-j]\right\}
```

将状态转移方程变形
```math
\displaystyle 
f_i = \min_{i < j \leqslant k} \left( f_j + A\cdot j + \sum \right) -A\cdot (i+1)
```

如果`for i = [k -> 0]`，$$\min$$中的部分恰好可以用**线段树来维护**，线段树初始值是$$+ \infty$$

> 怎么维护？考虑从 $$i+1 \to i$$，关键就是$$\sum$$ 部分是**怎么变化的**？

注意到$$i+1 \to i$$，在 $$y = i$$ 这一条线上**新加入了离散的点**
而这些点会影响一些$$j$$，影响$$j \in [i+1, k]$$的**一部分子区间**，具体是哪些呢？

不难预处理出$$(x, wgt) \in \text{V}[i]$$，即 $$y = i$$ 处所有的点，遍历这些点
假设当前考虑点 $$(x_p, i, wgt)$$，那么我们有

$$\begin{cases} i \leqslant j-1 \\\ x_p \leqslant k-j \end{cases}$$，从而有

$$j \in [i+1, k-x_p]$$ 区间，值都应该加上 `wgt`，对应线段树的**区间修改**

> 这样基本就做完了

线段树区间修改之后，查询$$[i+1, k]$$的最小值
（实际上也可以查询整棵树的最小值，因为$$\leqslant i$$位置还没计算出来，这些位置都是$$+\infty$$)
`f(i) = min( tr.all_prod() - A * (i+1) )` 更新`f(i)`

最后`f(i)`计算出来了，`i`这个位置不再是$$+\infty$$了，单点修改
$$i$$位置改成 $$f_i + A\cdot i + \sum$$
但由于$$\sum = [i \leqslant y \leqslant i-1][0 \leqslant x \leqslant k - i] = 0$$ （因为第一项不存在）
所以实际上单点修改令$$i$$改成$$f_i + A\cdot i$$ 即可

动态规划的方向是$$i = k-1 \to 0$$
初始时$$i = k, f[k] = 0$$，另外线段树在$$k$$处也要修改
$$f_k + A\cdot k + \sum$$，其中$$\sum = [i \leqslant y \leqslant k-1][0 \leqslant x \leqslant k - k]$$
而$$i = k$$时，$$[k \leqslant y \leqslant k-1] = 0$$，所以$$\sum = 0$$
由此，初始时刻$$k$$位置单点修改为$$f_k + A\cdot k$$

上一篇：树上问题综合下一篇：codeforces数据结构专题（二）

看完文章有啥想法