HDU-6058 Kanade's sum(计数)

传送门：HDU-6058

题意：一个1~n的全排列，定义f(i,j,k)为在区间[i,j]内第k大的数，求

∑nl=1∑nr=lf(l,r,k)

题解：对于每个数求自己对答案的贡献，首先要知道Ai在某个数有贡献当且仅当区间内只有k-1个数比Ai大，于是可以从大到小遍历，这样当枚举到A时，比Ai大的数的位置都已知道，这个可以用set进行保存，然后分别枚举Ai左右两边比Ai大的数的个数以及区间范围。

这个题很卡时间，因此不能用set进行遍历，可以再建立一个领接表来进行O1的遍历

时间复杂度:O(nlogn+nk)

#include<bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

namespace IO {
const int MX = 3e7;
char buf[MX]; int c, sz;
void begin() {
    c = 0;
    sz = fread(buf, 1, MX, stdin);
}
inline bool read(int &t) {
    while (c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
    if (c >= sz) return false;
    bool flag = 0;
    if (buf[c] == '-') flag = 1, c++;
    for (t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
    if (flag) t = -t;
    return true;
}
}
const int inf = 0x3f3f3f3f;
const int MX = 5e5 + 5;
const LL mod = 1e9 + 7;
int a[MX], fa[MX];
set<int>s;
set<int>::iterator now;
struct node {
    int pre, nxt;
} E[MX];

int main() {
    int  n, k, T;
    //freopen("in.txt", "r", stdin);
    IO::begin();
    IO::read(T);
    while (T--) {
        IO::read(n);
        IO::read(k);
        for (int i = 1; i <= n; i++) {
            IO::read(a[i]);
            fa[a[i]] = i;
        }
        LL ans = 0;
        memset(E, -1, sizeof(E));
        E[0].nxt = n + 1;
        E[n + 1].pre = 0;
        s.clear();
        s.insert(0);
        s.insert(n + 1);
        for (int i = n; i >= 1; i--) {
            now = s.upper_bound(fa[i]);
            //printf("%d %d\n",fa[i],*now);
            int r = *now;
            int l = E[*now].pre;
            s.insert(fa[i]);
            E[l].nxt = fa[i];
            E[r].pre = fa[i];
            E[fa[i]].nxt = r;
            E[fa[i]].pre = l;
            if (i + k - 1 <= n) {
                int lc = 0, rc = 1;
                l = r = fa[i];
                int ll = E[l].pre;
                int rr = E[r].nxt;
                for (; rc < k && rr != n + 1; rc++, r = E[r].nxt, rr = E[rr].nxt);
                LL tmp = 0;
                while (rc > 0) {
                    for (; lc + rc < k && ll != 0; lc++, l = E[l].pre, ll = E[ll].pre);
                    if (lc + rc < k) break;
                    tmp += (LL)(l - ll) * (rr - r) * i;
                    rc--;
                    r = E[r].pre;
                    rr = E[rr].pre;
                }
                ans += tmp;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}