[ARC114F] Permutation Division

题面

给定一个 $1\sim n$ 的排列。 Alice 要把它分成 $k$ 段，Bob 要把这 $k$ 段重排使得字典序最大。 问 Alice 的所有划分方式中最终得到的字典序最小的排列是什么。

$k\le n\le 2\times10^5$ 。

题解

让原排列和新排列 LCS 尽量长。二分之，在 $[1,x]$ 内，开头递减； $[x+1,n]$ 比 $a_1$ 小。平衡树或直接 set 维护。

代码

const int N = 2e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int a[N], id[N], sum[N];
	bool vis[N];
	int main () {
		n = Read (), m = Read();
		for (int i = 1; i <= n; i++) id[a[i] = Read()] = i;

		auto check = [&] (int x) -> int {
			set<int> s;
			for (int i = 1; i <= x; i++) {
				if (a[i] > a[1]) continue;
				auto it = s.upper_bound(a[i]);
				if (it != s.begin()) s.erase(--it);
				s.insert(a[i]);
			}
			for (int i = 1; i <= n; i++) sum[i] = 0;
			for (int i = x + 1; i <= n; i++) sum[a[i]]++;
			for (int i = 2; i <= n; i++) sum[i] += sum[i - 1];

			int i = s.size();
			for (auto j : s) { if (i + sum[j] >= m) return i; i--; }
			return 0;
		};
		int l = 0, r = n;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		int ans = m - check(l);
		vector<int> sec; sec.emplace_back(1);
		if (l < 1) ans --;
		for (int i = 1; i <= n; i++)
			if (ans && id[i] != 1 && id[i] > l) sec.emplace_back(id[i]), ans--;
		sort (sec.begin(), sec.end(), [&](int x, int y) {return a[x] > a[y];});
		for (auto i : sec) vis[i] = 1;
		for (auto i : sec) {
			printf ("%d ", a[i]);
			for (int j = i + 1; j <= n && !vis[j]; j++) printf ("%d ", a[j]);
		}
		putchar(10);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}