题解 - Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)

A

考虑存在 $a_i=100$ 的情况，那么对于所有的 $0\le k< 100n$（其中 $k=100n$ 的情况是平凡的）总可以通过令 $x_i=k\bmod 100$，剩下随便选 $\lfloor k/100\rfloor$ 个 $j\neq i$，令 $x_j=a_j$，就是一个解。

如果不存在 $a_i=100$ 的情况，那么 $k=1$ 就凑不出来。

复杂度 $O(n)$。

B

由于允许操作的区间长度是奇数，不难看出奇数位置的元素只能在奇数位置之间流动，偶数同理。

并且，如果 $p\equiv q\pmod 2$，我们总可以通过一次交换把 $p,q$ 互换。

那么我们只需关心 $x_i$ 的奇偶性。令 $s_0$ 为子序列 $a_2,a_4,a_6,\dots$，$s_1$ 为子序列 $a_1,a_3,a_5,\dots$。

令 $t_i=x_i\bmod 2$，那么每一次操作我们必须在 $s_{t_i}$ 中标记一个元素，记答案初始为所有元素之和。

1. 如果 $s_{t_i}$ 的元素都没有被标记过，显然我们会标记最大的元素，令答案减去这个元素；
2. 如果 $s_{t_i}$ 存在被标记过的元素，那么如果存在没被标记过的正整数，就标记最大的正整数，这样答案减去的最多；否则任意标记一个已经被标记过的元素，答案保持不变。

复杂度主要在于排序，为 $O(n\log n)$。

C

首先不难看出这是一个 $dp$，关键在于我们不知道所有子区间的中位数是谁。

假设知道这个中位数是 $x$，那么设 $dp_i$ 表示 $i$ 结尾的所有合法划分中，最多的子区间个数，转移为 $dp_i=\max_{0\le j<i}\{dp_j+1\}$，其中 $a_{j+1}\sim a_i$ 的中位数是 $x$，并且 $i-j$ 为奇数。

给定的 $n$ 总是奇数，而这个 $dp$ 似乎并不依赖于 $n$ 的奇偶性，这就意味着一定存在某种性质。

假设每一个子区间的中位数都是 $x$，由于子区间的长度为奇数，子区间的长度之和 $n$ 也为奇数，那么一定有奇数个子区间。

既然一共有奇数个子区间，那么这些子区间并起来的中位数就一定等于 $x$，这个结论简单画图即可得出。

也就是说 $x$ 是可以直接求出来的，那么复杂度就是 $dp$ 转移的复杂度，为 $O(n^2)$。

注意，这个转移并不一定是求出 $a_{j+1}\sim a_i$ 的中位数，因为动态求中位数一般来讲会用对顶堆，复杂度会多一个 $\log$；而这里我们是判断中位数是否为 $x$，只需要记一下比 $x$ 大和比 $x$ 小的元素个数，然后它们都 $\le (i-j-1)/2$ 就是中位数为 $x$ 的充要条件。

D

令 $S_i=\sum_{k=i}^n a_k$，那么一个逆序对 $(i,j)$ 的贡献就是 $S_i-S_j$。

对于每一个 $p_i$，我们都希望所有 $j>i$ 且 $S_i-S_j>0$ 的 $j$ 都满足 $p_i>p_j$；所有 $j>i$ 且 $S_i-S_j< 0$ 的 $j$ 都满足 $p_i<p_j$。

如果能做到这一点，显然此时 $\sum_{i<j,p_i>p_j}S_i-S_j$ 就会取到最大值，因为每一个位置 $i$ 的 $S_i$ 是固定的。

事实上也确实可以做到，只需要令 $S_i$ 和 $p_i$ 的相对大小保持一致即可，也就是说，我们给 $(S_i,i)$ 这个二元组按照字典序排序，然后按照排序后的位置从 $1\sim n$ 给 $p_{i}$ 赋值即可。

这样的话，每一个位置 $i$，对于 $j>i$，总是满足 $S_j<S_i$ 时有 $p_j<p_i$；$S_j>S_i$ 时有 $p_j>p_i$。

复杂度 $O(n\log n)$。

E

没想到这个交互我能做出来，下面令 $I(x)$ 表示询问 I x，$Q(x)$ 表示询问 Q x。

由于 $c\neq 0$，那么这三种操作中最特殊的 $x$ 必然是 $0$，因为 $k=1$ 时 $f(0)=0$，$k\neq 1$ 时 $f(0)=c$。

