A. World Cup

首先注意到，我们把自己的队伍的能力值设成 $0$，把比自己强的队伍能力值设成 $1$，比自己弱的队伍能力值设成 $-1$，那么最后能达到的最优排名只和自己在所有的队伍中排名多少有关。

也就是只需要预处理出自己是 $32$ 支队伍中第 $k$ 名，那么最后的结果是多少即可。这个可以直接搜索即可，枚举每组有多少个 $1$ 和 $-1$，然后根据赛程安排模拟。也可以直接手玩。

时间复杂度为 $O(q)$。

B. Graph

首先条件等价于，对于每个数字 $d$，所有 $d$ 的倍数的点形成的导出子图一定是连通的。

• 必要性：考虑 $d$ 和它的所有倍数即可。
• 充分性：如果 $(u, v) = d$，从 $u$ 先走到 $d$，然后走到 $v$ 即可。

从大往小考虑每个 $d$，令 $m = \lfloor n/d \rfloor$，并且对于每条边 $u, v$ ，我们认为它是在考虑到最大公约数 $(u, v)$ 时候被加入的。考虑 $d$ 的倍数的点的导出子图。假设新的图 $G'$ 里面的标号为 $1, 2, \dots, m$ 的点，分别为原图里 $d, 2d, \dots, md$ 的点。

注意到根据之前连的边，$G'$ 里有一些点已经连通。

• 如果一个数是合数 $x = px'$，其中 $p$ 为 $x$ 的某个素因子，那么 $x$ 与 $p$ 连通。
• 如果一个数是素数 $p$ 且不超过 $m/2$，那么 $p \to 2p \to 2$，也就是可以通过 $2p$ 与 $2$ 连通。
• 如果一个数是素数 $p$ 且超过 $m/2$，那么在这个图 $G'$ 中，它不会和其他任何点连通。

也就是 $G'$ 中的连通块为 $1$，所有大于 $m/2$ 的素数，以及其他点。因为需要连的边最少，那么我们会将这些点连一个生成树。方案数可以通过类似完全图生成树的方法计算，即：

• 如果有 $k$ 个连通块，大小分别为 $x_1, x_2, \dots, x_k$，那么生成树的个数为 $\prod x_k (\sum x_k)^{k-2}$。

如果对于 $m$，它的方案数为 $f_m$，那么答案为 $\prod_{i=1}^n f_{\lfloor n/i \rfloor}$，可以用数论分块的方法解决。

我们要注意到计算 $f_m$ 的时候，还需要统计大于 $m/2$ 并且不超过 $m$ 的素数个数，这一部分需要用到一些素数筛相关的方法，大家可以参考 OIWiki 或者 Atcoder。

前面筛素数的时间复杂度为 $O(n^{3/4} / \log n)$，所以总的时间复杂度就是这个。

C. Permutation Counting 4

问题等价于 $(l_i-1, r_i)$ 这个图是不是棵树。

从线性代数的角度考虑，假设有个矩阵 $A_{i, j} = [j \in [l_i, r_i]]$，等价于要求 $\text{per}(A) \bmod 2$，而 $\text{per}(A) \equiv \text{det} (A) \pmod 2$，那么考虑这个矩阵的行列式即可。

对于这个矩阵，我们可以在左边和上面补上一行一列，并且除了左上角的位置是 $1$，其他位置都是 $0$。然后依次从前往后，执行每一列减去后一列的操作（类似差分）。那么操作完之后，对于每一行 $1\leq i \leq n$，有 $A_{i, l_i-1} = -1, A_{i, r_i} = 1$，其他位置都是 $0$。

那么如果 $(l_i-1, r_i)$ 这些边成环，那么把这些边对应的行拿出来，一定是线性相关，也就是行列式为 $0$。

否则可以根据行列式的定义展开，那么恰好会有一项是非零的，也就是行列式为 $\pm 1$，即模 $2$ 的余数为 $1$。

时间复杂度为 $O(n)$。

D. Protection War

我们把所有极长的的非零区间当成一段。首先可以证明，如果每一轮模拟时间复杂度是 $O(段数)$，那么总的时间复杂度为 $O(n + q\sqrt{n})$。

