专栏文章

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

RRegister_int-std=c++14
P15325题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mlrocnhp
此快照首次捕获于
2026/02/18 14:52
23 小时前
此快照最后确认于
2026/02/18 14:52
23 小时前
查看原文
咋没人写，流泪。
先拆贡献。设最小的包含 0∼k0\sim k 中所有数的区间为 [lk,rk][l_k,r_k]。那么我们有：
∑l≤l′≤r′≤rmex⁡l′≤i≤r′pi=∑l≤l′≤r′≤r∑k[l′≤lk∧rk≤r′]=∑k∑l≤l′≤r′≤r[l′≤lk∧rk≤r′]=∑l≤lk,rk≤r(lk−l+1)(r−rk+1)=∑l≤lk,rk≤r(r+1)lk+(l−1)rk−lkrk−(l−1)(r+1)\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}
注意到设 ii 在排列中的位置为 qiq_i，实际上有 lk=min⁡i≤kqil_k=\min_{i\le k}q_i，rk=max⁡i≤kqir_k=\max_{i\le k}q_i。因此我们转到排列 qq 上考虑，原题操作相当于：
  1. 选择两个数 qx,qyq_x,q_y，并将二者交换。
  2. 给定 kk，求出 ∑i≤kmin⁡j≤iqj\sum_{i\le k}\min_{j\le i}q_j，∑i≤kmax⁡j≤iqj\sum_{i\le k}\max_{j\le i}q_j 与 ∑i≤k(min⁡j≤iqj)×(max⁡j≤iqj)\sum_{i\le k}\left(\min_{j\le i}q_j\right)\times\left(\max_{j\le i}q_j\right)。
使用单侧递归线段树即可做到 O(nlog⁡2n)\mathcal{O}(n\log^2 n)，但是没啥前途。
究其原因是修改和查询太不平衡了。明明修改是简单的单点修改，查询却是这么大一坨。
考虑换维。扫描序列维，维护时间维。具体地，枚举 i=1∼ni=1\sim n，维护每个时间点 tt 时 li,ril_i,r_i 的值。那么我们相当于要维护以下操作：
  1. 对于 [L,R][L,R] 内的所有 ii，li→min⁡(li,x)l_i\to\min(l_i,x)，ri→max⁡(ri,x)r_i\to\max(r_i,x)。
  2. 复制一个新版本。
  3. 查询 ii 上 lil_i，rir_i，liril_ir_i 的历史和。
那么就变成了两个我们熟悉的问题：区间 chkmin/max 与单点历史和。我们知道区间 chkmin/max 可以用 Segment Tree Beats 处理成区间对最值加，并且时间复杂度仍然为 O(nlog⁡n)\mathcal{O}(n\log n)。那么我们只需要设计出一种标记来维护三个历史和即可。
先来看简单的情况：区间加，单点历史和。对于一个在 t0t_0 时刻加 kk 的修改，其对 TT 时刻历史和的影响是 k(T−t0)=kT−kt0k(T-t_0)=kT-kt_0，是一个关于 TT 的一次函数。这启发我们以一次函数的形式描述一个标记。那么查询中前两项 ∑li,∑ri\sum l_i,\sum r_i 就可以简单处理。
对于第三项 ∑liri\sum l_ir_i，维护三类贡献：所有修改对于 ll 为最大值且 rr 不为最小值的位置的贡献（下文称为一类标记），对于 ll 不为最大值且 rr 为最小值的位置的贡献（称为二类标记），以及对于 ll 为最大值且 rr 为最小值的位置的贡献（称为三类标记）。
在一次修改时，第三类贡献是已经确定的，可以直接下传。但另两类贡献都有一个乘积项不确定。如何解决？
首先，在 Segment Tree Beats 修改的过程中，所有非最值的位置都不会被更改，且下传时最值一变标记就失效了，因此不用考虑一二类标记相互合并的情况。另外，以一类标记为例，其在下传至子区间时，我们会少算 rr 成为新的区间最小值的这段贡献。只需将这部分直接“结算”至第三类贡献，就能补上漏的部分。当然也可以理解为“延迟”了这部分贡献，等到新的最值出现时再结算。
事实上你可以发现，一类标记就是 ∑li\sum l_i 的贡献，二类标记就是 ∑ri\sum r_i 的贡献，所以总共只要维护三个标记。
那么我们可以写出来 pushdown：
CPP
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,yx,y 是区间内 ll 的最大值与 rr 的最小值，t1,t2,t3t_1,t_2,t_3 则分别是 ∑li,∑ri,∑liri\sum l_i,\sum r_i,\sum l_ir_i 的标记。
于是我们解决了标记下传的问题。查询时直接下传到叶子处，查询对应的 t1,t2,t3t_1,t_2,t_3 即可。至此整个问题得以在 O(nlog⁡n)\mathcal{O}(n\log n) 的复杂度内解决。
我已经观察到一些素质很低的小朋友，用 AI 把 std 改了改就交上去了。因此代码不予放出。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...