Histogram Sequence

lzyqwq · 2025-11-28 16:36:45 · 题解

钦定一个区间中最左边的最小值起贡献。容易单调栈求出每个位置 i 起贡献的区间 [l_i,r_i]。

先考虑简化版问题，即 L=1。考虑一个归并排序的过程，即先对于一个 i，把它起贡献的区间的权值从小到大排序，再把 n 个数组归并。由于 a_i 固定所以只需要对长度排序。我们对这些长度去重并记录出现次数 \operatorname{cnt}。然后把所有 i 当前的最小长度放进一个堆维护。每次取出堆顶并输出 \operatorname{cnt} 次当前权值，然后将当前决策弹出堆并加入当前决策的后继决策。

当 L>1 的时候，考虑先二分找到排名为 L 的权值 v，二分时的 check(v) 函数应当能够返回 \le v 的权值个数，那么我们就知道 v 需要输出几次。若次数超过 R-L+1 就直接输出并结束程序。否则对于每个 i，取出权值大于 v 的部分进行上面那个归并即可。

现在我们需要知道如何计算一个 i 有多少个长度 \le \operatorname{len} 的贡献区间。先考虑长度 =\operatorname{len} 的。若不考虑 l_i,r_i 的限制，那么可取的左端点为 [i-\operatorname{len}+1,i]。那么加上限制之后左端点的取值区间应当为 [\max\{i-\operatorname{len}+1,l_i\},\min\{i,r_i-\operatorname{len}+1\}]。个数容易计算。接下来还要对这玩意求个前缀和，分类讨论把 \min 和 \max 拆开分段计算即可。

认为 N,R 同阶，时间复杂度 \mathcal{O}(N\log N)，空间复杂度 \mathcal{O}(N)。