题解：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)$，有些卡常。

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

代码洛谷没过就不放了。