USACO 2022 一月月赛铂金组 T1 题解

题意

给定一个序列 A，每次操作可以交换值相差不超过 K 的相邻元素。允许操作任意多次，求字典序最小的最终序列。

暴力

进行一个贪心，我们从 1 到 n，最小化最终序列的每一位。对于第 i 项，找到满足：

$$j\in[i,n]且\forall k\in[i,j),|A_j-A_k|\le K$$

的最小元素 $A_k$，一路交换到 $A_i$ 的位置去。

可以证明，使用任何其他搞法都不能得到字典序更小的答案。

证明：

不妨称序列中所有与 $A_i$ 相差超过 K 的元素为“障碍”。显然，障碍不能与 $A_i$ 交换。因此，在任意时刻，在数列中位于 $A_i$ 前/后的障碍数量不变。

假设我们运用骚操作搞出一个字典序更小的答案 $A^\prime$，则存在 i 满足 $A_i>A^\prime_i且A_{[1,i)}=A^\prime_{[1,i)}$。

考虑将上述贪心进行了 i-1 步，不妨设 $A^\prime_i$ 对应 $A_j$。显然，有： $A^\prime_{[1,i)} 中的障碍数=A_{[1,j)}中的障碍数$ 又因为 $A_{[1,i)}=A^\prime_{[1,i)}$,有： $A^\prime_{[1,i)} 中的障碍数=A_{[1,i)}中的障碍数$ 两式相减，得 $0=A_{[i,j)}中的障碍数$

因此，在贪心过程中，$A_j$ 本来是是可以移过去的，并且还比最终的 $A_i$ 更小，矛盾。

得证。

但是这个前文所说的条件是不好直接用的，我们将其转化一下：

$$\forall k\in[i,j),|A_j-A_k|\le K\iff \max_{k\in[i,j]}(A_k)-A_j\le K 且 A_j-\min_{k\in[i,j]}(A_k)\le K$$

转化为和前缀 max，min 相差不超过 k，就可以每次贪心扫一遍，打出简单的 $O(n^2)$ 暴力。

线段树维护

目标

图 1

如上图，我们把数列转化为二维坐标，蓝线为前缀 max 对应的图像，红线为前缀 min 对应的图像，则我们维护的答案就是图中绿色区域中最靠下的点。

考虑我们需要支持什么操作，我们在贪心时需要把一个元素从某个位置移到 A 的前面，但在实际维护的时候不用这么麻烦，只需要直接删掉元素即可。

总结一下，我们需要一个数据结构：

支持删元素
动态维护与前缀 max，min 相差不超过 K 的最小元素

实现

定义 $mx_i,mn_i$ 为前缀 max，min。

开三个线段树，分别维护：

当前未被删除的 $A_i$ 的值，用来算前缀 max，min
$mx_i-A_i-K$
$A_i-mn_i-K$

