悲,赛时代码赛后被 hack 了。
发现对子段排序不会使排列的字典序变大。因此若存在长度 \(\ge k\) 的递增子段直接输出原排列。
否则答案与原排列的 \(\text{LCP}\) 至少为 \(n - k\)(可以通过对 \([n - k + 1, n]\) 排序达到)。我们想在不影响前 \(n - k\) 个数的顺序的前提下,最小化后面的数。
找出以 \(n - k\) 为右端点的最长递增子段,设其为 \([o, n - k]\)。则对于 \(l \in [o, n - k]\),若 \(p_{n - k} < \max\limits_{i = n - k + 1}^{l + k - 1} p_i\),就说明对 \([l, l + k - 1]\) 排序不会影响前 \(n - k\) 个数。对于所有这样的 \(l\),若 \(l_1 < l_2\),则对 \([l_1, l_1 + k - 1]\) 排序一定不劣于对 \([l_2, l_2 + k - 1]\) 排序。因为进入子段的数越少,排序结果不会变劣。
于是找出最小的 \(l\),对 \([l, l + k - 1]\) 排序即可。
若预处理以 \(n - k + 1\) 为左端点的区间最大值,使用计数排序等排序算法做到 \(O(n)\) 排序,时间复杂度就是 \(O(n)\)。
code
// Problem: B - Sliding Window Sort 2
// Contest: AtCoder - AtCoder Regular Contest 165
// URL: https://atcoder.jp/contests/arc165/tasks/arc165_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int logn = 20;
int n, m, a[maxn], f[maxn];
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
f[n - m + 1] = a[n - m + 1];
for (int i = n - m + 2; i <= n; ++i) {
f[i] = min(f[i - 1], a[i]);
}
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && a[j + 1] > a[j]) {
++j;
}
if (j - i + 1 >= m) {
for (int k = 1; k <= n; ++k) {
printf("%d ", a[k]);
}
return;
}
}
int p = n - m + 1, k = n - m + 1;
while (p > 1 && a[p - 1] < a[p]) {
--p;
if (a[n - m] < f[p + m - 1]) {
k = p;
}
}
sort(a + k, a + k + m);
for (int i = 1; i <= n; ++i) {
printf("%d ", a[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Sliding Windowatcoder regular contest sliding atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest degree atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest disconnected atcoder regular contest