自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:14:30，当前版本为作者最后更新于2023-02-15 11:36:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对 $a$ 排序。

• 若存在 $a_i > i$，则一定无解。

证明：已知 $p_i < i$，但此时构造出的 $p_{i + 1} > i$，则不合法。

• 所有 $a_i = i$ 的 $i$ 一定在 $1 \to n$ 的路径上。

证明：此时任何从 $\leq i$ 的点到 $> i$ 的点的路径都要经过 $i$。

• $1 \to n$ 的路径长度大于等于 $a_i = i$ 的 $i$ 的个数且小于等于 $a$ 去重后的元素个数。

证明：由上一条以及 $p_i < i$ 可得。

• 设上一条中确定的上下界为 $[l, r]$，则 $\forall k \in [l, r]$ 均存在满足条件的树。

证明：我们可以构造如下一棵树：

• $1 \to n$ 的路径的父亲序列由 $a_i = i$ 的 $i$（设其有 $i$ 个）、其他元素中互异且前 $k - cnt$ 小者组成。
• $1 \to n$ 的路径的边权序列由余下元素中前 $k$ 大组成。
• 其他信息由余下元素组成。

而我们构造出的树同样满足权值最大的性质，于是我们维护一棵支持单点删除、求前 $k$ 大的线段树即可。时间复杂度为 $O(n \log n)$。

代码：

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

typedef long long ll;

typedef struct {
	int l;
	int r;
	int cnt;
	ll sum;
} Node;

int a[200007], b[200007], diff[100007];
bool mark[100007], vis[100007];
Node tree[800007];

inline void update(int x){
	int ls = x * 2, rs = x * 2 + 1;
	tree[x].cnt = tree[ls].cnt + tree[rs].cnt;
	tree[x].sum = tree[ls].sum + tree[rs].sum;
}

void build(int x, int l, int r){
	tree[x].l = l;
	tree[x].r = r;
	if (l == r){
		tree[x].cnt = 1;
		tree[x].sum = b[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
	update(x);
}

void erase(int x, int pos){
	if (tree[x].l == tree[x].r){
		tree[x].cnt = tree[x].sum = 0;
		return;
	}
	if (pos <= ((tree[x].l + tree[x].r) >> 1)){
		erase(x * 2, pos);
	} else {
		erase(x * 2 + 1, pos);
	}
	update(x);
}

ll get_sum(int x, int k){
	if (tree[x].cnt == k) return tree[x].sum;
	int ls = x * 2;
	if (k <= tree[ls].cnt) return get_sum(ls, k);
	return get_sum(x * 2 + 1, k - tree[ls].cnt) + tree[ls].sum;
}

int main(){
	int n, m, mink = 0, cnt = 0, maxk = 0;
	cin >> n;
	m = (n - 1) * 2;
	for (register int i = 1; i <= m; i++){
		cin >> a[i];
	}
	sort(a + 1, a + m + 1);
	for (register int i = 1; i <= m; i++){
		if (a[i] > i){
			for (register int j = 1; j < n; j++){
				cout << -1 << " ";
			}
			return 0;
		}
		if (a[i] == i){
			mink++;
			mark[a[i]] = true;
		} else {
			b[++cnt] = a[i];
		}
		if (!vis[a[i]]){
			vis[a[i]] = true;
			maxk++;
		}
	}
	if (mink >= n || mink > maxk){
		for (register int i = 1; i < n; i++){
			cout << -1 << " ";
		}
		return 0;
	}
	reverse(b + 1, b + cnt + 1);
	for (register int i = cnt, j = 0; i >= 1; i--){
		if (!mark[b[i]] && b[i] != b[i + 1]) diff[++j] = i;
	}
	build(1, 1, cnt);
	for (register int i = 1; i < mink; i++){
		cout << -1 << " ";
	}
	for (register int i = mink; i <= maxk; i++){
		if (i > mink) erase(1, diff[i - mink]);
		cout << get_sum(1, i) << " ";
	}
	for (register int i = maxk + 1; i < n; i++){
		cout << -1 << " ";
	}
	return 0;
}