CF643D Bearish Fanpages 题解

CF643D Bearish Fanpages

题意

• 给定一个 $n$ 个点的基环森林，第 $i$ 个点与 $f_i$ 之间有一条边。
• 保证在任意时刻，这个基环森林中的环长至少为 $3$。
• 当一种「神秘事件」发生时，对于第 $i$ 个点，设与其相邻的点（包括 $f_i$ 和 $f_j = i$ 的 $j$）的个数为 $k$，这 $k$ 个点上都会出现 $\lfloor \frac{t_i}{k+1} \rfloor$ 个人，而 $i$ 上会出现 $t_i - k \cdot \lfloor \frac{t_i}{k+1} \rfloor$ 个人。
• 每次「神秘事件」发生都是互不影响的。
• 有 $q$ 个操作，操作有三种。
  1. 1 i j：将 $f_i$ 改为 $j$，此操作不超过 $5 \times 10^4$ 个。
  2. 2 i：询问当「神秘事件」发生时，第 $i$ 个点上出现的人数。
  3. 3：询问当「神秘事件」发生时，所有点上出现的人数的最小值和最大值。
• $n,q \le 10^5$，$t_i \le 10^{12}$。

题解

对于点 $i$，将 $f_j = i$ 的所有 $j$ 的权值去掉 $i$ 的贡献后存到 $i$ 上的一个 multiset 里（记为 $s_i$），然后 multiset 里的最大最小值加上 $i$ 的贡献存到一个大 multiset 里（记为 $s_0$）。

设 $a_i$ 表示 $i$ 去掉 $f_i$ 的贡献后的权值，$d_i$ 表示 $i$ 的度数。

考虑每次修改，即将 $f_i$ 改为 $j$ 的过程：

• 由于修改后 $i$ 不再对 $f_i$ 有贡献，$a_{f_i}$ 要减去修改前来自 $i$ 的贡献 $\lfloor \frac{t_i}{d_i+1} \rfloor$，$s_{f_i}$ 中删除 $a_i$。
• 由于 $d_{f_i}$ 修改后要减去 $1$，$a_{f_i}$ 要减去修改前自身的贡献 $t_{f_i} - d_{f_i} \cdot \lfloor \frac{t_{f_i}}{d_{f_i}+1}\rfloor$，加上修改后自身的贡献 $t_{f_i} - (d_{f_i}-1) \cdot \lfloor \frac{t_{f_i}}{d_{f_i}}\rfloor$，$s_{f_{f_i}}$ 要更新 $a_{f_i}$。
• 由于 $d_{f_i}$ 修改后要减去 $1$，$a_{f_{f_i}}$ 要减去修改前来自 $f_i$ 的贡献 $\lfloor \frac{t_{f_i}}{d_{f_i}+1} \rfloor$，加上修改后来自 $f_i$ 的贡献 $\lfloor \frac{t_{f_i}}{d_{f_i}} \rfloor$，$s_{f_{f_{f_i}}}$ 要更新 $a_{f_{f_i}}$。

此时执行修改，即 $d_{f_i}$ 减去 $1$，$f_i$ 改为 $j$，$d_j$ 加上 $1$，然后将上面的过程反向重复一遍。

• 由于修改前 $i$ 对 $j$ 没有贡献，$a_{j}$ 要加上修改后来自 $i$ 的贡献 $\lfloor \frac{t_i}{d_i+1} \rfloor$，$s_{j}$ 中插入 $a_i$。
• 由于 $d_{j}$ 修改后加上了 $1$，$a_{j}$ 要减去修改前自身的贡献 $t_{j} - (d_{j}-1) \cdot \lfloor \frac{t_{j}}{d_{j}}\rfloor$，加上修改后自身的贡献 $t_{j} - d_{j} \cdot \lfloor \frac{t_{j}}{d_{j}+1}\rfloor$，$s_{f_{j}}$ 要更新 $a_{j}$。
• 由于 $d_{j}$ 修改后加上了 $1$，$a_{f_{j}}$ 要减去修改前来自 $j$ 的贡献 $\lfloor \frac{t_{j}}{d_{j}} \rfloor$，加上修改后来自 $j$ 的贡献 $\lfloor \frac{t_{j}}{d_{j}+1} \rfloor$，$s_{f_{f_{j}}}$ 要更新 $a_{f_{j}}$。