因此第一步我们令 $a=0$，然后询问 $I(0)$ 区分出 $k=1$ 还是 $k=2,3$。

如果 $k=1$，此时 $S=\{0\}$，我们只需要询问 $I(2^0),I(2^1),\dots,I(2^{n-1})$ 即可。由于 $f(2^i)$ 不是 $0$ 就是 $2^i$，所以根据 $I$ 的返回值我们总能正确判断出 $c$ 的第 $i$ 位是 $0$ 还是 $1$。

如果 $k=2,3$，此时 $S=\{0,c\}$，我们询问 $I(2^n-1)$。

1. 如果 $S$ 不变，说明 $c=2^n-1$，此时我们只需询问 $I(1)$ 即可区分出 $k=2$ 还是 $k=3$。

2. 如果 $S$ 变了，说明 $c\neq 2^n-1$，但是还是有两种情况：

   1. 若 $k=2$，此时 $S=\{0,c,2^n-1\}$；
   2. 若 $k=3$，此时 $S=\{0,c,\neg c\}$，其中 $\neg c$ 表示 $c$ 的 $n$ 个二进制位按位取反。

   由于 $c\neq 2^n-1$ 且 $c\neq 0$，所以无论是 $c$ 还是 $\neg c$ 都一定是既有 $0$ 又有 $1$，所以 $c,\neg c<2^n-1$，因此询问 $Q(2^n-1)$ 就可以区分出 $k=2$ 还是 $k=3$。

   1. 若 $k=2$，我们通过二分区间 $l=1,r=2^n-2$ 就可以找到 $c$。

   2. 若 $k=3$，我们并不知道 $c$ 和 $\neg c$ 哪一个大。

      假设我们可以二分找到其中一个值，此时我们仍需要判断得到的是哪一个。

      假设我们二分出的是 $r$，那么 $f(c)=0\in S$，$f(\neg c)=2^n-1\not\in S$。所以询问 $I(r)$ 即可区分出 $c$ 和 $\neg c$。

      但是这里还有一个问题，不算二分次数，我们已经用掉了 $4$ 次询问，然而题目要求我们使用 $n+3$ 次询问，如何解决？

      由于 $c$ 和 $\neg c$ 一定有一个人最高位为 $1$，所以我们二分区间设置 $l=2^{n-1}$，$r=2^n-1$ 即可少一次二分。

复杂度 $O(n)$。

F

令 $1\sim n$ 的图为 $G$，$1\sim q$ 的图为 $G_Q$，那么要做的就是在 $G_Q$ 这个完全图上求最小生成树，其中边 $(i,j)$ 的权为 $dis(c_i,c_j)$。

考虑 $G_x$ 为 $G$ 删掉边权为 $x$ 的所有边后构成的图，那么 $dis(u,v)=\min\{x\mid (u,v)\text{ is connected in }G_x\}$。

反过来看，如果我们可以从小到大遍历 $x=0\sim m+1$，并且把 $G_x$ 中所有连通块对应到 $G_Q$ 中的点也连通起来，就等价于执行 Kruskal 算法。

问题是朴素遍历是 $O(mn^2)$ 的，显然无法通过本题。

观察 $G_x$ 为删除边权为 $x$ 的所有边，删除并且维护连通性并不简单，但是我们可以用线段树分治，将删除一条边，变为一条边只在某个区间中出现。

那么考虑暴力遍历 $G_x$ 中所有连通分量的操作，就等价于我们在 $G_x$ 对应的并查集合并的过程中，把 $G_x$ 并查集对应的 $G_Q$ 中对应的点也合并起来。

在实现上，我们需要将 $G_x$ 对应的并查集节点 $u$ 添加一个 $r_u$ 属性，表示 $G_x$ 的点 $u$ 对应在 $G_Q$ 的并查集的点是谁，如果不存在则为 $0$。在合并 $G_x$ 对应并查集的过程中，我们应当同时合并 $G_Q$ 对应的并查集。注意特殊处理 $r=0$ 的情况。

这里可以看作 $r_u$ 是一个等价类的集合，只不过只存储了这个等价类的某一个元素，那这里的处理就比较显然了，只要从集合合并的角度去理解即可。

将 $n,m,q$ 视作同阶，复杂度 $O(n\log^2n)$，其中一个 $\log$ 是线段树分治，另一个 $\log$ 是可撤销并查集。