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

· · 题解

先以每个区间左端点为横轴，右端点为纵轴建一个坐标系，更直观。

在这个坐标系中，查询 ([L,R],i) 是这些区间和的最大值：

考虑分成两块：

因为每次查询同时算 n 个位置的答案，所以上面平行四边形的那一块可以从左往右扫，用单调队列维护列，再用ST表算每一列的最大值：记 s_i=\sum_{j=1}^i a_i，s_0=0，则每一列的最大值为 \max_{j=i+L-1}^{i+R-1}s_j-s_{i-1}。

但下面那一块并不好算。

但我们发现，如果 2L\ge R，答案可以用两个平行四边形覆盖：

其中横向的平行四边形可以从上往下扫时类似地计算。

如果 2L< R，可以覆盖两个平行四边形后转化为 [2L+1,R] 的情况：

递归计算，时间复杂度 O(nq\log\frac R L+n\log n)，期望得分 60~65pts。（赛时止步于此）

实际上，若 2L<R，我们可以将 [L,R] 拆成 [L,2^l-1],[2^l,2^{l+1}-1],\ldots ,[2^r,R] 这些左端点的两倍不小于右端点的区间，中间可以预处理后用ST表记录，左右直接计算，时间复杂度 O(nq+n\log n \log \log n)，有些卡常。

另一种做法（其它题解）是按一开始的想法这样覆盖下面一块：

代码洛谷没过就不放了。