「解题报告」AGC001F Wide Swap

首先题目给的限制条件很奇怪，下标差 \(K\) 而值域差 \(1\)。我们变成逆排列，然后就转换成了下标差 \(1\)，值域差 \(K\) 了，每次操作就相当于交换相邻的两个差 \(\ge K\) 的数。

假设新的逆排列为 \(Q_i\)。我们发现，假如存在两个数差 \(<K\)，那么它们的相对位置关系一定不变。那么我们现在有若干个限制 \((i, j)\)，满足 \(Q_i\) 一定在 \(Q_j\) 前。那么我们可以将这个限制建出一个图，然后跑拓扑排序，便得到了一个可能的 \(Q_i\) 序列。

我们要求 \(P_i\) 字典序最小，这意味着 \(Q_i\) 中较小的数要尽可能靠前。那么最后一个数肯定尽可能大，让较小的数靠前。那么我们实际上就是要求 \(Q_i\) 翻转过来的字典序最大。那么我们只需要建反图，然后跑拓扑排序，每次选编号最大的点即可。

但是边数很多，直接跑显然不可行。我们可以拿线段树维护每个点的度数，然后维护一个最小值，每次删去一个数 \(i\)，入度会减少 \(1\) 的点的区间为 \((i - K, i + K)\)，然后找入度为 \(0\) 的点即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int n, k, p[MAXN], q[MAXN];
struct SegmentTree {
    struct Node {
        pair<int, int> mn;
        int tag;
    } t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
    void pushDown(int i) {
        if (t[i].tag) {
            t[lc].mn.first += t[i].tag, t[lc].tag += t[i].tag;
            t[rc].mn.first += t[i].tag, t[rc].tag += t[i].tag;
            t[i].tag = 0;
        }
    }
    void build(int i = 1, int l = 1, int r = n) {
        t[i].mn = { 0, l };
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(lc, l, mid), build(rc, mid + 1, r);
    }
    void update(int d, int v, int i = 1, int l = 1, int r = n) {
        if (l == r) {
            t[i].mn.first = v;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(i);
        if (d <= mid) update(d, v, lc, l, mid);
        else update(d, v, rc, mid + 1, r);
        t[i].mn = min(t[lc].mn, t[rc].mn);
    }
    void add(int a, int b, int v, int i = 1, int l = 1, int r = n) {
        if (a <= l && r <= b) {
            t[i].mn.first += v, t[i].tag += v;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(i);
        if (a <= mid) add(a, b, v, lc, l, mid);
        if (b > mid) add(a, b, v, rc, mid + 1, r);
        t[i].mn = min(t[lc].mn, t[rc].mn);
    }
} st;
struct BinaryIndexTree {
    int a[MAXN];
#define lowbit(x) (x & (-x))
    void add(int d, int v) {
        while (d <= n) {
            a[d] += v;
            d += lowbit(d);
        }
    }
    int query(int d) {
        if (!d) return 0;
        int ans = 0;
        while (d) {
            ans += a[d];
            d -= lowbit(d);
        }
        return ans;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} bit;
int ans[MAXN], m;
int ans2[MAXN];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        q[p[i]] = i;
    }
    st.build();
    priority_queue<int> que;
    for (int i = n; i >= 1; i--) {
        int ind = bit.query(max(q[i] - k + 1, 1), min(q[i] + k - 1, n));
        if (!ind) {
            que.push(q[i]);
            st.update(q[i], INT_MAX);
        } else {
            st.update(q[i], ind);
        }
        bit.add(q[i], 1);
    }
    while (!que.empty()) {
        int u = que.top(); que.pop();
        ans[++m] = u;
        st.add(max(1, u - k + 1), min(u + k - 1, n), -1);
        while (st.t[1].mn.first == 0) {
            int v = st.t[1].mn.second;
            que.push(v);
            st.update(v, INT_MAX);
        }
    }
    for (int i = 1; i <= n; i++) {
        ans2[ans[n - i + 1]] = i;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans2[i]);
    }
    return 0;
}