题解 CF643D 【Bearish Fanpages】

> [CF643D Bearish Fanpages](https://codeforces.com/contest/643/problem/D) ## 题意 - 给定一个 $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)$。 ## 代码 ```cpp 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; } ```