题解：P14638 [NOIP2025] 序列询问 / query（民间数据）

winter2020 · 2025-12-01 17:01:17 · 题解

本文提供一个易想易理解的单调队列做法（似乎没有重复做法（？）。

笔者在考场上用时 5 分钟推出 O(nq\log n)，后大战 T2 无果。于周一思考 O(nq) 简直唐到没边。故作此题解。

笔者现已退役，水平极低。

做 n 次区间 chkmax，在区间没有任何性质时容易做到 O(n\log n)，只有包含或相离关系时写单调栈，只有相交和相离关系时写单调队列，均可做到 O(n)。

我们直接枚举区间左端点，再暴力枚举区间右端点，此时存在 O(n^2) 个区间，暴力对这些区间做 chkmax 即可。

我们首先注意到我们只需要维护一个合法右端点的单调队列，只有这些会造成贡献，但此时复杂度没有降低。但我们仔细考虑其具体操作如下（对下图的红蓝色区间做 chkmax）：

这样的区间个数为 O(n)，且按区间左端点排序后（实际不用），右端点单调不降，此时直接做单调队列即可。

对于一个左端点，是对所有红色区间做 chkmax。但我们注意到在左端点移动时，有非常多个区间 chkmax 只是左端点改变，右端点未改变，chkmax 的区间也未改变。

于是这给我们一个优化：对于一个红色区间，我们只考虑其能造成最优答案的左端点。即当“红色区间存在于单调栈中”，合法的左端点是一个区间，找出这个左端点的前缀和最小值即可。

可以存储所有红色区间及其合法左端点区间，此时 rmq 出最优左端点即可。红色区间只有 O(n) 个，于是再次做 chkmax，可使用排序+并查集（考场大样例跑 7s）。

（这里缺一段考场代码）

下文为场下口胡。

我们定义 x 的“单调栈点”为最大的 y 满足 y<x \land s_y>s_x。（纯粹为方便叙述）

显然只需考虑优化掉上面的红色区间复杂度，我们再次注意到由于红色区间是“找上一个比自己大”的点来的，所以只会在区间端点处出现相交，即不会出现 a<c<b<d，且 a,c 分别为 b,d 的单调栈点。

此时我们把所有红色区间的左右端点往里面缩一位，即 [l,r] 变为 [l+1,r-1]，暴力贡献 a_l,a_r，此时所有区间只有包含关系，单调栈即可。