证明可以考虑势能分析，长度前 $T$ 大的段当成长段，剩下的当成短段。势能 $S$ 看成所有短段的长度的和，短段长度不超过 $n/T$。

• 一号操作可能会分裂一段，那么 $S$ 会增加不超过 $n/T$。
• 二号操作相当于合并若干段，如果合并之后的段为长段，那么 $S$ 不会增加，否则因为长度不会超过 $n/T$，$S$ 的增加量也不超过 $n/T$。
• 最后的修改操作，对于这些短段，如果操作了，那么对应的长度会减小，这部分会摊在势能中。

所以每次操作，势能的增量不超过 $n/T$，对于长段操作的代价可以额外计算，不超过 $T$，当 $T=\sqrt{n}$ 时，可以证明这部分时间复杂度不超过 $O(n+q\sqrt{n})$。

那么我们可以每一轮用 $O(段数)$ 的代价直接模拟，需要支持区间加，区间求和，单点修改等操作。如果直接使用线段树等数据结构，那么时间复杂度为 $O((n+q\sqrt{n})\log n)$，不一定能通过。

注意到区间求和操作的次数是 $O(q)$ 的，而区间加和单点修改操作的次数是 $O(n + q\sqrt{n})$ 的，那么可以使用根号数据结构把修改部分做到 $O(1)$，查询部分做到 $O(\sqrt{n})$ 即可。

这里还有个细节问题是每次对每段做把最后一个数改为 $0$ 的时候，需要 $O(1)$ 查询，也就是不能直接用数据结构查询这个数的值。我的做法是维护了整个序列的差分，以及每一段最后一个数的值，那么可以通过查分快速算出前一个数的值。

时间复杂度为 $O(n+q\sqrt{n})$。

E. Random Dungeon

首先把所有数从大到小排序。我们的策略一定是对于第一轮，我们会设定一个阈值 $t_1$，如果抽到的牌是全局前 $t_1$ 大，那么直接结束，否则继续抽取。对于第二轮，我们继续会设定一个阈值 $t_2$，后续轮次依次类推。这些阈值的设定与抽到了什么牌无关，并且是单调不增的，也就是 $t_1 \geq t_2 \geq \dots \geq t_n$。

一个比较符合直觉的的理解为：如果抽了 $k$ 轮还没结束，意味着前面抽的牌的排名都是大于 $t_k$。从后面的轮次来看，再抽到这些牌也会继续，所以都是垃圾牌，也就意味着后面的策略和具体抽了哪些牌无关。并且到后面的轮次还没结束，意味着我们前面扔掉了一些垃圾牌，那么剩下的牌会更偏向于好牌，所以阈值会相应的提高。

严谨一点的证明再说。

这样可以得到一个 $O(n^2)$ 的 $dp$，即令 $dp[i][j]$ 表示还剩 $i$ 张牌，当前极长没有被选中的前缀为 $j$ 的最大期望收益。那么有转移

$$dp[i][j] = \frac{i-j}{i} \times dp[i-1][j] + \frac{1}{i} \sum_{k=1}^j \max(dp[i-1][k-1], a_k) - c $$

含义为如果选中的不是前 $j$ 个，之前已经扔掉了 $j+1$，那么这个一定会扔掉，否则考虑扔掉继续做或者直接选择 $a_k$。

对着这个式子直接优化是困难的。继续考虑组合意义，根据前面的假设，在最优策略下，如果剩下 $i$ 张牌，那么这些牌一定是一个前缀加上垃圾牌，那么这个时候的最大期望收益和前面抽了什么牌没有关系，所以可以等效为剩下前 $i$ 大的。

令 $dp[i]$ 表示还剩前 $i$ 大的牌的最大期望。考虑当前的决策为如果抽到前 $j$ 大的就停止，否则继续抽。那么有转移

$$dp[i] = \max_{j=1}^i \frac{\sum_{k=1}^j a_k + dp[i-1] \times (i - j)}{i} - c$$

也就是选 $a_j\geq dp[i-1]$ 的最大位置即可，这也是倒数第 $i$ 轮对应的阈值。

dp 可以用单调性做到 $O(n)$。

