ACM模版

描述

题解

我的意中人是个盖世英雄，有一天他会踩着七色的云彩来娶我，我猜中了开头，可是我猜不着这结局……

这个题我也是猜中了开头，却没有猜中结尾……

首先，很明显的一个条件是，人家要求所有子区间的第 k 大的值的和，那么，很明显我们不能求所有子区间，我们必须求每个值的贡献才行。这个故事的开头总是如此，很容易猜到……

然后我就各种想，怎么才能优化这个贡献的查询呢？单调栈肯定不行，暴力，更不行……想来想去，始终无法使程序更优，也就 TLE 到了最后。

后来，发现这个题想要优化到 O(nk) 并非难事，因为我们想要求一个值的贡献，只需要求出一个值左边比他大的 k−1 个数，右边也求出比他大的 k−1 个数，就这样，我们就能求出来他的贡献，这部分比赛时就很清楚，但是没有想到一个很重要的优化，那就是从小到大进行枚举，维护一个链表，链表中的每个数都是比这个枚举的数要大的，所以我们只需要 O(k) 复杂度就能求出来这个数的左右范围，最后复杂度自然就是 O(nk) ，哎，感觉我自己好愚蠢，这么常见的优化我竟然没有想到……

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int n, k;
int s0, t0;
ll ans = 0;
int a[MAXN], pos[MAXN];
int pre[MAXN], ntp[MAXN];
int s[MAXN], t[MAXN];

void erase(int x)
{
    int pp = pre[x];
    int nn = ntp[x];
    if (pre[x])
    {
        ntp[pre[x]] = nn;
    }
    if (ntp[x] <= n)
    {
        pre[ntp[x]] = pp;
    }
    pre[x] = ntp[x] = 0;
}

void solve()
{
    for (int i = 1; i <= n; i++)
    {
        pre[i] = i - 1;
        ntp[i] = i + 1;
    }
    ans = 0;
    for (int num = 1; num <= n - k + 1; num++)
    {
        int p = pos[num];
        s0 = t0 = 0;
        for (int d = p; d && s0 <= k + 1; d = pre[d])
        {
            s[++s0] = d;
        }
        for (int d = p; d != n + 1 && t0 <= k + 1; d = ntp[d])
        {
            t[++t0] = d;
        }
        s[++s0] = 0;
        t[++t0] = n + 1;
        for (int i = 1; i < s0; i++)
        {
            if (k + 1 - i <= t0 - 1 && k + 1 - i >= 1)
            {
                ans += (t[k + 1 - i + 1] - t[k + 1 - i]) * 1ll * (s[i] - s[i + 1]) * num;
            }
        }

        erase(p);
    }
}

int main()
{
    int T;
    scan_d(T);
    while (T--)
    {
        scan_d(n), scan_d(k);
        for (int i = 1; i <= n; i++)
        {
            scan_d(a[i]);
            pos[a[i]] = i;
        }

        solve();

        cout << ans << endl;
    }

    return 0;
}