hdu6058

hdu6058

题意

定义 \(f(l, r, k)\) 函数为区间 \([l, r]\) 第 \(k\) 大的数，如果 \(r - l + 1 < k\)，\(f = 0\) 。求 \(\sum_{l=1}^{n}\sum_{r=l}^{n}f(l, r, k)\) 。

分析

我们直接去算每个数字在多少个区间为第 \(k\) 大的数，那么一定和它前面和后面的 \(k\) 个大于它的数有关（如果有的话），现在问题就是怎么快速找出它前面和后面大于它的 \(k\) 个数。

对于 \([1, n]\) 每个数，用两个数组分别指向它所在的位置前面的值和后面的值的位置，那么从 \(1\) 到 \(n\) 计算，算完之后删掉（更改它后面的值向前的指向，更改它前面的值向后的指向），这样对于每个数向左向右最多跳 \(k\) 次。复杂度 \(O(k * n)\) 。

code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAXN = 5e5 + 10;

int n, k;

int pre[MAXN], nxt[MAXN], pos[MAXN];

int l[MAXN], r[MAXN];

void del(int x) {

    pre[nxt[x]] = pre[x];

    nxt[pre[x]] = nxt[x];

}

ll cal(int x) {

    int c1 = 0, c2 = 0;

    for(int i = x; i > 0; i = pre[i]) {

        l[++c1] = i - pre[i];

        if(c1 == k) break;

    }

    for(int i = x; i <= n; i = nxt[i]) {

        r[++c2] = nxt[i] - i;

        if(c2 == k)  break;

    }

    ll res = 0;

    for(int i = 1; i <= c1; i++) {

        if(k - i + 1 <= c2) {

            res += 1LL * l[i] * r[k - i + 1];

        }

    }

    return res;

}

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        scanf("%d%d", &n, &k);

        for(int i = 1; i <= n; i++) {

            int x;

            scanf("%d", &x);

            pos[x] = 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 += cal(pos[i]) * i;

            del(pos[i]);

        }

        printf("%lld\n", ans);

    }

    return 0;

}