P14638 [NOIP2025] 序列询问 题解

分享一下赛时做法。

首先把区间 $[l,r]$ 映射到直角坐标系上的点 $(l,r)$，注意到求出一个矩形的最大值是不难的，而题目相当于要求这样一个梯形的最大值：

这个梯形似乎没有什么很好的性质。但我们注意到对于一次询问的所有 $i$，两条倾斜直线都是不变的。也就是说，如果基于这两条直线构造平行四边形，就相当于一个 RMQ 问题，可以使用单调队列求解，例如：

如果 $2L\ge R$，使用两个平行四边形即可覆盖梯形内的所有整点。对于一般情况，左下角的三角形可以使用如下方式覆盖：

然后这道题就做完了。可能需要卡常，RMQ 全部使用单调队列维护。