[AGC068C] Ball Redistribution 题解

· · 题解

题传

首先，我们可以想到，将 i 向 a_i 连边，表示球 i 在盒子 a_i 中。

这样我们就得到了一棵基环内向树。

我们考虑每次对盒子 i 操作在干什么。

其实就是把所有连向 i 的点拿出来，按任意顺序连成一个环。

但是我们考虑，每次连成环的过程中，我们无法得知应该按怎样的顺序去排列环，而且我们并不知道这张图的初始状态是怎样的，所以我们考虑倒着操作。

考虑将 i 从 n 到 1 枚举的过程中，每次如何变化这张图。

实际上就是每次把一个环全部断开，然后全都连到 i 上。

但是这样做是有问题的。

我们在正着做的时候，由于我们每次拿出了所有连向 i 的点，所以每次对于 i 操作完，点 i 一定要么入度为 0，要么处在某一个环上，且除了环上的点没有点连向他，这就限制了我们每次操作 i 的时候，必须保证当前图满足操作后的条件。

那么可以想到，如果我们在操作过程中发现当前的 i 不合法，那么肯定就无解了。

那么我们每次应该操作哪个环才能最优呢？

我们考虑每次断开的环如果不在当前连通块，那么每个点的可操作性是不变的（可以自己画一画）；如果在当前连通块，那么我们发现，原来可操作的还能操作，如果当前点入度为 0，原来一些在当前点到环的路径上的点，可能从不能操作变为可操作，所以证明，我们每次操作当前连通块内的环一定是最优的。

所以我们可以暴力扫，每次找到当前环，然后暴力更改。

这样做乍一看是 O(n^2) 的，实际上可以分析到 O(n\sqrt n)，可以均摊。

我们令环长为 L，每次的花费实际上就是 O(L) 的。（可能还会多一点环之前的链，但是由于操作一次后链就变成环了，所以我们认为这还是环）。

总花费是 O(\sum L) 的。

设 S 为当前图上每个点的入度的平方和，显然，S\le n^2。

我们考虑操作一次后，S 是如何变化的，对于原来在环上的点，它们的入度 -1；对于 i，他的入度 +L。

我们令 ind_i 表示 i 节点的入度，那么 S 的变化就是 (ind_{i}+L)^2+\sum_{\text{x on ring}} (ind_x-1)^2-ind_i^2-\sum_{\text{x on ring}} ind_x^2=L^2+2\times ind_i\times L-\sum_{\text{x on ring}} 2\times ind_x+1。

所以 S 的变化每次是 O(L^2)-O(n) 的。

要变化 n 次，那么 \sum L^2 最多是 O(n\sqrt n) 级别的。

实际上跑的飞快。

更详细的证明可以看这里。

感谢 @KSCD_ 和 @Pigsyy 的帮助。

提交记录。