6010

先考虑怎么对一组询问求解答案。容易想到一种贪心策略：如果 $a_{q_i}a_i$ 的情况也类似，只不过要下落速度越慢越好。 考虑处理前一种情况，后一种情况则是镜像的。我们将 $a_j>a_i$ 的部分插入直线凸包，那么从 $i$ 开始经过的世界就是插入 $i$ 这条直线时，$i$ 这条直线右边的部 ......