[HNOI2016] 序列题解

思路

把每个连续子段用平面上的点 $(s,t)$ 表示，其中 $s$ 是左端点，$t$ 是右端点。需要回答的就是正方形 $[l,r]\times[l,r]$ 内所有合法点的权值和，点权为对应子段的最小值。

对每个位置 $i$，用单调栈求出左侧第一个严格小于 $a_i$ 的位置，以及右侧第一个小于等于 $a_i$ 的位置。采用这一固定的相等值归属规则后，所有以 $a_i$ 为代表最小值的子段恰好组成一个矩形：左端点在一段连续范围内，右端点也在一段连续范围内。这些矩形互不重叠并覆盖全部合法子段。

做法

将每个常值矩形用二维差分拆成四个角点事件。设 $F(x,y)$ 表示左端点不超过 $x$、右端点不超过 $y$ 的全部点权和，则询问 $[l,r]$ 的答案可化为 $F(r,r)-F(l-1,r)$；另外两项因所有合法子段都满足左端点不超过右端点而相互抵消。

把角点事件和所需前缀查询按第一维排序扫描。一个角点对前缀的贡献是两个一次式的乘积，展开后只需分别维护系数、系数乘第二维、系数乘第一维、系数乘两维乘积。四棵树状数组即可在对数时间内加入事件并求出前缀值。

小规模子任务可以逐询问枚举子段并增量维护最小值。只有一个完整区间询问时，用单调栈在线性时间内累计所有以每个位置为右端点的子段最小值。对于 $n\le 5000$，可以固定左端点，用单调栈依次扩展右端点，二次预处理每个区间的答案。

复杂度

单调栈与事件生成需要 $O(n)$ 时间。排序和树状数组处理需要 $O((n+q)\log n)$ 时间，总空间复杂度为 $O(n+q)$。