F. Make Max

首先注意到，如果操作的时候选了大于两个数，那么把它变成从最大值开始，每次修改相邻的数，这样一定不劣，也就是每次操作会选择相邻两个数。

其次注意到，如果一个数变成了全局最大值，那么就无法继续操作，所以可以把保留全局最大值，先递归左右两边，然后最后操作全局最大值。

我们可以通过建笛卡尔树来模拟这个过程，每个数的操作次数也就是这个数到根的路径上不同的数字个数。

时间复杂度为 $O(n)$。

G. The Median of the Median of the Median

首先可以二分，判断答案是不是大于等于 $X$，那么我们可以把大于等于 $X$ 的数字当成 $1$，小于 $X$ 的数字当成 $-1$。那么一个集合的中位数大于等于 $X$ 当且仅当它们和大于 $0$。

所以题目中的操作都可以用前缀和求每个集合的和，在 $O(n^2)$ 解决。时间复杂度为 $O(n^2 \log n)$。

H. Rainbow Bracket Sequence

问题相当于 $n$ 个左括号，你需要分配给这些位置，并且要求：

• 第 $i$ 种颜色个数不小于 $l_i$。
• 前 $2i - 1$ 个位置左括号个数不小于 $i$。

使用上下界最大费用流解决。建立一个源点 $S$，对于每个颜色建立一个点 $b_i$，对于整个序列建立一拍点 $a_1, \dots, a_{2n+1}, $。我们连这些边（下面括号里三个值分别表示下界，上界，和费用）：

• $S$ 向 $b_i$ 连 $(l_i, \infty, 0)$ 的边，表示每种颜色的下界。
• $b_{c_i}$ 向 $a_i$ 连 $(0, 1, v_i)$ 的边，表示如果这个位置放左括号，那么需要 $v_i$ 的费用。
• $a_i$ 向 $a_{i+1}$ 连 $(\lceil i/2\rceil, n, 0)$ 的边，表示前面至少需要这么多个左括号。
• $a_{2n+1}$ 向 $S$ 连 $(n, n, 0)$ 的边，表示一共需要恰好 $n$ 个左括号。

跑最大费用流即可。

时间复杂度为 $O(\text{maxcostflow}(n, n))$。

I. Boxes

首先可以发现，如果所有的点集形成的凸包都是嵌套的，那么一定更优。

证明 by 修噶：考虑最外层的若干个凸包，假设多于一个，则使用这些凸包的凸包代替这些凸包，显然点数减少，体积增大，且不影响内部方案。所以一层层剥凸包是最优的。

那么你需要做的是不断重复，先求出这个点集的凸包，然后删除，接着继续执行这个操作，直到剩下的点不超过 $3$ 为止。

假设一层凸包上会有 $d$ 个点，那么一些常见的三维凸包算法（比如卷包裹）时间复杂度其实是 $O(nd)$ 的。那么你只需要暴力做这个过程即可，这些凸包上点数一共是不超过 $n$ 的，也就是时间复杂度为 $O(n^2)$。

注意：这个题答案可能会超过 long long 的数据类型。

J. Rivals

好像是生成函数爆算一下，没意思的，别做了。

见修噶题解

K. AC Automation Chicken

如果知道了哪个点为根，那么 Trie 上的边会从根往外连，而 fail 边会朝根连，那么从根节点出发 BFS 就可以确定哪些边是 Trie 上的边。那么可以相对简单得判断和构造，具体细节见下。

考虑根节点具有什么性质。假设 $u$ 为根节点，$v$ 为它的一个儿子节点，那么图里面会有 $(u, v)$ 和 $(v, u)$ 这两条边，即分别为树边和对应的 fail 边。下文把 $(u, v)$ 和 $(v, u)$都存在的边叫做双向边。

对于一条双向边 $(u, v)$，如果这两个点都不为根节点，那么根据 AC 自动机的性质可以得到这个节点对应的字符串包含的字符一定是相同的。假设路径为 $r \to v_1 \to \dots \to v_k$，那么对应的 fail 边为 $v_k \to v_{k-1} \to \dots \to v_1 \to r$。所以一个合法的 AC 自动机的双向边会形成一个类似菊花图的结构，从根节点出发，往外若干条链。

