XJOI 11.15

### XJOI 11.15 ### T1 Graph 一个通用的解法： 考虑随机一个排列 $ P $ .一个 $ u $ 产生贡献仅当他是与 $ u $ 有边的点和自己（共 $ deg_u+1 $ 个）中不是最晚出现。 所以答案就是 $ \sum_u\frac{deg_u}{deg_u+1} $ ### T2 ds 首先可以用`std::map`做一个在线离散化。 考虑 $ B $ 个分一块。预处理 $ (n/B)^2 $ 个块之间的答案，并对 $ n/B $ 个块处理前缀每种颜色的出现次数。 对于询问，已经知道中间大块的答案， $ O(B) $ 加上两边的散块即可。 对于修改，影响了 $ (n/B)^2 $ 个块间的答案，但都能 $ O(k) $ 或 $ O(\log k) $ 修改。 平衡 $ (n/B)^2=B $ 得到 $ B=n^{2/3} $ .最终复杂度 $ O(n^{5/3}) $ . ### T3 Tree 搓魔方！ 考虑从叶子开始逐层构造，显然要求有颜色出现次数 $ \ge 2^{D-1} $ ，并且如果存在，必然是唯一的。 那么考虑将不满足条件的叶子换掉。考虑实现一个`Move(x,y)` 操作，将 $ x $ 的颜色给 $ y $ ，并且不影响深度更大的点。 分讨两种情况： $ x,y $ 到根的路径无公共边和有公共边。 无公共边：这一步就很像魔方，考虑将 $ y $ 拉到底然后 $ x $ 再拉到底，那么 $ y $ 的颜色就变成了 $ x $ 的颜色，然后分别拉回去就行了，次数是 $ 2D+O(1) $ 有公共边：取一中间点 $ z $ ,满足与 $ x,y $ 到根的路径均无公共边，变成两个无公共边的问题。次数是 $ 4D+O(1) $ 最坏是 $ 4\times 2^DD+O(2^D) $ .似乎爆标了？ ### T4 per 首先 $ A_i=P_i $ 或 $ i $ 联想到最小割。 ~~感谢CSP，好罢~~ 但是仅通过最小割指定 $ A $ 的选取，不能保证是一个排列。 考虑 $ P $ 中的一个环 $ C $ . - 若 $ i\in C $ 选取了 $ A_i=i $ ,那么 $ \forall j\in C,A_j=j $ 必须成立。 - 若 $ i\in C $ 选取了 $ A_i=P_i $ ,那么 $ \forall j\in C,A_j=P_j $ 必须成立。 那么将这个环看作一个整体，只有"全部选 $ i $ "和"全部选 $ P_i $ " 两种选择. 考虑一个 $ P $ 中的环 $ C_1 $ 和 $ Q $ 中的环 $ C_2 $ 的一个公共点 $ i $ 的贡献。 - $ P_i=Q_i=i $ 那么必然有 $ A_i=B_i=i $ ，产生1的代价。 - $ P_i=i,Q_i\ne i $ 那么若 $ B_i=i $ 会产生1的代价。 - $ P_i\ne i,Q_i=i $ 那么 $ A_i=i $ 会产生1的代价。 - $ P_i=Q_i\ne i $ 那么 $ A_i=B_i $ 会产生1的代价。 - $ P_i\ne Q_i,P_i\ne i,Q_i\ne i $ ,那么 $ A_i=B_i=i $ 会产生1的代价。 那么用最小割描述，建一张图，左侧 $ n $ 个点表示 $ A $ ,右侧 $ n $ 个点表示 $ B $ ,然后再建 $ S,T $ 一个比较直观但最终没前途的想法是，左侧 $ n $ 个点划分到 $ S $ 所在集合表示 $ A_i=i $ ,划分到 $ T $ 所在集合表示 $ A_i=P_i $ ,右侧分到 $ S $ 表示 $ B_i=i $ ,分到 $ T $ 表示 $ B_i=Q_i $ .但这样很难描述 $ A_i=B_i $ 则产生1的代价 这个事件。 那么反转右侧，即右侧分到 $ T $ 表示 $ B_i=i $ ,分到 $ S $ 表示 $ B_i=Q_i $ . 那么 $ A_i=B_i=i $ 就连边 $ (C_1\rightarrow C_2,1) $ . 那么 $ A_i=B_i $ 产生1的代价 就连边 $ (C_1\rightarrow C_2,1) $ 和 $ (C_2\rightarrow C_1,1) $ .(对应 $ S\rightarrow C_1\rightarrow C_2\rightarrow T $ 和 $ S\rightarrow C_2\rightarrow C_1\rightarrow T $ 的两种情况) 最后就是一个最小割了。 PS:其实这个算是"有向图最小割"，但和无向图最小割没什么不同，线性规划对偶的分析依然适用。