题意
给定一个序列 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)$ 暴力。
线段树维护
目标
如上图，我们把数列转化为二维坐标，蓝线为前缀 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 并返回。
代码
#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;
}
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: