原题大意

1~n的数组成了序列A，f(l,r,k)为[l, r]里第k大的数，如果r-l+1 < k,那么f(l,r,k)就为0.
现在求

t = 0
for l in 1 : n
    for r in 1 : n
        t+=f(l,r,k)

即求t，注意k < min(n, 80)

算法分析

考虑每个数被几个有效区间包含，每个数向左右各找最多k个比它大的数，然后按左边i个，右边k-i-1个这样讨论。这里可以用链表优化，先维护一个1~n的链表，记录每个数的位置，我们贪心的从1开始选，一直选到n，计算完之后就把它删除，这样就能保证每次选的数都是最小的。

程序代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
typedef long long ll;
int pos[maxn], v[maxn], n, k, T;
int pre[maxn], nxt[maxn];
ll a[maxn], b[maxn];
ll solve(int x){
    int c1 = 0, c2 = 0;
    for(int i = x; i && c1 <= k; i = pre[i])
        a[++c1] = i - pre[i];
    for(int i = x; i <= n && c2 <= k; i = nxt[i])
        b[++c2] = nxt[i] - i;
    ll ans = 0;
    for(int i = 1; i <= c1; i++)
        if(k-i+1 >= 1 && k-i+1 <= c2)
            ans += a[i] * b[k-i+1];
    return ans;
}
void Delete(int x){
    pre[nxt[x]] = pre[x];
    nxt[pre[x]] = nxt[x];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--){
        cin >> n >> k;
        for(int i = 1; i <= n; i++){
            cin >> v[i];
            pos[v[i]] = i;
        }
        for(int i = 0; i <= n+1; i++) pre[i] = i-1, nxt[i] = i+1;
//        pre[0] = 0, nxt[n+1] = n+1;
        ll ans = 0;
        for(int i = 1; i <= n; i++){
            ans+=solve(pos[i]) * i;
            Delete(pos[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}