codeforces round 757 (Div 2) and EDU 118

线段树杂题

问题描述
给定一个 $1 \to n$ 的排列 $\{a_1, a_2, \cdots a_n\}$
当存在 $i < j$ 并且 $[i+1, j-1]$ 中所有数都满足 $\leqslant \min \{a_i, a_j\}$ ，影魔会获得 $p_1$ 的攻击力
特别地， $(i, i+1)$ 这样一对数总会给影魔提供 $p_1$ 的攻击力
另外，令 $c$ 为 $\max\{a_{i+1}, a_{i+2}, \cdots a_{j-1}\}$ ，当 $a_i < c < a_j$ 或者 $a_j < c < a_i$
影魔会获得 $p_2$ 的攻击力

现在给出 $m$ 个问询，对于每个问询，求 $[ql, qr]$ 区间内的灵魂能为影魔提供多少攻击力

算法分析
注意到问题给出的是关于 $a[1\cdots n]$ 的一个排列，也就是说所有元素都不相同
不难想到，对于某个 $i$ ，考虑它会对哪些位置或者区间产生贡献

$[i, i+1]$ 肯定会产生贡献 $p_1$ ，这部分贡献相对独立，对于每个问询 $[ql, qr]$ ，可以单独计算
这部分的贡献就是 $p_1 \cdot (qr-ql)$ ，是相对固定的
可以想到找到左边第一个比 $i$ 大的数 $l(i)$ ，和右边第一个比 $i$ 大的数 $r(i)$
那么 $[l(i)+1, r(i)-1]$ 中的数都 $< \min\{l(i), r(i)\}$ ，影魔在 $l(i)$ 处获得 $p_1$ 攻击力
这可以用线段树执行单点增加， $l(i)$ 增加 $p_1$ 即可维护
至于 $l(i), r(i)$ ，可以用单调栈预处理
另外， $a(l_i+1, l_i+2, \cdots i-1) < a(i) < a(r_i)$ ，此时 $a_i$ 产生的贡献是多少？
每一个 $\forall j \in [l_i+1\cdots i-1]$ 都会有 $p_2$ 的贡献，用线段树区间增加维护
执行 $[l_i + 1, i-1]$ 的区间增加，注意维护增加的值为 $p_2 \cdot len$ ， $len$ 为区间长度
同理， $a(i+1, i+2, \cdots, r_i-1) < a(i) < a(l_i)$ ，执行区间 $[i+1, r_i-1]$ 增加 $p_2$

每一个位置 $i$ 都可以用以上方法维护贡献，如果我们要求得影魔获得的总攻击力
只需要在线段树上查询 $[1, n]$ 即可，比较棘手的是处理问询子区间 $[ql, qr]$

假设现在考虑询问 $id$
对于位置 $i \notin [ql, qr]$ ，按之前的方法维护出 $i$ 在线段树上整体的贡献
再进一步查询得到对 $[ql, qr]$ 的贡献，这部分贡献是要扣除的
想到这里，可以考虑主席树的思想
$[ql, qr]$ 的贡献等于 $qr$ 处添加的贡献减去 $ql-1$ 处添加的贡献，具体来说
对于 $qr$ 版本的线段树，查询 $[ql, qr]$ ，记为 $S(qr)$
对于 $ql-1$ 版本的线段树，查询 $[ql, qr]$ ，记为 $S(ql-1)$ ，那么答案为 $S(qr)-S(ql-1)$

可以对所有问询离线，然后扫描 $i \in [1, n]$
如果某个 $i$ 和某个问询的 $ql-1$ 重合，此时线段树上正好维护了 $[1\cdots ql-1]$ 产生的总贡献
此时问询 $[ql, qr]$ 就对应 $i < ql$ 的点，对 $[ql, qr]$ 的贡献，这部分贡献是要扣除的，记为 $S_2(id)$
如果 $i$ 和问询的 $qr$ 重合，此时线段树包括了从 $[1\to qr]$ 所有的 $i$ 产生的贡献
查询区间 $[ql, qr]$ 得到 $S_1(id)$ ，令 $S_1(id) - S_2(id)$ 就是答案

