好题题解整理（三）
没有摘要。
cf1368f Lamps on a Circle
有一个长为 \(n\) 的环，环上每个点是一个开关，Alice Bob 玩游戏，每轮执行以下流程：
- Alice 选择是否结束游戏。如果是则游戏结束。
- Alice 选择一个参数 \(k\) ，并将任意 \(k\) 个开关打开。
- Bob 将任意连续的 \(k\) 个开关关闭。
Alice Bob 分别想要最大最小化最后打开的开关数量。设 \(R(n)\) 是双方执行最优策略时最后打开的开关数量。
交互题，实现 Alice 的策略，使得最后打开的开关数量不少于 \(R(n)\) 。
题解
不妨让 Alice 去复制 Bob 的操作，那么只要 Bob 选择连续 \(k\) 个开关不是全开的，通过一次复制后回到 Bob 操作，局面不变，但是 \(k\) 会变小，因为 Alice 只需要选择那些实际上被 Bob 关闭的开关。
那么可以发现 Bob 实际上只能关掉不超过 \(k\) 的一个全部打开的连续段。游戏的一轮可以转换为以下流程：
- Alice 选择是否结束游戏。如果是则游戏结束。
- Alice 选择一个参数 \(k\) ，并将任意 \(k\) 个开关打开。
- Bob 选择长度不超过 \(k\) 的 连续 的一段 打开的 开关关闭。
进一步可以发现这个游戏只需要进行一轮，进行多轮是没有意义的。这样一来，游戏的最终局面仅仅由 Alice 第一次打开的开关集合有关，设 Alice 打开了 \(p\) 个连续段，第 \(i\) 个连续段长度为 \(a_i\) 。那么问题就是在满足 \(\sum_{i=1}^p (a_i+1) \le n\) 的前提下最大化
\[\sum_{i=1}^p a_i - max\{a_i\}\]
显然前者的和最大不超过 \(n-p\) ，只需要最小化后者，尽量使得 \(a\) 平均时最优，可以得到
\[R(n) = max\{n - p - \lceil \frac{n-p}{p} \rceil\}\]
用上述策略实现 Alice 即可。
cf1368e Ski Accidents
有一张 \(n\) 个点的 DAG ，每个点的出度不超过 2 ，求一个大小不超过 \(\frac{4n}{7}\) 的点集使得该点集的补集的导出子图没有一个点同时有出度和入度。
时间复杂度：\(O(n)\) 。
题解
一个很自然的贪心是按照拓扑序一个个加点，只要当前点加入后仍然不存在同时有出度和入度的点就加入该点。最后把没有加入的点作为答案。
猜结论选手直接一交发现它 A 了。
这样做确实是对的，观察这个诡异的分数 \(\frac{4}{7}\) ，注意到 \(1 + 2 + 4 = 7\) ，这或许能带来一些启发。
称上述贪心过程中加入的点集为 \(S\) ，其补集为 \(C\) ，\(S\) 的导出子图中没有入度的点集 \(A\) ，其他的点集为 \(B\) 。由于每个点的出度不超过 2 ，显而易见的是 \(|C| \le 2|B| \le 4|A|\) ，那么 \(|C|\) 就不会超过 \(\frac{4n}{7}\) 。
lg5433 月宫的符卡序列
给定长为 \(n\) 的字符串 \(s\) ，定义一个回文串的权值是该回文串在 \(s\) 中所有出现位置的中点（下取整）的异或和，求最大权值回文串。
时间复杂度：\(O(n)\) 。
题解
（未实现）
PAM 在处理中点相关的问时会比较无力，如果是端点算贡献倒是很好用 PAM 处理。但也未尝不能做。虽然 PAM 只能简单地维护 right 集合，但只要来个 PAM 套 01-trie ，用类似于《联合省选 2020 树》的技巧，就能推广到维护中点集合，不过会带来时间和空间上更大的开销，不在讨论范围内。
manacher 处理中点相关的问题往往更简单，把 \(s\) 特殊处理后得到 \(t\) ，考虑每个位置作为中点的贡献，贡献到的会是一堆串，这些串在 PAM 上形成了一条链。因此对 \(t\) 建 PAM ，配合 manacher 做树上差分即可。这个 PAM 比较特殊，事实上此时这个 PAM 是真正的回文自动机，不需要建两个根节点。
lg5227 [AHOI2013] 连通图
给定一张 \(n\) 点 \(m\) 边的图，\(q\) 次询问，每次给定大小 \(O(1)\) 的边集求原图删掉该边集后是否连通。
时间复杂度：\(O(n + m + q)\) 。
题解
（未实现）
大力 lct 维护动态图连通性。
引理 1
对于任意一颗生成树，给每条边一个 01 向量，满足每条树边的向量恰好是其被覆盖的非树边的异或和，且每条非树边的向量线性无关。那么有：删掉边集 E 后图不连通当且仅当 E 中向量线性相关。
证明繁琐，可以参见 yhx-12243 的博客。
正题
显然给每条非树边一个线性无关的向量是不现实的，这至少需要 \(m-n+1\) 维。不妨给每条非树边一个均匀随机的 \(k\) 维向量，本质上是一个哈希，\(k\) 足够大的时候冲突概率就会很低，冲突概率约为 \(2^{d-k}\) ，其中 \(d\) 是边集大小。
于是只需要判断一组向量是否线性相关即可，边集很小，暴力判断或使用线性基。复杂度 \(O(\frac{k}{w})\) 或 \(O(\frac{k^2}{w})\) ，不妨取 \(k=w\) ，可以做到 \(O(1)\) 回答询问。
边集大小任意的话复杂度分析下来应该是 \(O(n + md + q\frac{d^3}{w})\) ，因为需要分配的维度大小得是 \(d + O(1)\) 的。
loj536 「LibreOJ Round #6」花札
Alice Bob 分别有 \(n\) 张牌，每张牌有一个颜色和一个点数，每个人轮流打出一张牌，要求必须和上一张的颜色或者点数一致，不能操作者输。
Alice 先手，求每张牌作为第一张牌被打出后游戏的必胜必败态。
时间复杂度：\(O(n^{\frac{5}{3}})\) 。
题解
图论模型
把双方的牌看做节点，然后根据是否有颜色/点数相同连边，得到一张二分图 \(G\)，那么这个游戏就可以描述为：从一个节点开始，每次选一条边走过去，不能走重复的点，不能操作者输。
这是个经典问题，同《[JSOI2009] 游戏》，结论是一个点是先手必胜的当且仅当它存在于所有最大匹配的交集中，应用反证法很容易证明。然而游戏那题数据范围小得多，显然不能直接套用过来。
优化连边
注意到 \(G\) 的边数是 \(O(n^2)\) 的，必然需要优化连边。
直接在二分图上优化连边不太方便。不妨用网络流描述这个二分图匹配，然后优化网络流的连边使得前后的网络流等价。由于两点连边当且仅当颜色或点数相同，容易想到对每个颜色和点数建辅助点，然后在网络流上，\(u\) 向所有颜色和点数连边，所有颜色和点数向对应的 \(v\) 连边，就能间接连边 \(u \rightarrow v\) 。这样一来点数和边数都是 \(O(n)\) 的。
残量网络
然后需要判断一个点 \(u\) 是否存在于所有的最大匹配中，也就是在所有最大流中 \(S \rightarrow u\) 这条边都有流量。常规的做法是求出一组最大流，然后删掉 \(u\) 再求一遍最大流，若最大流减小了就说明 \(u\) 所有最大流都要经过 \(u\) 。虽然删掉 \(u\) 重新跑最大流是不现实的，但是这可以带来一些启发，在一组最大流的残量网络上考虑这个过程，可以发现删掉 \(u\) 不改变最大流说明可以通过一些手段把 \(S \rightarrow u\) 的流量退掉并且不影响最大流，也就是说残量网络上存在一条从 \(S\) 到 \(u\) 的路径。
那么求出任意一组最大流，然后在残量网络上 dfs 出所有 \(S\) 能到达的点 \(u\) 即可。
dinic 的复杂度是 \(O(n^2m)\) 的，查了一下在单位容量的图上似乎是 \(O(\max\{n^{2/3}, m^{1/2}\} m)\) 的（不确定），在此题中就是 \(O(n^{5/3})\) 。
lg6730 [WC2020] 猜数游戏
给定模数 \(p\) ，定义一个数 \(x\) 的导出集合为 \(F(x) = \{y|x^k \equiv y \pmod{p}\}\) 。对于一个非空集合 \(S\) ，称它的非空子集 \(T\) 是优秀的，当且仅当 \(T\) 中元素的导出集合的并集是 \(S\) 的父集。\(S\) 的权值定义为其最小的优秀子集的大小。
给定大小为 \(n\) 的一个数集 \(S\) ，求所有子集的权值和。另外，保证 \(p=q^k\) ，其中 \(q\) 是奇质数。
时间复杂度：\(O(nk\log p + d(\varphi(p))k)\) ，其中 \(d\) 表示约数个数函数，\(k\) 表示 \(\varphi(p)\) 的质因子个数。
题解
集合关系
先考虑一个关键的问题，如何判断 \(y \in F(x)\) 是否成立。一个朴素的做法是 BSGS ，单次复杂度 \(O(\sqrt{p})\) ，显然代价太大不能接受。
但是注意到 \(p\) 是一定有原根 \(g\) 的，那么如果 \(q|x \lor q|y\) 可以直接枚举 \(k\) 暴力判断，否则一定可以表示为 \(x = g^a, y = g^b\) 。于是 \(y \in F(x)\) 等价于关于 \(k\) 的方程 \(g^{ak} \equiv g^b\) 有解。该方程等价于 \(ak \equiv b \pmod{\varphi(p)}\) ，显然有解的充要条件是
\[\gcd(a, \varphi(p)) | \gcd(b, \varphi(p))\]
注意到事实上 \(\mathrm{ord} x = \frac{\mathrm{lcm}(\varphi(p), a)}{a} = \frac{\varphi(p)}{\gcd(a, \varphi(p))}\) ，因此上式还等价于
\[\mathrm{ord} y | \mathrm{ord} x\]
也就是说只需要求出 \(S\) 每个数模 \(p\) 意义下的阶，就可以简单判断这个集合关系了。求阶可以用试除法 + 快速幂，试除只需要枚举 \(\varphi(p)\) 的每个质因子，复杂度 \(O(\log^2p)\) 。
统计答案
如果将 \(y \in F(x)\) 这个关系连边 \(x \rightarrow y\) ，那么一个点集的权值就是最小点覆盖。观察这个图，由于连边的唯一判断依据是阶，可以发现阶相同的数连成了一个团，把这个团看做一个整体的点的话，整张图就是一张 DAG 。那么算一个给定图的权值是容易的，就是没有入度的团的数量（注意这张图的连边有传递性，也就是分层后层数不超过 2）。
现在要统计所有子集的权值和，对于每个团单独算贡献，那么一个子集 \(T\) 中该团产生贡献（作为没有入度的团）当且仅当
- 该团中至少一个点在 \(T\) 中
- 连向该团的其他团的任何点都不在 \(T\) 中。
设一个团大小为 \(x\) ，有 \(y\) 个不在该团的点连向该团，那么综上一个团的贡献就是 \((2^x-1)2^{n-y-x}\) 。
建图
可以发现尽管我们知道了连边方式，但是 \(n\) 很大的时候显式地连边显然不行，不过我们并不关注具体连边，只需要关注每个点的入度。
统计一个阶为 \(x\) 的团的入度的数量也就是统计有多少个数的阶是 \(x\) 的倍数。目前我没有想到很好的解决方案，可以用高维前缀和做这个经典问题，复杂度 \(O(d(\varphi(p))\log)\) 。
lg3665 [USACO17OPEN]Switch Grass P
给定一张 \(n\) 个有色点 \(m\) 条带权边的图，\(q\) 次询问，每次修改一个点的颜色，求权值最小的边，满足两个端点颜色不同。
时间复杂度：\(O(m\log + n + q\log)\) 。
题解
（未实现）
引理 1
确定一颗最小生成树，那么所有非树边不可能作为答案。
应用反证法，注意到非树边的权值一定不小于其覆盖的所有树边，并且如果非树边两个端点颜色不同，那么其覆盖的树边也一定存在至少一个端点异色。
正题
根据引理 1 ，图可以转换为树。
考虑如何维护一个修改，由于修改一个点只会影响其连接的边，一个经典的做法是度数分块，但是不能接受。正确的做法比较繁琐，就是对于每个点维护其儿子的颜色集合，这是很好维护的。其次维护每个点往儿子连边的最优答案，维护儿子集合的同时也能更新。再然后就是维护每个点的最有答案，对于询问取最小值。
个人认为本题精彩的部分就在于引理 1 。
hdu6311 Cover
给定一张 \(n\) 点 \(m\) 边的无向图，要求使用最少的路径覆盖所有边。
时间复杂度：\(O(n + m)\) 。
题解
不妨假设图连通。假设用 \(k (k > 1)\) 条路径覆盖所有边，那么将路径的端点用 \(k\) 条虚边连成一个回路，那么该回路就是新图（原图加虚边）的欧拉回路。
同样的，如果先给图加上 \(k\) 条虚边然后求新图的欧拉回路，把欧拉回路上的虚边割掉就可以得到原图的一组 \(k\) 个路径的覆盖方案。
那么问题等价于加上最少的虚边使得图有欧拉回路，一个无向图有欧拉回路当且仅当所有所有点的度数为偶数，因此最少的加边方案就是把奇度点（一定有偶数个）任意弄个匹配。
cf1299e So Mean
有一个 \(n\) 元排列 \(\{p\}\) ，需要通过若干次询问确定该排列，每次询问可以给定一个子集，得到该子集的平均数是否为整数。
特别的，对于该排列的逆 \(\{q\}\) ，总有 \(q_1 < q_n\) 。
询问次数不超过 \(18n\) ，\(n\) 是不超过 \(800\) 的偶数。
题解
（未实现）
trick 1
询问大小为 2 的子集 \(\{p_i, p_j\}\) ，可以知道它们的奇偶性是否相同。
trick 2
询问大小为 \(n-1\) 的子集 \(U \setminus \{p_i\}\) ，由于 \(\sum_{x \in U} x \equiv \frac{n(n+1)}{2} \equiv 1 \pmod{n-1}\) ，询问的结果为真当且仅当 \(p_i \equiv 1 \pmod{n-1}\) ，容易发现只有 \(1\) 和 \(n\) 满足条件，因此这样就能确定 \(q_1\) 和 \(q_n\) 。
结合 trick 1 ，可以知道所有数的奇偶性。
trick 3
考虑推广 trick 2 ，在已知 \(q_1 ... q_k, q_{n-k+1} ... q_n\) 的情况下询问一个大小为 \(n-2k-1\) 的子集 \(S \setminus \{p_i\}\) ，其中 \(S\) 是剩余的未知数，注意到 \(\sum_{x \in S} x \equiv \frac{(n+1)(n-2k)}{2} \equiv k+1 \pmod{n-2k-1}\) ，因此询问的结果为真当且仅当 \(p_i \equiv k + 1 \pmod{n-2k-1}\) ，满足条件的数只有 \(k+1\) 和 \(n-k\) ，并且它们奇偶性不同，由此可以确定 \(q_{k+1}\) 和 \(q_{n-k}\) 。
可以发现反复使用这个 trick 总能在 \(O(n^2)\) 次询问后得到整个排列。
trick 4
通过 trick 1 + trick 2 实际上得到了所有数在模 2 意义下的值。对于 \(p_i \bmod 2 = 1\) ，其在模 4 意义下只能是 1 或 3 ，如果用三个和为 1 （模 4 意义下）的已知的数（称之为 3 元组）和 \(p_i\) 一起询问，就可以判断出 \(p_i\) 在模 4 意义下的值，对于 \(p_i \bmod 2 = 0\) 同理。
同样的道理，知道每个数模 4 的值后还可以通过若干 7 元组得到每个数模 8 的值。
trick 5
如果能找到 \(k-1\) 个模 \(k\) 意义下的和两两不同的 \(k-1\) 元组，把任意 \(p_i\) 和它们逐个询问就能得到 \(p_i \bmod k\) 。
中国剩余定理
如果知道了 \(p_i\) 在模 \(3,5,7,8\) 意义下的值，根据中国剩余定理，可以知道其在模 \(3 \times 5 \times 7 \times 8 = 840\) 意义下的值，也就是真实值。
而 trick 4 和 trick 5 给出了每个模数求值的方法，但是需要一些已知数。trick 3 恰好给出了产生一些已知数的方法（事实上只需要 8 个）。综上，就可以使用较少的询问得到答案。
如果不用 trick 4 的话，直接用 trick 5 处理 8 这个模数，就要使用 trick 3 产生更多的已知数，容易导致询问数过大。
hdu6842 Battle for Wosneth2
Alice Bob 打架，两者生命值分别为 \(n, m\) ，命中率分别为 \(p, q\) ，从 Alice 开始轮流攻击对方，生命值先到 0 的一方败。求 Alice 胜率。
时间复杂度：\(O(n + m)\) 。
题解
一个朴素的 DP 是设 \(f_{n,m}\) 表示当前局面下的胜率，转移枚举下两次攻击的情况，可以得到 \(f_{n,m} = a f_{n,m-1} + b f_{n-1,m} + c f_{n-1,m-1}\) ，其中 \(a,b,c\) 是只与 \(p,q\) 有关的常数。
把这个 DP 放在二维平面上，就是从 \((n, m)\) 走到任意一个满足 \(x>0\) 的 \((x, 1)\) 。可以枚举 \(c\) 的步数 \(k\)，注意到 \(a\) 的步数和 \(c\) 的步数总和始终为 \(m-1\) ，那么就需要对所有 \(b\) 的步数算贡献。此时可以知道 \(b\) 的步数的上界是 \(n-1-k\) ，而每一个 \(b\) 的具体步数 \(i\) 的贡献是与 \(k\) 无关的，那么预处理个前缀和即可。
具体的，问题等价于求
\[(a+c) \sum_{k} \sum_{i=0}^{n-1-k} \binom{m-1}{k} \binom{m-1+i}{i} a^{m-1-k} b^i c^k\]
即
\[(a+c) \sum_{k} \binom{m-1}{k} a^{m-1-k} c^k \sum_{i=0}^{n-1-k} \binom{m-1+i}{i} b^i\]
后面的 \(\sum\) 里头的值与 \(k\) 无关，可以预处理。
uoj549 【UNR #4】序列妙妙值
给定长为 \(n\) 的值域 \([0, 2^v)\) 的整数序列，划分为恰好 \(k\) 段使得每段异或和的总和最小，求该最小值。
时间复杂度：\(O(n k 2^{v/2})\) 。
题解
一个朴素的 DP 是设 \(f_{i,j}\)
表示前 \(i\) 个分 \(j\) 段，然后暴力转移。另一个朴素的 DP 是设
\(f_{i,j,x}\) 表示前 \(i\) 个分 \(j\) 段最后一段为 \(x\) 然后 \(O(1)\) 转移。巧的是这两个 DP
都跟正解没啥关系。
将序列做个异或前缀和得到 \(\{a\}\) ，沿用第一个朴素 DP ，不过转移枚举分段点的位置是很难优化的，不妨考虑转移枚举分段点的 \(a\) 的值。于是转移的复杂度就从 \(O(n)\) 变成了 \(O(2^v)\) 。
考虑这个过程实际上是维护了一个 \(g_x\) 表示分段点的 \(a\) 值在 \(x\) 时候的转移最大值，转移事实上是求：
\[\max \{g_x + (x \oplus a_i)\}\]
而注意到更新 \(g\) 是 \(O(1)\) 的，直接把 \(g_{a_i}\) 和当前 DP 值取 max 即可。这个 DP 关键就在于这个 \(g\) ，它可以看做一个 \(O(2^v)\) 查询和 \(O(1)\) 修改的数据结构。然而修改次数和查询次数是几乎相等的，显然我们希望让两者的复杂度尽量平摊。
那么到这里思路就很显然了，每次查询只枚举前 \(v/2\) 位，对于后面 \(v/2\) 位查表，而每次修改只需暴力更新后 \(v/2\) 位对应的表即可。
uoj551 【UNR #4】校园闲逛
有 \(n\) 点 \(m\) 边的有向图，边权为 \(V\) 以内的正整数。\(q\) 次询问，每次询问从 \(x\) 到 \(y\) 的边权和恰为 \(z\) 的路径有多少（可以不是简单路径）。
时间复杂度：\(O(n^3 V + n^2 V \log V + m \log V + q)\) 。
题解
容易想到弄 \(n^2\) 条边，每条边是一个多项式，其 \(k\) 次项系数是原图该条边边权为 \(k\) 的数量。那么只要对于每个 \(x, y\) 求出从 \(x\) 到 \(y\) 的所有路径的多项式乘积的和 \(f_{x,y}\) ，询问的答案就是 \([x^z] f_{x,y}\) 。
倍增求这个多项式 ，也就是说每次在已知 \(f \bmod x^{k}\) 的基础上求出所有的 \(f \bmod x^{2k}\) 。
注意到倍增后增加的路径都是权值在 \([k, 2k)\) 内的路径，目标是统计这些新增的路径。
对于一条新增路径，称使得路径权值大于等于 \(k\) 的第一条边为关键边（比如对于 \(k=4\) ，路径 \(1+2+2+1\) ，第三条边为关键边），考虑 通过枚举关键边来统计对应的新增路径 。
那么一条新增路径可以按照三部分，一是关键边前面的部分，而是关键边本身，三是关键边后面的部分。注意到一三部分的权值都不会超过 \(k\) ，因此都可以在上一轮的 \(f\) （称为 \(g\) ）中表示出来。而对于边权在 \([k, 2k)\) 内的边，它们在路径中至多出现一次，且一定作为关键边。
那么一个简单的做法就呼之欲出了。先枚举一部分 \((x, y)\) 和二部分 \((y, z)\) 。设 \(h_{x,y}\) 表示 \((x, y)\) 上的关键边构成的多项式，\(t_{x,z} = \sum_y g_{x,y} \times h_{y,z}\) ，那么 \(t_{x,z}\) 的 \(d (d \in [k, 2k)\) 次项系数就是从 \(x\) 到 \(z\) 前两部分到 \(z\) 的权值为 \(d\) 的路径数。
然后把第三部分考虑进来，注意到对于 \(t\) 我们只关注它的 \(k\) 次项系数到 \(2k-1\) 次项系数，不妨设 \(h\) 表示 \(t\) 的后 \(k\) 项系数构成的多项式，那么直接枚举第三部分 \((x, y)\) ，设 \(s_{x,z} = \sum_y h_{x,y} \times g_{y,z}\) ，\(s\) 的前 \(k\) 项系数就是我们需要的。于是有
\[f_{x,y} \bmod x^{2k} = g_{x,y} + x^k (s_{x,y} \bmod x^k)\]
每次只需要对 \(O(n^2)\) 个多项式做 DFT/IDFT ，那个类似于 floyd 的 \(O(n^3)\) 转移都是可以线性点乘的。
agc001f Wide Swap
给定 \(1 ~ n\) 的排列 \(P\) 和参数 \(K\) ，每次可以进行如下操作：
- 选择两个下标 \(i, j\) 满足 \(1 \le i < j \le n \land j - i \ge K \land |P_i - P_j| = 1\) ，交换 \(P_i\) 和 \(P_j\) 。
求进行若干次操作后可以得到的字典序最小的排列。
时间复杂度：\(O(n \log)\) 。
题解
不妨设 \(Q\) 为 \(P\) 的逆，在 \(Q\) 上考虑这个问题，那么每次操作等价于：
- 选择下标 \(i\) 满足 \(1 \le i < n \land |Q_i - Q_{i+1}| \ge K\) ，交换 \(Q_i\) 和 \(Q_{i+1}\) 。
也就是交换相邻的差不小于 \(K\) 的两个位置，那么可以发现对于 \(i < j \land |Q_i - Q_j| < K\) ，\(Q_i\) 始终会在 \(Q_j\) 左边。也就是说如果把这样的关系连边 \(i -> j\) ，那么最终可以得到的排列 \(Q\) 一定是图的一个拓扑序。也可以知道图的拓扑序一定对应一个可以得到的排列 \(Q\) 。
目标是要最小化 \(P\) 的字典序，这是否等价于最小化 \(Q\) 的字典序呢？
字典拓扑原理
对于任意 DAG 的拓扑序 \(P\) 以及其逆 \(Q\) ，\(P\) 是字典序最大的当且仅当 \(Q\) 是字典序最大的。
记 \(\mathrm{rev}P\) 表示排列 \(P\) 的翻转。同样条件下，不难得到以下推论；
- \(P\) 是字典序最小的当且仅当 \(\mathrm{rev}Q\) 是字典序最大的。
- \(\mathrm{rev}P\) 是字典序最大的当且仅当 \(Q\) 是字典序最小的。
- \(\mathrm{rev}P\) 是字典序最小的当且仅当 \(\mathrm{rev}Q\) 是字典序最小的。
End
于是乎只需要最大化 \(\mathrm{rev}Q\) 的字典序，拓扑序的 \(\mathrm{rev}\) 就是图把边翻转后的拓扑序。
可是注意到直接连边的话，边数是 \(O(n^2)\) 的，但是由于对于这张图我们只关注其可能的拓扑序，许多边都是没有必要的。据此可以用线段树找到每个点必要的出边，细节略去。
keoj199 爱乐之城
对于正整数 \(x\) 定义
\[f(x) = \sum_{i=1}^x \sum_{j=1}^x [i \bot j] ij\]
\[g(x) = \sum_{i=1}^x \sum_{j=1}^x \mu (ij)\]
对于数集（严格定义，不允许重复元素） \(S\) 定义
\[h(S) = \sum_{T \subset S} g(\gcd T) \prod_{x \in T} f(x)\]
要求维护数集 \(S\) ，支持在线加入元素和查询 \(h(S)\) ，数的大小不超过 \(n\) 。
题解
考虑 \(f, g\) 的逆向差分，有：
\[\Delta f(x) = f(x) - f(x - 1) = 2 (\sum_{i=1}^x [i \bot x] ix) - [x = 1]\]
\[\Delta g(x) = g(x) - g(x - 1) = 2 (\sum_{i=1}^x \mu (ix)) - [x = 1]\]
设 \(f_0(x) = \sum_{i=1}^x [i \bot x] ix\) 以及 \(g_0(x) = \sum_{i=1}^x \mu (ix)\) ，这两个函数都是可以莫比乌斯反演预处理的，因为 \(\sum\) 内有值的条件都是 \([i \bot x]\) ，具体过程略去。通过预处理这两个函数就可以进一步得到 \(f, g\) 的所有取值。
然后考虑维护答案，简单的想法是对于每个 gcd 维护一个函数，然而这样问题仍然会很困难，这里需要一步转换，设 \(\delta\) 是 \(g\) 的狄利克雷卷积逆，那么有
\[h(S) = \sum_{T \subset S} (\sum_{d | \gcd T} \delta(d)) \prod_{x \in T} f(x)\]
整理得到
\[h(S) = \sum_{d=1}^n \delta(d) \sum_{T \subset S} (\prod_{x \in T} f(x) [d | x]) = \sum_{d=1}^n \delta(d) \sigma(d) \]
而对于每个 \(d\) 维护 \(\sigma(d)\) 是很简单的。
咕咕咕。
咕咕咕。