如果这个菊花图中存在一个大于等于三度的点，那么这个点一定是根节点，否则会形成一条链。对于一条链，每个点都可能是根节点，比如字符串 aaa, bbb 和字符串 aaaaaa 形成的 AC 自动机是同构的。

首先特判一下，整个图是一条链，那么任何一个点作为根节点都是合法的。否则假设根节点 $r$ 左右两边的点分别是 $u, v$（如果左右两边的点不存在也同理），即这三个点形成 $u \leftrightarrow r \leftrightarrow v$ 的结构，不妨设 $u, v$ 对应的字符为 $1, 2$。那么考虑 $u$ 这个子树的最浅的分叉，也就是不在双向边的链上的点。

• 如果对应的字符为 $1$，那么还是双向边，矛盾。
• 如果对应的字符为 $2$，因为是最浅，那么会指向 $v$。
• 如果对应的字符不为 $1, 2$，因为最浅，会指向 $r$。

也就是如果指到了链上，那么根节点一定是这个点本身，或者这个点在链上的邻居节点。同样的，对于链上任意一点 $x$，指向了一个不在链上的点 $y$ ，$y$ 指向了一个在链上的点 $z$。可以通过类似的分析得到根节点一定是 $z$ 或者 $z$ 的邻居，那么只需要检查 $O(1)$ 个点能否成为根即可。

判断一个点为根是否可行，首先根据上文说的，可以通过 BFS 区分树边和 fail 边。其次，对于每个点，如果它的 fail 边指向根节点，那么可以给它一个新的字符，否则与 fail 边指向的点对应的字符相同。最后需要判断它的 fail 边是不是真的指向那个点，这个可以通过对这个 Trie 建一遍 AC 自动机判断。但是由于字符集大小为 $O(n)$，所以建立 AC 自动机需要可持久化线段树或者其他方法辅助，并不是特别方便。一个简便方法是假设这个点字符等于 $c$，那么等价于判断沿着父亲的 fail 边往上跳，第一个等于 $c$ 的儿子等于这个点的 fail。那么可以通过在 fail 树上 dfs，然后对每个字符 $c$ 用一个栈记录一下上一个等于 $c$ 的儿子在什么地方。这样就可以做到 $O(n)$ 判断。

这个题还有很多细节，包括但不限于：

• 没有重边自环。
• Fail 边需要指向深度更浅的点。
• 图需要连通。
• Trie 里每个节点的儿子字符集需要不同。
• 等等

如果用 Hash 表之类的方法找双向边以及判断重复，那么这个题可以做到 $O(n)$ 的时间复杂度。

L. Bull Farm

考虑对于每个操作，我们的空格会怎么移动。

• 如果一个操作不同的位置不超过 $n-2$，那么一定会有两个元素到同一个地方，那么是不合法的，可以直接忽略。
• 如果不同的位置等于 $n$，那么也就是形成若干个环，即 $i \to p_i$，有因为它是个环，也就是操作若干次能回到原点，所以可以把这些边看成双向边。
• 如果不同的位置等于 $n-1$，假设 $x_1, x_2$ 是指向同一个位置的两个数，$y$ 是缺失的位置，那么等价于 $x_1 \to y, x_2 \to y$。

每个查询等价于用不超过前 $k$ 轮的边，$a$ 能否到达 $b$。

对于无向边，我们只需要在从前往后加入的过程中，保留会改变连通性的边即可，那么不会超过 $O(n)$ 条。有向边一共 $O(l)$ 条，也就是图里面的边，只需要保留 $O(n + l)$ 条。

对于每条边的边权设成加入的时间，那么问题变成了需要求两个点之间的权值最大边最小的路径。这个可以对于每个起点，用类似 Dijkstra 的做法解决，因为值域比较小，所以可以用若干个桶的做法做到线性。也可以按时间从小到大依次加入边，然后从加入的这条边开始 BFS，求出新的可达的点。

这两种做法都是线性的，总的时间复杂度为 $O(n(n+l) + q)$。

M. Find the Easiest Problem

按照题意模拟即可。