题解：P15325 【MX-X24-T6】「RiOI-7」Stardust:RAY

· · 题解

咋没人写，流泪。

先拆贡献。设最小的包含 0\sim k 中所有数的区间为 [l_k,r_k]。那么我们有：

\begin{aligned} &\sum_{l\le l'\le r'\le r}\operatorname{mex}_{l'\le i\le r'}p_i\\ =&\sum_{l\le l'\le r'\le r}\sum_k[l'\le l_k\land r_k\le r']\\ =&\sum_k\sum_{l\le l'\le r'\le r}[l'\le l_k\land r_k\le r']\\ =&\sum_{l\le l_k,r_k\le r}(l_k-l+1)(r-r_k+1)\\ =&\sum_{l\le l_k,r_k\le r}(r+1)l_k+(l-1)r_k-l_kr_k-(l-1)(r+1) \end{aligned}

注意到设 i 在排列中的位置为 q_i，实际上有 l_k=\min_{i\le k}q_i，r_k=\max_{i\le k}q_i。因此我们转到排列 q 上考虑，原题操作相当于：

  1. 选择两个数 q_x,q_y，并将二者交换。
  2. 给定 k，求出 \sum_{i\le k}\min_{j\le i}q_j，\sum_{i\le k}\max_{j\le i}q_j 与 \sum_{i\le k}\left(\min_{j\le i}q_j\right)\times\left(\max_{j\le i}q_j\right)。

使用单侧递归线段树即可做到 \mathcal{O}(n\log^2 n)，但是没啥前途。

究其原因是修改和查询太不平衡了。明明修改是简单的单点修改，查询却是这么大一坨。

考虑换维。扫描序列维，维护时间维。具体地，枚举 i=1\sim n，维护每个时间点 t 时 l_i,r_i 的值。那么我们相当于要维护以下操作：

  1. 对于 [L,R] 内的所有 i，l_i\to\min(l_i,x)，r_i\to\max(r_i,x)。
  2. 复制一个新版本。
  3. 查询 i 上 l_i，r_i，l_ir_i 的历史和。

那么就变成了两个我们熟悉的问题：区间 chkmin/max 与单点历史和。我们知道区间 chkmin/max 可以用 Segment Tree Beats 处理成区间对最值加，并且时间复杂度仍然为 \mathcal{O}(n\log n)。那么我们只需要设计出一种标记来维护三个历史和即可。

先来看简单的情况：区间加，单点历史和。对于一个在 t_0 时刻加 k 的修改，其对 T 时刻历史和的影响是 k(T-t_0)=kT-kt_0，是一个关于 T 的一次函数。这启发我们以一次函数的形式描述一个标记。那么查询中前两项 \sum l_i,\sum r_i 就可以简单处理。

对于第三项 \sum l_ir_i，维护三类贡献：所有修改对于 l 为最大值且 r 不为最小值的位置的贡献（下文称为一类标记），对于 l 不为最大值且 r 为最小值的位置的贡献（称为二类标记），以及对于 l 为最大值且 r 为最小值的位置的贡献（称为三类标记）。

在一次修改时，第三类贡献是已经确定的，可以直接下传。但另两类贡献都有一个乘积项不确定。如何解决？

首先，在 Segment Tree Beats 修改的过程中，所有非最值的位置都不会被更改，且下传时最值一变标记就失效了，因此不用考虑一二类标记相互合并的情况。另外，以一类标记为例，其在下传至子区间时，我们会少算 r 成为新的区间最小值的这段贡献。只需将这部分直接“结算”至第三类贡献，就能补上漏的部分。当然也可以理解为“延迟”了这部分贡献，等到新的最值出现时再结算。

事实上你可以发现，一类标记就是 \sum l_i 的贡献，二类标记就是 \sum r_i 的贡献，所以总共只要维护三个标记。

那么我们可以写出来 pushdown：

inline 
void upd(int p, const node &tag) {
    if (t[p].x == tag.x) t[p].t1 += tag.t1;
    if (t[p].y == tag.y) t[p].t2 += tag.t2;
    if (t[p].x == tag.x && t[p].y == tag.y) t[p].t3 += tag.t3;
    else if (t[p].x == tag.x) t[p].t3 += tag.t1 * t[p].y;
    else if (t[p].y == tag.y) t[p].t3 += tag.t2 * t[p].x;
}

其中 x,y 是区间内 l 的最大值与 r 的最小值，t_1,t_2,t_3 则分别是 \sum l_i,\sum r_i,\sum l_ir_i 的标记。

于是我们解决了标记下传的问题。查询时直接下传到叶子处，查询对应的 t_1,t_2,t_3 即可。至此整个问题得以在 \mathcal{O}(n\log n) 的复杂度内解决。

我已经观察到一些素质很低的小朋友，用 AI 把 std 改了改就交上去了。因此代码不予放出。