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

· · 题解

为什么我的线性做法常数这么大ww

观察特殊性质 E ，这其实等价于区间一定跨过序列中点，明示分治。

我们先来考察如何计算跨过同时跨过 i 和 mid 的区间权值最大值，设这个值是 g_i。

不妨设 i<mid。

首先我们可以计算 f_i 表示 i 是左端点，并且右端点 >mid，长度合法的区间的权值最大值，这个可以用单调队列 O(n) 求出。

容易发现 g_i = \max_{j\leq i} f_j，这是因为我们算出的所有区间都保证了跨过中点，如果一个区间其左端点 \leq i，还跨过了在 i 右边的中点，很显然它就包含了 i。

所以可以分治，轻松做到 O(nq\log n)。

考察怎么把这个 \log 去掉。

我们发现分治这个结构太菜了，很难既分治又没 \log，考虑上述做法更本质的一个结构。

我们知道长度 > \frac{n}{2} 的区间一定会经过序列中点，这个结构能不能扩展？

显然是可以的，考察长度 > \frac{n}{2^k} 的所有区间，在数组上将是 \frac{n}{2^k} 倍数的点标记，那么长度 >\frac{n}{2^k} 任何区间经过至少一个被标记的点，这是显然的。

更进一步的考察长度 \frac{n}{2^k}<l<\frac{n}{2^{k-1}} 的所有区间，其恰好经过一个被标记的点。

因此，如果存在一个 k，满足 \frac{n}{2^k}<l\leq r<\frac{n}{2^{k-1}}，那么长度限制区间是 [l,r] 的答案就能通过统计每个标记点两边的区间的手段做到线性。

我们可以将区间长度做一个倍增分块，每块维护 len\in [2^i,2^{i+1}) 时的信息。

每次查询把 [l,r] 拆成 \log n 个能一次计算的区间，容易发现只有左右端点会各出现一个散块，直接 O(n) 算，中间的整块只要预处理出答案就行，然后需要查整块区间最大值，由于块数是 O(\log n) 的所以是容易的，时间复杂度 O(nq+n\log^2 n)。

我写了，南航机子上大样例跑了 2s，而且卡不动，我希望这只是因为南航机子配置和 CCF 不一样。