然后在每次删数时，在单调栈上找到删的数的前驱，把新进入单调栈的数搞出来。同时，单调栈的变化会导致第二三个线段树上要进行若干个区间减。再做区间减的时候，用势能线段树的写法，首先看当前区间减完之后最小值是否小于0，如果是，递归到叶子，如果叶子对应的元素当前已经同时满足前文所说的两个条件，就把他放到 priority_queue 里头；如果否，就打一个 tag 并返回。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
#define fi first
#define se second
constexpr ll INF = 2e9, MXN = 4e5 + 5;
ll n, m;
priority_queue<pi> q;
ll arr[MXN], cnt[MXN];
void upd(ll x) {
    if (x == 0 || x == n + 1) return;
    if (++cnt[x] == 2) q.push({-arr[x], -x});
}
struct seg {
    struct node {
        pi mn;
        ll tag;
    } t[MXN];
#define ls p << 1
#define rs p << 1 | 1
    bool type;
    seg(bool _type) : type(_type) {}
    void addt(ll p, ll k) { t[p].mn.fi += k, t[p].tag += k; }
    void pushd(ll p) {
        addt(ls, t[p].tag);
        addt(rs, t[p].tag);
        t[p].tag = 0;
    }
    void pushu(ll p) { t[p].mn = min(t[ls].mn, t[rs].mn); }
    void build(ll p, ll l, ll r, ll *arr) {
        if (l == r) {
            t[p].mn.se = l;
            if (arr) t[p].mn.fi = arr[l];
            return;
        }
        ll mid = (l + r) >> 1;
        build(ls, l, mid, arr);
        build(rs, mid + 1, r, arr);
        pushu(p);
    }
    void mod(ll p, ll l, ll r, ll ml, ll mr, ll mv) {
        if (ml > r || mr < l) return;
        if (ml <= l && r <= mr && (type || t[p].mn.fi + mv > 0)) {
            addt(p, mv);
            return;
        }
        if (l == r) {
            t[p].mn.fi = INF;
            upd(l);
            return;
        }
        ll mid = (l + r) >> 1;
        pushd(p);
        mod(ls, l, mid, ml, mr, mv);
        mod(rs, mid + 1, r, ml, mr, mv);
        pushu(p);
    }
    pi fl(ll p, ll l, ll r, ll qv) {
        if (l == r) return t[p].mn;
        ll mid = (l + r) >> 1;
        pushd(p);
        if (t[ls].mn.fi <= qv) return fl(ls, l, mid, qv);
        return fl(rs, mid + 1, r, qv);
    }
    pi que(ll p, ll l, ll r, ll ql, ll qr) {
        if (ql > r || qr < l) return {INF, INF};
        if (ql <= l && r <= qr) return t[p].mn;
        ll mid = (l + r) >> 1;
        pushd(p);
        return min(que(ls, l, mid, ql, qr), que(rs, mid + 1, r, ql, qr));
    }
} a_mn(0), mx_a(0), mnp(1), mxp(1);
#define op(func, args...) func(1, 0, n + 1, args)

bool imn[MXN], imx[MXN];
ll _mnp[MXN], _mxp[MXN], _a_mn[MXN], _mx_a[MXN];
void init() {
    ll mx = -2 * INF, mn = 2 * INF;
    imn[0] = imn[n + 1] = imx[0] = imx[n + 1] = 1;
    mnp.op(build, NULL);
    mxp.op(build, NULL);
    for (ll i = 0; i <= n + 1; i++) {
        if (i == n + 1) mx = INF, mn = -INF;
        if (!i) arr[i] = INF;
        if (arr[i] < mn) mn = arr[i], imn[i] = 1;
        _mnp[i] = arr[i];

        if (!i) arr[i] = -INF;
        if (arr[i] > mx) mx = arr[i], imx[i] = 1;
        _mxp[i] = -arr[i];
        _a_mn[i] = arr[i] - mn - m;
        _mx_a[i] = mx - arr[i] - m;
        if (_a_mn[i] <= 0) _a_mn[i] = INF, upd(i);
        if (_mx_a[i] <= 0) _mx_a[i] = INF, upd(i);
    }
    mnp.op(build, _mnp);
    mxp.op(build, _mxp);
    a_mn.op(build, _a_mn);
    mx_a.op(build, _mx_a);
}
void del(ll x) {
    mnp.op(mod, x, x, INF);
    mxp.op(mod, x, x, INF);
    if (imn[x]) {
        imn[x] = 0;

        auto cur_ele = mnp.op(que, 0, x);
        while (1) {
            auto nx_ele = mnp.op(fl, cur_ele.fi - 1);
            bool f = imn[nx_ele.se];
            a_mn.op(mod, max(x, cur_ele.se), nx_ele.se - 1, -cur_ele.fi + arr[x]);
            if (f) break;
            imn[nx_ele.se] = 1;
            cur_ele = nx_ele;
        }
    }
    if (imx[x]) {
        imx[x] = 0;

        auto cur_ele = mxp.op(que, 0, x);
        while (1) {
            auto nx_ele = mxp.op(fl, cur_ele.fi - 1);
            bool f = imx[nx_ele.se];
            mx_a.op(mod, max(x, cur_ele.se), nx_ele.se - 1, -cur_ele.fi - arr[x]);
            if (f) break;
            imx[nx_ele.se] = 1;
            cur_ele = nx_ele;
        }
    }
}
int main() {
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n; i++) scanf("%lld", arr + i);
    init();
    for (ll i = 1; i <= n; i++) {
        auto best = q.top();
        q.pop();
        printf("%lld\n", -best.fi);
        del(-best.se);
    }
    return 0;
}