hdu6058 Kanade's sum 区间第k大

/**
题目：Kanade's sum
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6058
题意：给定[1,n]的排列，定义f(l,r,k)表示区间[l,r]内的第k（k <= min(n,80)）大的数，如果[l,r]没有k个数，那么为0,。给定一个k，求所有f(l,r,k)的和。
思路：从小到大枚举数x，维护一个>=x的链表，跳k个查询左边>x的k个，右边>x的k个。计算之后，O(1)删除x。
比赛的时候，，刚好反过来了，用的是从大到小用set，二分位置，再迭代器枚举，然后超时了。
eg：
x=1，那么其他数都>x，所以直接x的左边右边各找k个，删除1之后，最小数为2，那么仍然ta的左边和右边各找k个，继续删除，依次操作。

*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<cmath>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int maxn = 5e5+100;
int num[maxn];
int posl[maxn], posr[maxn];
int l[104], r[104];
int li, ri;
int a[maxn];
void read(int &x){
    x = 0;
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >='0' && c <= '9') x = x * 10 + c - 48,c = getchar();
}
int main()
{
    int T,cas = 1;
    cin>>T;
    int n, k;
    while(T--)
    {
        read(n),read(k);
        int x;
        for(int i = 1; i <= n; i++){
            read(x);
            a[i] = x;
            num[x] = i;
        }
        posl[0] = -1, posr[0] = 1;///虚拟节点
        posl[n+1] = n, posr[n+1] = -1;
        for(int i = 1; i <= n; i++){
            posl[i] = i-1;
            posr[i] = i+1;
        }
        LL ans = 0;
        for(int i = 1; i <= n; i++){
            li = ri = 0;
            int cnt = k+1, pos = num[i];
            while(cnt&&pos!=-1){
                l[li++] = pos;
                pos = posl[pos];
                cnt--;
            }
            cnt = k+1;
            pos = num[i];
            while(cnt&&pos!=-1){
                r[ri++] = pos;
                pos = posr[pos];
                cnt--;
            }
            LL cn = 0;
            for(int j = li-1; j >= 0; j--){
                if(ri<k+2-j) break;
                int lans = l[j-1]-l[j];
                int rans = r[k+1-j]-r[k-j];
                LL tmp = (LL)lans*rans;
                if(j==1&&k-j==1&&lans>1&&rans>1){
                    tmp--;
                }
                cn += tmp;
            }
            ans += cn*i;
            posr[posl[num[i]]] = posr[num[i]];
            posl[posr[num[i]]] = posl[num[i]];
        }
        printf("%lld
",ans);
    }
    return 0;
}