本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-10-01 15:08:43

传送门： F. Almost Sorted

题目大意：

给定长度为 $n$ 的排列 $p_i$ 和常数 $k$，一个长度为 $n$ 的排列 $q_i$ 是合法的当且仅当对于任意 $1 \le i < j \le n$，$p_{q_i} \le p_{q_j}+k$。求合法的排列的逆序对数的最小值。

看到 $k \le 8$，八九不离十就是状压 dp。
考虑从 $1$ 至 $n$ 挨个位置填数，注意到我们若在某个位置上填了 $i$，那么 $[1,i-k)$ 必定在这个位置之前就已经填上了，同理，$(i+k,n]$ 必定还没有填过，现在我们就只需要关心 $[i-k,i) \cup (i,i+k]$ 这 $2k$ 个数的状态，直接设 $f_{i,j,S}$ 表示第 $i$ 位填 $j$，$[j-k,j) \cup (j,j+k]$ 中填上的数的集合为 $S$ 时的最小逆序对数，看起来状态数达到了 $O(n^24^k)$ 级别，但实际上第 $i$ 位上填的数的范围是 $[i-k,i+k]$，所以 $j$ 这一维是 $O(k)$ 的，然后 $S$ 这一维中最大的填过的数和最小的没被填过的数的差不应超过 $k$，搜一下发现只有 $1280=5 \times 2^8$ 种合法的 $S$，所以状态数只有 $O(nk2^k)$ 级别。

然而常数还是太大了，必须考虑继续优化。

注意到 $S$ 这一维中最大的填过的数和最小的没被填过的数的差不超过 $k$，最小的没被填过的数说明小于该数的数全部都填上了，同理最大的填过的数说明大于该数的数全部未填，而现在我们就只需要考虑两数之间的 $O(k)$ 个数了，重新设计 dp 状态 $f_{i,S}$ 表示最小的未被填上的数是 $i$，$(i,i+k]$ 中填上的数的集合为 $S$ 时的最小逆序对数，这时状态数就降到了 $O(n2^k)$ 级别了，转移时选择 $[i,i+k]$ 中一个没被填过的数填上，使用主席树计算其与已经填过的数形成的逆序对数，可在 $O(nk2^k(k+\log n))$ 时间内解决该问题。

代码：

#include <bits\/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 5005;
const int Mod = 998244353;

int n, K, p[MAXN], id[MAXN];
int f[MAXN][1 << 8];\/\/f[i][S] 表示未填的数中最小的是 i，(i,i+k] 填的情况为 S 时的最小逆序对数

inline void chkMin(int &a, int b) { if (a > b) a = b; }

int tot, rt[MAXN];

struct node {
    int ls, rs, sum;
} T[MAXN * 15];

void upd(int &p, int vp, int l, int r, int gk) {
    T[p = ++tot] = T[vp];
    T[p].sum++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (mid >= gk) upd(T[p].ls, T[vp].ls, l, mid, gk);
    else upd(T[p].rs, T[vp].rs, mid + 1, r, gk);
}

int query(int p, int l, int r, int gl, int gr) {
    if (gl > gr) return 0;
    if (l >= gl && r <= gr || !p) return T[p].sum;
    int mid = (l + r) >> 1, ret = 0;
    if (mid >= gl) ret = query(T[p].ls, l, mid, gl, gr);
    if (mid < gr) ret += query(T[p].rs, mid + 1, r, gl, gr);
    return ret;
}

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        id[p[i]] = i;
        upd(rt[i], rt[i - 1], 1, n, p[i]);
    }
    
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;

    for (int i = 1; i <= n; i++)
        for (int S = 0; S < 1 << K; S++) if (f[i][S] < 1e9) {
            int mn = min(K + 1, n + 1 - i);
            for (int j = min(K, n - i); j; j--) if (!(S >> j - 1 & 1)) {
                mn = j;
                int cnt = (id[i] < id[i + j]) + query(rt[id[i + j]], 1, n, i + K + 1, n);
                for (int k = min(K, n - i); k; k--) if (!(S >> k - 1 & 1))
                    cnt += (id[i + k] < id[i + j]);
                chkMin(f[i][S | 1 << j - 1], f[i][S] + cnt);
            }

            int cnt = query(rt[id[i]], 1, n, i + K + 1, n);
            for (int j = min(K, n - i); j; j--) if (!(S >> j - 1 & 1))
                cnt += (id[i + j] < id[i]);
            chkMin(f[i + mn][S >> mn], f[i][S] + cnt);
        }

    printf("%d", f[n + 1][0]);
    return 0;
}