第 $k$ 大查询（kth）

题目传送门
外网传送门

正文

我们首先可以想到，我们如果枚举区间是很难继续优化的，所以我们可以考虑每一个数对答案的贡献，即求出 $\sum_{i=1}^n a_i \times cnt_i$，其中 $cnt_i$ 表示包含了第 $i$ 个数且比 $a_i$ 大的数有且仅有 $k - 1$ 个数时的区间个数。

那么，问题就变成了：对于每一个 $a_i$，有多少个区间满足包含了 $a_i$ 且比 $a_i$ 大的数有且仅有 $k - 1$ 个数时的区间个数。那么我们可以从小到大枚举 $a_i$，这个时候，比 $a_i$ 大的数一定越来越少，我们可以维护一个链表，维护比当前大的数，那么，当我们按顺序枚举完一个数之后，就删除这一个数，就可以保证维护的是比当前大的数。那关于这个链表，我们就维护出了每个数的 $pre$ 和 $nxt$。

这时，我们可以枚举左右两边选了多少个比它大的（其实可以只枚举一边，因为总共 $k-1$ 个，所以另一边可以算出来），那么，我们可以利用乘法原理，具体见下图：

那么将 $cntl \times cntr$ 的和求出来，就可以计算出上文中的 $cnt_i$，套公式，即可算出答案。

欢迎在评论区提出题解意见。（不许说“膜拜”等无效内容）