526互联

AtCoder Regular Contest 130 E Increasing Minimum

发布时间 2023-05-21 12:19:28作者: zltzlt

这题太神仙了吧！感觉还不是很懂，但是尽力理一下思路。

设 \(t_x\) 为最大的 \(j\) 使得 \(i_j = x\)，不存在则 \(t_x = 0\)。

设 \(1 \sim n\) 的数按照 \(t\) 从小到大排序后是 \(p_1, p_2, ..., p_n\)，设 \(q_i\) 为 \(i\) 在 \(p\) 中的排名，即 \(q_{p_i} = i\)。

发现正着不好考虑，不妨最小化操作之后的序列字典序，这与原问题等价（操作对每个数加的值是定值）。

下面的讨论设 \(a_i\) 为 \(p_i\) 位置上的数。

在第一次操作前，容易发现使 \(\min\limits_{i=1}^n a_i = 1\) 最优。因为若 \(\min\limits_{i=1}^n a_i > 1\)，可以把所有数减去 \((\min\limits_{i=1}^n a_i) - 1\)。

但是这样的限制太宽了。根据题目操作的性质，观察有没有更紧的限制。

大概感受一下，如果所有操作都结束了，显然我们希望 \(a_i\) 越紧凑越好，即理想状态是 \(\max\limits_{i=1}^n a_i - \min\limits_{i=1}^n a_i \le 1\)。事实上如果存在解，那么一定存在一组解满足这个条件，且这个解就是最优解。思考这是为什么。

考察所有操作都结束后，\(a_{i-1}\) 和 \(a_i\) 的大小关系（不妨先假设 \(p_{i-1}\) 被操作过）。

  • 当 \(a_i\) 最后一次操作之前，\(a_i\) 是序列的最小值。那我们得到 \(a_i - 1 \le a_{i-1}\)。

  • 在 \(a_{i-1}\) 最后一次操作前，\(a_{i-1}\) 是序列的最小值，并且 \(a_{i-1}\) 最后一次操作后，能使得 \(a_i\) 还能被操作。那我们得到 \(a_{i-1} \le a_i\)。

那我们得到 \(a_i - 1 \le a_{i-1} \le a_i\)。这是一条很强的限制。

事实上对于任意 \(i < j\)，\(a_j - 1 \le a_i \le a_j\)。并且对于没有被操作过的数，它们的 \(a_i \ge a_n - 1\)（显然取 \(a_i = a_n - 1\) 最优）。综上，我们得到 \(a_n - 1 \le a_1 \le a_2 \le \cdots \le a_n\)。

观察这个不等式，显然最终结果中只有一个符号是 \(<\)，其他都是 \(=\)。枚举 \(<\) 号的位置，取字典序最小值，就能做平方了。但是还不够。

不妨先假设 \(a_1 = a_2 = \cdots = a_n = 0\)，然后逆序操作，要求第 \(k\) 次操作后，\(a_{i_k}\) 为序列最小值。

考虑进行了第 \(k\) 次操作 \(u = i_k\)，这时候序列的最小值是 \(a_v\)（如果有多个就取 \(q_v\) 最小的）：

  • 如果 \(u = v\)，那么操作合法，直接进行下一个操作；
  • 如果 \(u \ne v \land a_u = a_v\)，那么 \(q_u > q_v\)。我们希望最后 \(u \sim v\) 之间都是 \(=\) 号，否则 \(a_u\) 就不能成为最小值了；
  • 如果 \(a_u = a_v + 1\)：
    • 如果 \(q_u < q_v\)，那么 \(u\) 还有救，只要保证 \(u \sim v\) 之间存在一个 \(<\) 号；
    • 否则没救了，无解。
  • 如果 \(a_u \ge a_v + 2\)，那也没救了，无解。

那么最后我们得到了若干个位置必须放 \(=\) 号，若干的位置可以放 \(<\)。

要使字典序越小得先让最小值最大（现在的最小值只能是负数，这样后面加的就越少）。在最小值最大的前提，我们还希望小于号尽量靠后（要使字典序最小）。

设 \(x\) 为逆序操作后，\(a\) 序列中的最小值的位置（如果有多个最小值就取 \(q_x\) 最小的）。那么最后小于号在 \(q_x\) 之前，最小值最大，如果 \(q_x\) 前面都不能放小于号了，那只能在它后面放；如果没有位置可以放小于号，就是无解。

那么最后能确定字典序最小的情况下 \(a_i\) 的相对大小关系，加上一个最小的数使得 \(a_i\) 都为正数，就是最后的解。

时间复杂度线性对数。瓶颈在逆序操作时的查询最小值。

code 
// Problem: E - Increasing Minimum
// Contest: AtCoder - AtCoder Regular Contest 130
// URL: https://atcoder.jp/contests/arc130/tasks/arc130_e
// 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 mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 300100;

int n, m, a[maxn], b[maxn], p[maxn], q[maxn];
int c[maxn], d[maxn], ans[maxn];

struct node {
	int x, y, id;
	node(int a = 0, int b = 0, int c = 0) : x(a), y(b), id(c) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &a[i]);
		b[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
	}
	sort(p + 1, p + n + 1, [&](int x, int y) {
		return b[x] < b[y];
	});
	for (int i = 1; i <= n; ++i) {
		q[p[i]] = i;
	}
	set<node> st;
	for (int i = 1; i <= n; ++i) {
		st.emplace(0, q[i], i);
	}
	for (int i = m; i; --i) {
		int x = a[i];
		st.erase(node(c[x], q[x], x));
		--c[x];
		st.emplace(c[x], q[x], x);
		node p = *st.begin();
		int y = p.id;
		if (x == y) {
			continue;
		}
		if (c[x] == c[y]) {
			++d[q[y]];
			--d[q[x]];
		} else if (c[x] == c[y] + 1) {
			if (q[x] < q[y]) {
				++d[1];
				--d[q[x]];
				++d[q[y]];
			} else {
				puts("-1");
				return;
			}
		} else {
			puts("-1");
			return;
		}
	}
	for (int i = 1; i <= n; ++i) {
		d[i] += d[i - 1];
	}
	int pos = -1, mx = -1, rk = -1;
	for (int i = 1; i <= n; ++i) {
		if (-c[i] > mx) {
			mx = -c[i];
			rk = q[i];
		} else if (-c[i] == mx) {
			rk = min(rk, q[i]);
		}
	}
	for (int i = rk - 1; i; --i) {
		if (!d[i] && pos == -1) {
			pos = i;
		}
	}
	for (int i = n; i >= rk; --i) {
		if (!d[i] && pos == -1) {
			pos = i;
		}
	}
	if (pos == -1) {
		puts("-1");
		return;
	}
	// printf("pos: %d\n", pos);
	// for (int i = 1; i <= n; ++i) {
		// printf("%d ", c[p[i]]);
	// }
	// putchar('\n');
	for (int i = 1; i <= pos; ++i) {
		ans[p[i]] = -1;
	}
	for (int i = 1; i <= n; ++i) {
		ans[i] += c[i];
	}
	// for (int i = 1; i <= n; ++i) {
		// printf("%d ", ans[i]);
	// }
	// putchar('\n');
	int k = *min_element(ans + 1, ans + n + 1);
	for (int i = 1; i <= n; ++i) {
		ans[i] -= k - 1;
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d ", ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}