Histogram Sequence

钦定一个区间中最左边的最小值起贡献。容易单调栈求出每个位置 $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)$。