P3542 [POI 2012] PEN-Salaries

真神仙题，看到这个题之后想把 POI 刷一遍。

前情提要

生产队的驴要这么歇早被拉出去砍了。

此题成分复杂。

别骂了前一天场切贪吃蛇和喵了个喵注意力不足了。

思路

神秘贪心（树动规？我不知道啊）题，拼尽全力无法战胜。

显然的注意是一个点的 $z$ 最大值是且仅是由其祖先确定的。

于是有一个模糊的想法，每一个点的祖先确定其 $z$ 最大值，而其最小值是 $z$ 一定比它小的节点数量加一。

来求最大值。这里记 $mx$ 数组，$mx_i$ 表示第 $i$ 个点最大选的 $z_i$ 能够是多少。据传说这里有一个典型技巧（这种偏构造的技巧八成出自 CF），使用类似并查集的方法，开一个 $pre$ 数组。$pre_i$ 表示一个点的 $z$ 如果要小于等于 $i$ 那么最大取到多少，初始都设置为 $i$。如果一个 $z_i$ 已存在则 $pre_{z_i} = z_i - 1$。设置完之后对于每个 $i$ 从小到大做一遍 $pre_i = pre_{pre_i}$。显然这么做可以正确处理出来所有 $pre_i$。

$mx$ 的维护比较简单，见代码。

接下来就是求最小值部分了。发现对于每个店做很难做，于是转变为对每个数字做。记 $c$ 数组，$c_i$ 表示 $mx$ 为 $i$ 的位置个数。显然 $i - (c_1 + \cdots c_{i - 1})$ 就是能取 $i$ 的个数，如果为 $1$ 则把 $mx$ 为 $i$ 的那个点可以直接设为 $i$，保证有解所以永远不会出现 $i - (c_1 + \cdots c_{i - 1})$ 为负的情况。

Code

#include <iostream>
#include <vector>
// #define int long long
using namespace std;
vector<int> a[1000010];
int z[1000010], fa[1000010], n, pre[1000010];
int c[1000010], mx[1000010];
int rt;
int dy[1000010];
void dfs(int p) {
	//cerr << p << '\n';
	if(z[p] == 0) mx[p] = pre[mx[fa[p]] - 1]; // 想要 mx[fa[p]] - 1 但是可能取不到
	else mx[p] = z[p];
	c[mx[p]]++;
	dy[mx[p]] = p;
	for(int i = 0; i < a[p].size(); i++) if(a[p][i] != p) dfs(a[p][i]);
}
signed main() {
	cin >> n;
	for(int i = 1; i <= n; i++) pre[i] = i; // 典型技巧，维护并查集状物
	for(int i = 1; i <= n; i++) {
		cin >> fa[i] >> z[i];
		if(fa[i] == i) rt = i;
		pre[z[i]] = z[i] - 1;
		a[fa[i]].push_back(i);
	}
	z[rt] = n;
	for(int i = 1; i <= n; i++) pre[i] = pre[pre[i]];
	dfs(rt);
	int su = 0;
	for(int i = 1; i <= n; i++) {
		su++;
		su -= c[i];
		if(c[i] == 1 && su == 0) z[dy[i]] = i;
	}
	for(int i = 1; i <= n; i++) cout << z[i] << '\n';
	return 0;
}

后记

• CF 题还是练少了。

• 通过对飞屋 muyangli 的观察发现它的注意力是有限的。注意力不充足的时候经常被 D2C（D1）草似，而注意力充足的时候甚至可以切掉 F。

• 空间 122.74 卡着线飞过去的。