A. Azaleap Garden
首先找到 \(A = \max a\)，\(b_i > A\) 的对都不可能被打败。
找到一个 \(a_i = A\) 的对 \((a_i, b_i)\)，现在只需要考虑该对可否被 \(b_j > A\) 的对打败，如果可以答案就是 \(b_j > A\) 的对的数量，否则答案要再加 \(1\)。
如果 \(b_i > A\) 则答案就是前者，只考虑 \(b_i\le A\) 的情况。
\(b_j > A\) 的对肯定会选择 \(\max a_j\) 来打败，所以只需要找到打败的关系链，使得一开始被打败的是 \(i\)，最小化未被打败的对的 \(b_k\)，如果 \(\max a_j > b_*\) 则可以让 \(i\) 先把不在这条链的对打败，然后按照链的顺序打败，最后打败 \(k\) 这个对。
考虑一个传递关系，对于 \(b_i \ge b_j\)，当 \(a_j \ge b_i\) 时 \(i\) 能被 \(j\) 打败，刻画到数轴上相当于是 \([b_j, a_j], [b_i, a_i]\) 有交。于是对于 \(b_j < a_j\) 的对在数轴上覆盖 \((b_j, a_j]\) 这块区域，从 \(A\) 开始向左走走到的第一个没有被覆盖的值就是 \(\min b_k\)。
一颗线段树维护 \(b_j\) 为下标的 \(a_j\) 的最大值，一颗线段树维护数轴覆盖即可。
时间复杂度 \(\mathcal{O}((n + q)\log n)\)。
submission。
B. Beautiful Dangos
首先求解最小区间容易发现固定 \(r\) 时最大 \(l\) 是不减的，于是可以双指针。
主要的问题是如何判断一个区间 \([l, r]\) 是否存在合法的重排方案。
如果不考虑 \(l - 1, r + 1\) 位置的值，那么合法条件很简单：\(\max(cnt_C, cnt_W, cnt_P)\le \lfloor\frac{r - l + 1}{2}\rfloor\)。
但现在的问题是 \(l - 1, r + 1\) 会限制边界的值的位置，可能导致不合法，感受一下这说明这是在加入边界元素后才不合法的，只需要把 \([l, r], [l - 1, r], [l, r + 1], [l - 1, r + 1]\) 这 \(4\) 个区间的合法性判一下就好了。
构造也是类似的，只需要从前往后依次确定每一个位置的值并判断之后是否能填即可。
时间复杂度 \(\mathcal{O}(n)\)。
submission。
C. Catch the Monster
首先一条链是合法的，可以从链的一端不断往另一端走，于是考虑在链上再加什么结构会是合法的。
手玩一下会发现如果链上的点非链上的子树都是单点是可以操作的，可以在链上走到一个点时走到相邻的单点再走回来，此时排除了单点的可能性且没有新增某个点的可能性。
于是合法条件可以刻画为对于任意点 \(u\)，\(\sum\limits_{v\in e_u} [|e_v|\ge 2] \le 2\)（这里 \(e_u\) 指的是只保留 \([l, r]\) 中的点的导出子图的的边）。
因为 \(r\) 增大的时候最小的合法的 \(l\) 是不减的，所以可以双指针维护每个 \(r\) 最大的合法 \(l\)。
因为双指针保证了每个点至多被加入一次删除一次，只需要在更新 \(\sum\limits_{v\in e_u} [|e_v|\ge 2]\) 时以 \(v\) 去更新 \(u\)，且只更新 \(u\in e_v\) 的 \(u\) 即可。
时间复杂度 \(\mathcal{O}(n\log n + q)\)。
submission。
D. Directed Acyclic Graph
先不考虑都要被 \(1\) 可达这个条件，考虑怎么构造出 \(16000\) 种方案。
此时先把求交转为补集求并，这样就有了一个显然的构造：构造出两排点 \(a_i, b_i\)，让 \(a_i\) 可达 \(b_j(j\not= i)\)，这样选中 \(a\) 的集合 \(S\) 可达的点集合就是编号不在 \(S\) 中的 \(b\) 点。这样就可以用 \(\mathcal{O}(w^2)\) 条边构造出 \(2^w\) 种方案。
这显然还有优化的办法，直接让 \(a_i\) 与每个 \(b_j(j\not= i)\) 都连边显然用的边数还是太多了，可以建一个前缀点和后缀点 \(pre_i, suf_i\)。具体来说，连边 \(pre_i\to pre_{i - 1}, pre_i\to b_i\)，\(suf_i\to suf_{i + 1}, suf_i\to b_i\)，这样 \(a_i\) 的连边就可以变为 \(a_i\to pre_{i - 1}, a_i\to suf_{i + 1}\)。这样就可以用 \(4w - \mathcal{O}(1)\) 条边构造出 \(2^w\) 种集合。
继续优化，考虑能不能去把底数的 \(2\) 换成更大的数，此时底数是 \(2\) 是因为对于 \(b_i\) 只有能到和不能到这两种情况。于是考虑扩展一下，考虑把 \(a, b\) 改成 \(h\) 行，\(a_{i, j}\) 不能到达的点集为 \(b_{i, k}(k\le j)\)，这样对于 \(j\) 列就有 \(h + 1\) 种可能了。
按照如下构造：\(b_{i, j}\to b_{i + 1, j}\)，\(pre_{j}\to pre_{j - 1}, b_{1, j}\)，\(suf_{j}\to suf_{j + 1}, b_{1, j}\)，\(a_{h, j}\to pre_{j - 1}, suf_{j + 1}\)，\(a_{i, j}\to a_{i + 1, j}, b_{i + 1, j}(i < h)\)。其中 \(pre_n, suf_1\) 可以省略掉。
再考虑上 \(1\) 要可达，发现这个 DAG 中大部分点都已经有入边了，所以只需要给没有入边的点加上 \(1\) 到该点的边即可，这样算下来额外的边数只需要 \((h + 2)w - 6\) 条边（一共需要 \((3h + 3)w - 8\) 条边，有 \((2h + 1)w - 2\) 个点已经有入边了，相减就是额外的边数）。
因为额外边数有 \(m - (n - 1) = 29\) 条，可以令 \(h = 3, w = 7\)，此时恰好用完了 \(29\) 条额外边，且能构造出 \(4^7 + \mathcal{O}(1)\) 种方案。
submission。
如果忽略掉 \(6\) 的常数，\(f(x) = (x + 1)^{1 / (x + 2)}\) 在整数时的最大值确实是在 \(x = 3\) 时取到的，不过这个构造能否用来逼近小数的 \(x\) 呢？
我还尝试了一些构造，例如当底数为 \(4, 8\) 时用二进制来表示，效果都不理想，因为要构造出二进制也需要每个 \(a_{s, i}\) 至少连出两条边，且此时会有更多的 \(s\) 是无入边的，多过了 \(b\) 少掉的点数。
E. Epilogue of Happiness
以下认为 \(n, m, q\) 同阶。
考虑重链剖分（这里算子树大小时需要把子树内的 \(o_i\) 和询问一起算上），如果在一条长度为 \(L\) 的链上能以 \(\mathcal{O}(L\sqrt{L})\) 的复杂度解决链上的所有询问，那么最终的复杂度其实就是 \(\mathcal{O}(n\sqrt n)\)，因为对于一个点所经过的所有重链 \(u_1, u_2, \cdots, u_k\)，复杂度为 \(\mathcal{O}(\sum\limits_{i = 1}^k \sqrt{sz_{u_i}})\)，因为 \(2sz_{u_i}\le sz_{u_{i + 1}}\)，所以复杂度 \(\le \mathcal{O}(\sum\limits_{i = 0}^{k - 1}\sqrt{n / 2^i}) = \mathcal{O}(\sqrt{n})\)。
现在就只考虑对长度为 \(L\) 的一条链查询了。
考虑一个好优化的暴力，对于询问 \((l, r, u)\)，从 \(u\) 开始往根走，维护值 \(x\) 表示 \(u\) 往下编号在 \([l, r]\) 的 \(o_i\) 数量，在 \(u\) 处初始化后，每次向上爬至点 \(v\) 时 \(x\) 只需要异或上点 \(v\) 上编号在 \([l, r]\) 的 \(o_i\) 的数量即可，若 \(x = 1\) 则加上该点点权。
然后考虑按 \(B\) 分块（这里每个点的大小依旧要算上 \(o_i\) 和询问），把 \(o_i\) 和询问的 \((l, r)\) 都缩小到 \(\mathcal{O}(L)\) 级别，自底向上遍历，贡献分为 \(3\) 种：
-
到 \(u\) 时询问刚出现，需要初始化 \(x\)。在自底向上的过程用树状数组维护一下 \(u\) 及 \(u\) 之下出现过的 \(o_i\)，可以 \(\mathcal{O}(\log L)\) 加入一个点，\(\mathcal{O}(\log L)\) 查询区间异或值。
-
块内点 \(u\) 对块内点 \(v\) 的询问（\(u\) 在 \(v\) 上方）。因为保证了块大小至多为 \(B\)，所以可以直接暴力枚举 \(u\) 处的 \(o_i\) 和 \(v\) 处的询问并更新 \(x\) 的值，然后更新 \(v\) 询问的答案。复杂度 \(\mathcal{O}(B^2)\)。
-
块 \([u, v]\) 对块外询问 \((l, r, x)\) 的贡献（询问所在的点已经不重要了，在该块下方即可）。
考虑不同的 \([l, r]\) 会影响到其的 \([u, v]\) 中的 \(o_i\) 的集合，如果 \(l = 1\)，则显然不同的情况只会有 \(\mathcal{O}(B)\) 种，若 \(l \not = 1\)，可以看作是 \([1, l), [1, r]\) 两个集合的差，所以也只会有 \(\mathcal{O}(B^2)\) 种。
于是考虑等价类分治，每次找到 \([u, v]\) 中点 \(w\)，递归得到 \([u, w], (w, v]\) 中对 \((l, r)\) 的贡献，然后再合并出 \([u, v]\) 的贡献（其中 \(l, r\) 都只需要考虑出现在区间中的 \(o_i\) 的值）。这样复杂度是 \(T(len) = 2T(len / 2) + len^2\)，是 \(\mathcal{O}(B^2)\) 的。得到等价类后枚举块外询问 \((l, r, x)\) 就可以 \(\mathcal{O}(1)\) 得到 \(x\) 和答案的变化了，这部分的复杂度是 \(\mathcal{O}(L)\) 的。
特殊处理一个点大小 \(> B\) 的情况，这个时候对块外贡献只需要 \(\mathcal{O}(L)\) 预处理一下前缀 \(o_i\) 出现次数奇偶，就也可以 \(\mathcal{O}(L)\) 处理了。
总复杂度就为 \(\mathcal{O}(L / B \times (B^2 + L)) = \mathcal{O}(LB + L^2 / B)\)，取 \(B = \mathcal{O}(\sqrt{L})\)，复杂度即为 \(\mathcal{O}(L\sqrt L)\)。
总复杂度为 \(\mathcal{O}(n\sqrt n + n \log^2 n)\)（\(\log^2\) 的来源是每条链的离散化和树状数组）。
submission。
F. Follow the Penguins
类似 dij 的想法，维护每个 \(i\to t_i\) 的最小相遇时间。
相遇之后因为 \(i\) 固定，可以重新计算 \(t_j = i\) 的 \(j\to i\) 的相遇时间并更新。
时间复杂度 \(\mathcal{O}(n\log n)\)。
submission。
G. Grand Voting
手玩一下会发现最大化 \(s\) 按照 \(a\) 从小到大排序，最小化 \(s\) 按照 \(a\) 从小到大排序即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
submission。
I. Imagined Holly
有一个想法是如果存在 \(A_{u, v}\oplus A_{u, w}\oplus A_{v, w} = w\) 则 \(w\) 会在 \((u, v)\) 路径之间。
会发现这是对的，因为 \(A_{u, v} \oplus A_{u, w}\oplus A_{v, w}\) 放在树上考虑得到的就是使三个点分割在不同子树（认为自己也是一个单独的子树）的根。
以 \(1\) 为根，令 \(u = 1\) 则可以得到所有 \((v, w)\) 的祖先关系，也就知道了每个点的祖先，那就知道了深度，而每个点的父亲恰好是深度比自己少 \(1\) 的祖先，于是可以得到整棵树。
时间复杂度 \(\mathcal{O}(n^2)\)。
submission。
January's Color
发现可能的过程一定是凑出 \(x\) 的父亲的一个儿子，然后与 \(x\) 合并成 \(x\) 的父亲，一直不断往上的过程。
所以当 \(y\) 是 \(x\) 祖先是有解。
求答案可以首先求出 \(f_u\) 表示从 \(u\) 的子树凑出这个点 \(u\) 的最小代价，转移有两种，一种是直接买 \(u\)，否则是凑出两个儿子合并，维护 \(f_v(v\in son_u)\) 的最小值次小值即可。
然后就可以对 \(u\) 得到 \(g_u\) 表示 \(u\) 父亲的儿子中除 \(u\) 的 \(f_v\) 最小值，依然可以通过维护 \(f\) 最小值次小值得到。
答案即为 \(x\to y\) 链上 \(g\) 值的和（含 \(x\) 不含 \(y\)），对 \(g\) 做一个树上前缀和即可。
时间复杂度 \(\mathcal{O}(n)\)。
submission。
K. Killing Bits
首先判掉 \(a, b\) 相同的情况。
否则至少要进行一次操作，所以应当满足 \(b_i\subseteq a_i\)。
其次选择的排列 \(p_i\) 应当满足 \(b_i\subseteq p_i\)。
判定是否存在合法的 \(p_i\) 需要网络流，考虑如下连边：
- \((S, b_i, 1)\)。
- \((s, s \cup \{x\}, \infty)\)
- \((s, T, 1)\)。
若满流则说明存在合法的 \(p_i\)。
但只找到一个合法的 \(p_i\) 并不能满足 \(a_i \cap p_i = b_i\)，不过考虑 \(p_j = b_i\) 的 \(j\)，\(a_j\cap p_j = a_j\cap b_i\subseteq b_i\subseteq p_i\)，所以交换 \(p_i, p_j\) 后 \(p_i = b_i\) 且 \(a_j\) 不会有任何变化，于是一定存在合法解。
能跑过。
submission。
L. Let's Make a Convex!
合法条件即为 \(\sum\limits_{x\in S} - \max\limits_{x\in S} > \max\limits_{x\in S}\)。
对 \(a\) 排序后，枚举 \(\max\) 的值 \(a_i\)，贪心的考虑，个数固定时肯定是贪心的选 \(< a_i\) 的最大的数，因为这样既能最大化答案也能尽可能满足条件。
于是枚举 \(i\) 后二分出最大的 \(j\) 满足 \(\sum\limits_{k = j}^{i - 1} a_k > a_i\)，若个数 \(\in [j - i + 1, j]\) 则可以选 \(i\) 为右端点。
而个数确定时因为确定了选择的是一段区间，所以最大值一定是在最大的右端点取到。于是对于上文求出的 \((i, j)\) 假定其能贡献到选取个数 \(\in [j - i + 1, n]\) 的所有值（只需要把无解的判定改一下），就相当于是一个前缀 \(\max\) 了。
时间复杂度 \(\mathcal{O}(n\log n)\)。
submission。
M. Mystique as Iris
因为最后要消成空序列，一个想法是最后消成 \(1, 1\) 然后变成空序列。
于是会发现若存在 \(n - 1\) 则一定可以消空，因为可以把旁边的值分别消完。于是尝试把这个结论扩展到 \(< n - 1\) 的值。
实际上 \(1\) 是不太行的（看起来就很特殊），但是能发现 \([2, n - 1]\) 都是可以的，尝试用归纳法证明这个结论：
- \(n = 3\) 时显然成立。
- 假设 \(2\sim n - 1\) 都成立，尝试证明 \(n\)：
- 若存在 \(n - 1\) 则按上述方法构造即可。
- 若存在 \([2, n - 3]\) 的值，考虑令 \(n\gets n - 2\) 递归构造。按照这个值分成两个部分，如果一个部分存在相邻的 \(1, x\) 则可以 \(n\gets n - 2\)，否则每一侧要么为空要么为单独的 \(1\) 要么全 \(> 1\)，因为根据限制有 \(n\ge 5\)，所以至少存在一侧是 \(\ge 3\) 个非 \(1\) 的数，任选 \(3\) 个连续的数 \(x, y, z\)，操作 \(x\gets 0, y\gets y - 1\)，\(y\gets 0, z\gets z - 1\) 即可。
- 若存在 \(n - 2\)，考虑若 \(n - 2 \not = 2\) 时，只需要让 \(n - 2\) 这个值 \(-1\) 并且选一个相邻的值变为 \(0\) 即可，否则 \(n = 4\)，可以依次验证。
接下来就只需要考虑只有 \(1\) 或者 \(\ge n\) 的情况了。因为 \(\ge n\) 的值显然不可能通过 \(-1\) 变为 \(0\)，所以可以视为 \(+\infty\)。
画一下可能的变化：\([1, 1]\to \varnothing, [1, +\infty] \to \varnothing / [+\infty], [+infty, +\infty]\to [+\infty]\)。贪心的考虑，一定是先把相邻的 \(+\infty\) 都合并了，此时只有 \(+\infty, 1, +\infty, 1, +\infty\) 的情况会无解，也就是任意 \(1\) 之间（包括开头的 \(1\) 的前面和末尾的 \(1\) 的后面）都有 \(+\infty\) 时无解。
于是可以写个线性 dp，\(f_{i, 0/1}\) 表示当前值是 \(1/+\infty\) 的方案数。
时间复杂度 \(\mathcal{O}(n)\)。
submission。