注意每次更新 $s_i$ 的操作实质上是先删除再修改后插入，必须保证删除在修改之前，因此不能完全按照上面的顺序来做。

另外，别忘了每次更新 $s_i$ 还要同步更新 $s_0$，同时注意不能重复插入或删除。

所以实际上本题是个模拟题，总时间复杂度 $\mathcal O((n+q) \log n)$。

代码

const int N = 1e5 + 7;
int n, q, d[N], f[N];
bool v[N];
ll a[N], t[N];
multiset<ll> s[N];

inline void del(int x) {
	if (v[x] && s[x].size())
		v[x] = 0,
		s[0].erase(s[0].find((*s[x].begin()) + t[x] / (d[x] + 1))),
		s[0].erase(s[0].find((*(--s[x].end())) + t[x] / (d[x] + 1)));
}

inline void add(int x) {
	if (!v[x] && s[x].size())
		v[x] = 1,
		s[0].insert((*s[x].begin()) + t[x] / (d[x] + 1)),
		s[0].insert((*(--s[x].end())) + t[x] / (d[x] + 1));
}

inline void work(int i, int j) {
	del(f[i]), del(f[f[i]]), del(f[f[f[i]]]);
	del(j), del(f[j]), del(f[f[j]]);

	s[f[i]].erase(s[f[i]].find(a[i]));

	s[f[f[i]]].erase(s[f[f[i]]].find(a[f[i]]));
	a[f[i]] -= t[i] / (d[i] + 1);
	a[f[i]] -= t[f[i]] - d[f[i]] * (t[f[i]] / (d[f[i]] + 1));
	a[f[i]] += t[f[i]] - (d[f[i]] - 1) * (t[f[i]] / d[f[i]]);
	s[f[f[i]]].insert(a[f[i]]);

	s[f[f[f[i]]]].erase(s[f[f[f[i]]]].find(a[f[f[i]]]));
	a[f[f[i]]] -= t[f[i]] / (d[f[i]] + 1);
	a[f[f[i]]] += t[f[i]] / d[f[i]];
	s[f[f[f[i]]]].insert(a[f[f[i]]]);

	--d[f[i]], ++d[j];

	s[j].insert(a[i]);

	s[f[j]].erase(s[f[j]].find(a[j]));
	a[j] += t[i] / (d[i] + 1);
	a[j] -= t[j] - (d[j] - 1) * (t[j] / d[j]);
	a[j] += t[j] - d[j] * (t[j] / (d[j] + 1));
	s[f[j]].insert(a[j]);

	s[f[f[j]]].erase(s[f[f[j]]].find(a[f[j]]));
	a[f[j]] -= t[j] / d[j];
	a[f[j]] += t[j] / (d[j] + 1);
	s[f[f[j]]].insert(a[f[j]]);

	add(f[i]), add(f[f[i]]), add(f[f[f[i]]]);
	add(j), add(f[j]), add(f[f[j]]);

	f[i] = j;
}

int main() {
	rd(n), rd(q), rda(t, n), rda(f, n);
	for (int i = 1; i <= n; i++) ++d[i], ++d[f[i]];
	for (int i = 1; i <= n; i++)
		a[i] += t[i] - d[i] * (t[i] / (d[i] + 1)),
		a[f[i]] += t[i] / (d[i] + 1);
	for (int i = 1; i <= n; i++) s[f[i]].insert(a[i]);
	for (int i = 1; i <= n; i++) add(i);
	while (q--) {
		int o, i, j;
		rd(o);
		switch (o) {
			case 1 : rd(i), rd(j), work(i, j); break;
			case 2 : rd(i), print(a[i] + t[f[i]] / (d[f[i]] + 1)); break;
			case 3 : print(*s[0].begin(), ' '), print(*(--s[0].end())); break;
		}
	}
	return 0;
}