模拟赛 序列

题意：

（\(n,m\le10^6\)）

​ 题目所给表达式涉及区间和。将原式转化为前缀和形式：

\[f(l,r)=suma_r-k\times sumb_r-(suma_{l-1}-k\times sumb_{l-1})

\]

​ 我们设 \(V_i=suma_i-k\times sumb_i\)。那么\(f(l,r)=V_r-V_{l-1}\)。那么我们在 \([p,n]\) 取 \(V_{max}\)，在 \([0,p-1]\) 取 \(V_{min}\) 就能得到答案。

​ 注意到 \(V_i\) 的形式与一次函数的形式相同，容易想到斜率优化。我们考虑维护 \([1,p]\) 区间的下凸壳和 \([p,n]\) 区间的上凸壳。由于维护凸壳我们需要保证一段区间的斜率单调。如果直接对每一段区间先排序再 \(O(n)\) 单调栈维护，时间复杂度是 \(O(n^2\log n)\) 的。所以我们可以考虑线段树。由于题目中没有修改操作，所以重点就是在于如何合并两端区间。

​ 由于我们要保证单调性，又因为线段树是递归建树的，我们很容易想到归并排序的方式来保证单调性。然后用一个单调栈扫一下维护上下凸壳。

​ 查询的时候，我们可以二分决策点，找到凸壳中最佳决策点然后选择。

​ 那么空间复杂度是 \(O(n \log n)\) ，而时间复杂度是 \(O(n\log n\log n)\)。这已经可以通过本题了（有数据水的原因）。

​ 这里可以继续优化，考虑优化掉查询时的二分。由于这题不是强制在线，我们可以将询问按 \(k\) 的大小排序，然后查询时用单调队列代替掉二分。那么时间复杂度就做到了 \(O(n\log n)\)。（但是我太懒了没写）

​ 这里值得注意的一点线段树每个节点的栈如果直接存 \(V_i\) 的信息会 MLE。由于 \(V_i\) 一共只有 \(n\) 个，所以我们在线段树每个节点的栈里存编号就好了。

​ （关键的一点是不要把栈的弹出那行的 while 写成 if，不然就会调一个晚上）

代码如下：（没有离线询问，复杂度还是 \(O(n\log \log n)\)）

路漫漫其修远兮，吾将上下而求索。