hdu 6058 Kanade's sum (计算贡献，思维）

题意： 给你一个全排列，要你求这个序列的所有区间的第k大的和

思路：比赛的时候一看就知道肯定是算贡献，也知道是枚举每个数，然后看他在多少个区间是第K大，然后计算他的贡献就可以了，但是没有找到如何在o(k)的时间内找到这k个区间，然后就一直挂机，惨惨惨

感觉官方题解的思路就很棒啊：

我们只要求出对于一个数x左边最近的k个比他大的和右边最近k个比他大的，扫一下就可以知道有几个区间的k大值是x.=

我们考虑从小到大枚举x，每次维护一个链表，链表里只有>=x的数，那么往左往右找只要暴力跳k次，删除也是O(1)的。

时间复杂度：O(nk)

代码：

/** @xigua */

#include <cstdio>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <cstring>

#include <queue>

#include <set>

#include <string>

#include <map>

#include <climits>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 5e5 + 5;

const int mod = 1e9 + 9;

const int mod2 = 1e9 + 7;

const int INF = 1e8 + 5;

const ll inf = 1e15 + 5;

const db eps = 1e-5;

const ll hp = 233333;

int a[maxn], pos[maxn], pre[maxn], nex[maxn];

ll pp[105], np[105];

void solve() {

    int n, k; cin >> n >> k;

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

        scanf("%d", a + i);

        pos[a[i]] = i;

        pre[i] = i - 1;

        nex[i] = i + 1;

    }

    pre[0] = -1, nex[n+1] = n + 2;

    ll ans = 0;

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

        int t1 = 0, t2 = 0;

        int curp = pos[i];

        for (int j = curp; j >= 0 && t1 <= k; j = pre[j]) {

            pp[++t1] = j;

        }

        for (int j = curp; j <= n + 1 && t2 <= k; j = nex[j]) {

            np[++t2] = j;

        }

        for (int j = 1; j <= t1 - 1; j++) {

            if (k - j + 2 > t2) continue;

            ll tmp = (pp[j] - pp[j+1]) * (np[k - j + 2] - np[k - j + 1]);

            ans += tmp * i;

        }

        //删除当前节点 相当于链表

        int tp = pre[curp], tn = nex[curp];

        nex[tp] = tn, pre[tn] = tp;

    }

    cout << ans << endl;

}

int main() {

    int t = 1, cas = 1;

   // freopen("in.txt", "r", stdin);

   // freopen("out.txt", "w", stdout);

   // init();

    scanf("%d", &t);

    while(t--) {

       // printf("Case %d: ", cas++);

        solve();

    }

    return 0;

}