题解：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 不一样。