CF 757

EDU 118

D.MEX Sequences
题目大意
给定序列 $a_1, a_2, \cdots, a_n$ ，问存在多少个 mex-correct 子序列
其中子序列满足 $(a_{i1}, a_{i2}, \cdots a_{im})$ ， $1 \leqslant i1 < i2 < \cdots < im \leqslant n$
只要下标不同就算不同的子序列，如果两个序列取相同的值，但是下标不同，就算不同的序列

mex-correct 子序列 $(x_1, x_2, \cdots x_k)$ 定义如下
对于每一个元素 $i \in [1, k]$ ，前缀 mex 值为 $\textbf{mex}[i] = \bm{mex}(x_1, x_2, \cdots x_i)$
每个元素都必须满足 $|x_i - \text{mex}[i]| \leqslant 1$

算法设计

考虑 $\bm{dp}$ ，对于每一个位置 $i$ ，如果 $a_i = x$ ，不难发现只有以下 $3$ 种情况

$[1\cdots i-1]$ 包含所有 $\{0\cdots x-2\}$ 的元素， $\textbf{mex}(i-1) = x-1$
- 如果选择 $a_i$ ，存在转移
  $[1\cdots i]$ 包含所有 $\{0 \cdots x-2\} \cup \{x\}$ 的元素， $\textbf{mex}(i) = x-1$
- 不选 $a_i$ ，存在转移
  $[1\cdots i]$ 包含所有 $\{0 \cdots x-2\}$ 的元素，并且 $\textbf{mex}(i) = x-1$
$[1\cdots i-1]$ 包含所有 $\{0\cdots x-1\}$ 的元素， $\textbf{mex}(i-1) = x$
- 如果选择 $a_i$ ，存在转移
  $[1\cdots i]$ 包含所有 $\{0 \cdots x\}$ 的元素， $\textbf{mex}(i) = x+1$
- 不选 $a_i$ ，存在转移
  $[1\cdots i]$ 包含所有 $\{0 \cdots x-1\}$ 的元素， $\textbf{mex}(i) = x$
$[1\cdots i-1]$ 包含所有 $\{0\cdots x\}$ 的元素， $\textbf{mex}(i-1) = x+1$
- 如果选择 $a_i$ ，存在转移
  $[1\cdots i]$ 包含所有 $\{0 \cdots x\}$ 的元素， $\textbf{mex}(i) = x+1$
- 不选 $a_i$ ，存在转移
  $[1\cdots i]$ 包含所有 $\{0 \cdots x\}$ 的元素， $\textbf{mex}(i) = x+1$

注意到后两种情况，都是 $dp(i-1, x) \to dp(i, x)$ 或者 $dp(i-1, x) \to dp(i, x+1)$ 的转移
可以考虑递推，具体来说，用 $dp(i, x)$ 表示状态 $\textbf{mex}(i) = x$ 对应的方案数

对于第二种情况， $dp(i-1, x) \to \displaystyle\begin{cases}dp(i, x) \\ dp(i, x+1)\end{cases}$
对于第三种情况， $dp(i-1, x+1) \to dp(i, x+1)$

那么对于位置 $i$ ，合法的方案数为 $dp(i, x) + dp(i, x+1)$ ，这部分累加到答案中
从 $i \to i+1$ 递推的时候，存在转移 $dp(i+1, x+1) \leftarrow dp(i, x) + dp(i, x+1)$
算法实现时候，可以省略第一维，用 $dp(x+1) += (dp(x) + dp(x+1))$

下面单独处理第一种情况
注意到对于第一种情况，首先有 $dp(i, x-1) \leftarrow dp(i-1, x-1)$
还有很重要的一点是，对于 $[i+1\cdots n]$ 能选的数是固定的，只能是 $\{x-2, x\}$ 两种
只要一次预处理，算出 $\text{suf}(i)$ 表示后缀 $[i+1\cdots n]$ 中有几个 $\{x-2, x\}$ 即可
此时的方案数为 $dp(i, x-1) \cdot 2^{\text{suf}(i)}$
$\textbf{power}(2, \text{suf}(i))$ 就是后缀可选元素的子集个数