kanade’s sum

题目链接

定义$f(l, r, k)$为$A[l…r]$的$k-th$大。
计算 $sum_{l=1}^{n} sum_{r=l}^{n} f(l, r, k)$ .

不妨计算每个数字的贡献，我们求出每个数字的贡献区间即可。
标程是用链表写的。我觉得其实笛卡尔树也是一个不错的选择，每次删的都是根结点，但是会T，因为如果树的形状是第一个元素次小的样子，去找那$k$个区间的时候是$O(n)$的。我还是把它贴在这里吧。


using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "