一个更加厉害的O(n)支配对：考虑所有询问，取忽略第二个限制的全局最优解 $(a,b)$ 表示 $a$ 这个左边的 和 $b$ 这个右边的之间满足 $y_a < y_b$，使得总和最大。这可以回答 $l< a,b< r$ 或者 $a< l,r< b$ 的所有询问 $(l,r)$。

将所有询问画在平面上，剩下的未被回答的询问，即为两个横纵坐标均不交的矩形。接下来取可行点对，将会继续划分这个图形。

稍加分析可以得出这样划分只有 $< 2n$ 个划分是重要的。

怎么快速找划分？框架：递归。方法：用DS维护 $y$ 这一维，数据结构分裂。

总有一种实现可以做到 $O(n\log n+q)$，大家见谅。