task13

[TOC]

1. CF1896H - Cyclic Hamming [K] ✨

题面

对于两个长度相等的 01 串 $a,b$，定义 $f(a,b)=\sum[a_i\neq b_i]$

给定两个长度为 $2^{k+1}$ 的由 01? 组成的串 $s,t$，求有多少将 ? 替换为 01 的方式使得：

$s,t$ 均恰好有 $2^k$ 个 1
对于 $t$ 的任意循环位移 $c$，$f(s,c)\ge2^k$

答案对 $998244353$ 取模

H1：$1\le k\le7$

H2：$1\le k\le12$

题解

Sol

外星人题目。

令 $n=2^k$，首先进行一些简单的分析：由于 $\sum f(s,c)$ 应该是 $n^2$，所以任意一个 $f(s,c)$ 都应该等于 $\frac n2$，那么意味着 $s$ 中的 1 恰好有 $\frac n2$ 个对应 0，$\frac n2$ 个对应 1

考虑这是一个字符串和一个字符串的所有长度相等的子串，算一些对位贡献的，这个可以用卷积字符串匹配的 trick 解决

我们尝试列一下，可以发现，对 $S$ 和 $\text{rev}(T)$ 做长为 $2n$ 的循环卷积，得到的每一位，就是每一种位移方式，产生的 $S$ 和 $T$ 都为 1 的位置数量

而我们原先的条件等价于这个多项式每个位置都是 $\frac n2$

写成普通卷积的形式，就是 $x^{2n}C+\frac n2(1+x+\cdots+x^{2n-1})-C$，其中 $C$ 为某个 $n-1$ 次多项式

将右边的式子变形，可以得到 $(\frac n2+(x-1)C)(1+x+\cdots+x^{2n-1})$，而右边的东西可以被拆成 $\prod_{i=0}^k(1+x^{2^i})$

那么我们不妨猜测一下，两个串合法当且仅当其生成函数可以拆出所有 $(1+x^{2^i})$（因为这些东西都不可分，一定由某个串拆出）

事实上，这是正确的，因为将 $1$ 代入原多项式可以得到 $(S\cdot\text{rev}(T))(1)=n^2$，因此新的该多项式将 $\prod_{i=0}^k(1+x^{2^i})$ 除掉之后一定代入 $1$ 得到的值是 $\frac n2$，因此一定是 $\frac n2+(x-1)C$ 的形式，可以验证 $C$ 的次数也是对的

那么问题就是，我们需要判断 $S$ 和 $T$ 是否能拆出所有 $(1+x^{2^i})$

手玩一下，可以发现一个串可以拆出 $(1+x^{2^i})$ 的判据就是 $\bmod 2^{i+1}=0$ 的位置和应当与 $\bmod 2^{i+1}=2^i$ 的位置和相等

涉及模 $2^{i+1}$ 余数因此我们可以想到将每个数倒过来（即，从低位到高位）插入到 trie，那么我们对 $i$ 的限制就是所有深度为 $i$ 的点，左右子树内 1 的个数相等

那么我们就可以着手开始 dp 了。注意到此时 $S,T$ 已经没有什么关系了，我们可以分开处理。

令 $dp_{u,S,cnt}$ 表示当前在 $u$ 的子树，$S$ 内的 $(1+x^{2^i})$ 都能被拆出（其他的不要求不能拆出），子树内有 $cnt$ 个 1

转移有两种：

$dp_{u,S,x+y}\leftarrow dp_{2u,S,x}\cdot dp_{2u+1,S,y}\\dp_{u,S\cup\{dep_u\},2x}\leftarrow dp_{2u,S,x}\cdot dp_{2u+1,S,x}$

直接写的话，可以算一下复杂度是 $\sum_{t=0}^k2^t\cdot2^{k-t}\cdot2^{k-t}\cdot2^{k-t}=8^k$，可以通过 H1

有两个优化：

注意到第一种转移就是卷积，可以使用 ntt
设 $c=\text{popcount}(S)$，那么 $cnt$ 一定要是 $2^c$ 的倍数，否则一定是 $0$

两个优化同时加上之后复杂度是 $\sum_{t=0}^k 2^t\sum_S2^{|S|}\cdot|S|=3^k\cdot k$，可以通过 H2

2. CF1930H - Interactive Mex Tree [K]

题面

交互题。

首先，交互库给定一棵 $n$ 个点的树

你需要根据树的结构给出两个 $1\sim n$ 的排列 $p_1,p_2$

有 $q$ 个情景，每个情景交互库会生成一个你不知道的 $0\sim n-1$ 的排列 $a$，表示树上每个点的点权，然后给定两个点 $u,v$，询问树上 $u$ 到 $v$ 路径点权的 $\text{MEX}$

为了回答询问，你可以向交互库查询，查询给出一个区间 $[l,r]$ 以及 $t\in\{1,2\}$，交互库会回答 $p_t[l:r]$ 内节点的点权最小值

每个情景你有 $5$ 次查询机会，请实现这件事情

$2\le n\le10^5,1\le q\le10^4,nq\le3\times10^6$

题解

Sol

问号。

不知道怎么想到的啊？？

考虑 dfn 序：dfn 序一段区间其实可以表示将一段祖孙链删掉之后，还没被 dfs 过的位置

那么这就解决一半的问题了！

因此我们考虑用 dfs 入栈序和出栈序，那么我们就可以用一个序表示半边的子树

讨论一下是否是祖孙链，祖孙链的情况可以用 $3$ 次询问，非祖孙链的情况可以用 $5$ 次询问，问题解决。

3. CF2029G - Balanced Problem [E]

题面

有一个长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$，第 $i$ 个位置的权值为 $b_i$，初始均为 $0$

一次操作内，你可以选择一个前缀或后缀 $+1$

给定一个常数 $v$，定义数列的价值为，数列中 $a_i=v$ 的位置的 $b_i$ 之和

现在 $a$ 数组一开始被操作了 $m$ 次，这 $m$ 次由输入给出

给定 $V$，对于所有 $v=1,2,\cdots,V$，你需要得到经过在经过输入操作的数组 $a$ 上，再进行若干次操作，能得到的在最大价值

$1\le n,m\le2\times10^5,1\le V\le2000$

题解

Sol

莫名其妙。

最后我们一定是选择一个子序列，让它是 $v$，考虑如何判断一个子序列是否合法

考察这个序列的差分，每次加前缀相当于将 $d_1$ 加 $1$，将 $d_{i+1}$ 减 $1$，加后缀相当于给一个 $d_i$ 加 $1$

也就是说，我们最后要将这个子序列的差分变为 $0$（除 $d_1$），如果最后 $d_1\le v$，那么就可行

注意到 $d_1$ 的最小值其实就是 $d_1+\sum_{i\ge2}\max(d_i,0)$，对应到原序列上就是 $a_{i_1}+\sum\max(a_{i_j}-a_{i_{j-1}},0)$

那么我们就可以开始 dp 了，令 $dp_{i,j}$ 表示选了第 $i$ 个位置，当前的和为 $j$

直接 dp 是 $O(n^2V)$ 的，注意到只和上一个数的值有关，容易用树状数组优化到 $O(nV\log V)$

此时我们还没有用生成方式，注意到生成方式保证了整个序列可以被缩成 $O(V)$ 段值相同的段，那么我们的复杂度就是 $O(V^2\log V)$

其实还可以额外加一些段，使得相邻两段之间差的绝对值为 $1$，并且段数仍为 $O(V)$

考虑删掉一些不优的转移，对于位置 $x\rightarrow y$ 的转移，如果 $a_y$ 是 $a[x:y]$ 的最大值或最小值，那么我们让 $y$ 从 $y-1$ 一定可以涵盖这种情况，否则一定存在一个 $z$ 满足 $z\in(x,y)$ 且 $a_z=a_y$，我们让从 $y$ 从 $z$ 转移也可以涵盖这种情况

因此我们对于一个 $i$，只需要考虑从 $i-1$ 和上一个 $a_j=a_i$ 的位置的转移即可，复杂度 $O(V^2)$

4. CF2029H - Message Spread [K]

题面

给定一张 $n$ 个点 $m$ 条边的无向连通图，每一时刻每一条边 $(u,v)$ 有 $e_{u,v}$ 的概率出现

一开始节点 $1$ 被点亮了，接下来每一时刻，如果某个点上一时刻被点亮或有至少有一个邻点被点亮，那么它会被点亮

求所有节点被点亮的期望时间，对 $998244353$ 取模

$1\le n\le21,n-1\le m\le\frac12n(n-1)$，保证分母模意义下不为 $0$

12s, 1024MB

题解

Sol

考虑有一个显然的 dp：令 $f_S$ 表示 $S$ 被点亮，将所有点点亮的期望时间

那么有转移：

$f_S\leftarrow f_T\cdot\prod_{j\in T-S}\frac{1-\prod_{i\in S}(1-e_{i,j})}{\prod_{i\in S}(1-e_{i,j})}$

转移完了再给 $f_S$ 乘上一些无关的常数，进行一些无关紧要的运算

直接做是 $O(3^n)$ 的，考虑优化：如果令 $g_S$ 表示 $S$ 点集內部所有边的 $1-e$ 乘积，那么分母的乘积项可以拆成一个 $\frac{g_T}{g_S\cdot g_{T-S}}$ 的形式，分子就比较难办

大胆拆一下，然后进行一些推式子：

$f_S\leftarrow f_T\cdot\sum_{V\subseteq T-S}(-1)^{|V|}\frac{\prod_{j\in V}\prod_{i\in S}(1-e_{i,j})}{\prod_{j\in T-S}\prod_{i\in S}(1-e_{i,j})}\\f_S\leftarrow f_T\cdot\sum_{V\subseteq T-S}(-1)^{|V|}\prod_{j\in T-S-V}\prod_{i\in S}\frac1{1-e_{i,j}}\\f_S\leftarrow f_T\cdot\sum_{V\subseteq T-S}(-1)^{|V|}\cdot\frac{g_S\cdot g_{T-S-V}}{g_{T-V}}\\$

我们可以将这个过程看成一次 $T\rightarrow T-V$ 的高维后缀和，以及一次 $T-V\rightarrow S$ 的子集卷积

在线维护这个过程即可，复杂度 $O(n^22^n)$

5. JOI Open 2019 - Triple Jump [E] ⭐

题面

给定长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，$q$ 次询问，每次询问给定 $l,r$，你需要回答如下式子的值：

$\max_{l\le x<y<z\le r,y-x\le z-y} a_x+a_y+a_z$

$3\le n,q\le5\times10^5$

题解

Sol

好题啊！

直接做发现非常不好做，考虑观察一些性质：

经过若干时间的尝试，我们可以发现对于一个选择 $(x,y,z)$ 的方案，一定要满足 $\max(a[x+1:y-1])<\min(a_x,a_y)$，否则一定可以将区间缩的更小，并且和不降

那么把这个东西放到单调栈上考虑，容易发现只有 $O(n)$ 对 $(x,y)$ 有用

考虑对 $x$ 从大到小扫描线，维护每个 $z$ 的答案，扫到一个 $(x,y)$ 时将 $[2y-x,n]$ 的答案对 $a_x+a_y$ 取 $\max$（$+a_z$ 额外考虑），查询就是区间最大值，这个可以用线段树打 tag 维护

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

6. UR28 - 环环相扣 [E] ✔️

题面

给定长为数列 $a_1,a_2,\cdots,a_n$，$q$ 次询问，每次询问给定一个区间 $[l,r]$，询问如下式子的值：

$\max_{i,j,k\in [l,r],i\neq j,j\neq k,k\neq i}(a_i\bmod a_j)+(a_j\bmod a_k)+(a_k\bmod a_i)$

强制在线。

$3\le n\le2\times10^6,1\le q\le8\times10^5,1\le a_i\le10^{18}$，保证 $a_i$ 互不相同，且 $r-l+1\ge3$

题解

Sol

对于三个数 $a<b<c$，只有两种本质不同的排列方式：

$a+b+(c\bmod a)$，有下界 $a+b$，上界 $b+c$
$a+(b\bmod a)+(c\bmod b)$，有上界 $c$

考虑分析一些性质：

设 $mx_i$ 表示第 $i$ 大数，那么答案 $\ge mx_2+mx_3$
那么也就是说，两类的最大值 $c$ 必须为 $mx_1$，否则无法超过 $mx_2+mx_3$
第一类 $b$ 的值与 $a$ 无关，因此一定取 $mx_2$
如果 $2mx_3>mx_1$，那么 $(mx_1\bmod mx_3)+mx_3=mx_1$，即第一类可以取到上界 $mx_1+mx_2$，此时我们不用管第二类了，因为一定不优，直接输出答案即可
此时第二类如果 $b\le mx_3$，则上界为 $2mx_3$，小于 $mx_2+mx_3$，因此第二类想要有用必须取 $b=mx_2$

现在我们已经确定两类均满足 $b=mx_2,c=mx_1$，接下来考虑如何找到使其最大的 $a$

我们要求的是形如 $a+(k\bmod a)$ 的最大值，这个看起来没有什么性质，但是我们可以考虑根据这题的附加条件搞一下

对于一个 $a_i$，我们分析它在哪些 $b$ 和 $c$ 处会有用：

如果 $a_i\le\frac12 mx_3$，那么 $a+(k\bmod a)\le mx_3$，也就被 $mx_3+mx_2$ 爆了
注意到我们有若干个和 $\frac12$ 相关的限制，因此我们考虑在 $2a_i$ 处画一条线：
其中 $prv_i$ 表示 $i$ 左边第 $i$ 个 $>2a_i$ 的点
对于绿框内的点，其 $a_i+(k\bmod a_i)=k$，因为 $k\le 2a_i$，也就是说对于这种询问我们直接取 $mx_3$，一定不劣于取 $a_i$，因此不用考虑
对于 $prv_2$ 左边的点，如果其要为到 $i$ 区间的次大值或最大值，那么必定需要 $>2a_i$，而此时区间内有三个 $>2a_i$ 的数，也即 $mx_3>2a_i$，此时再取 $a_i$ 不优
也即我们需要考虑的点其实只有 $prv_1,prv_2$，以及对称的 $nxt_1,nxt_2$

因此，我们可以对每个数维护一个 vector，表示所有可能有用的决策，这样总和是 $O(n)$ 量级的

那么每次询问时，我们在 $mx_2,mx_3$ 的 vector 上分别查询一下这个区间的答案

注意到这时我们查询的是 vector 上一个区间的最大值，并且在查 $mx_3$ 的 vector 时，要求其不能与 $mx_2$ 相同

一个 vector $v_i$ 上查询的区间一定都经过某一个点，这个点就是原序列中这个 vector 的元素的出现位置 $i$，因此我们可以从 $i$ 为中心，向前向后求一个前缀 max 的东西，再维护一下次大值

总复杂度 $O(n\log n+q\log n)$，空间复杂度 $O(n)$，但是会被卡空间，需要精细实现

7. CF2029I - Variance Challenge [K]

题面

给定长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$，以及一个魔法常数 $k$

你一次操作可以选定一个区间 $[l,r]$，给 $a[l:r]$ 整体 $+k$

定义 $V(a)=\frac1n\sum_{i=1}^n(a_i-x)^2$，其中 $x=\frac1n\sum_{i=1}^na_i$，给定 $m$，你需要对每个 $p=1,2,\cdots,m$ 求出，恰好进行 $p$ 次操作后 $n^2V(a)$ 的最小值，可以发现这个数是整数

$1\le n,m\le5000,nm\le2\times10^4,1\le k,a_i\le10^5$

6s，256MB

题解

Sol

注意到恰好 $p$ 就是最多 $p$，因为操作 $[1,n]$ 不会对 $V(a)$ 有任何影响

直接 dp 很完蛋啊，而且这个操作看起来也没有什么性质。

注意到我们可以弱化一下，改成 $x$ 任意取，这样最小值仍然是 $x$ 取平均数的时候

$x$ 的取值只有 $O(nm)$ 种，因此我们考虑如何对一个 $x$ 求解：现在的问题就是进行 $p$ 次操作，最小化 $\sum(a_i-x)^2$ 的和

这个可以用费用流解决：

对每个 $0\sim n$ 的点 $i$ 连 $(S\rightarrow i,\infty,0),(i\rightarrow T,\infty,0)$
对每个 $0\sim n-1$ 的点 $i$，以及每个 $j\ge0$ 连 $(i\rightarrow i+1,1,(d_i+(j+1)-x)^2-(d_i+j-x)^2)$

进行 $p$ 次操作的最小代价就是流量为 $p$ 的最小费用流

但这个过程很简单，可以直接模拟，每轮增广的就是一个最大子段和，$O(n)$ 求一遍即可

复杂度 $O(n^2m^2)$，可以接受

8. CF1991H - Prime Split Game [E]

题面

给定 $n$ 个数 $a_1,a_2,\cdots,a_n$，两个人进行博弈，轮流进行如下操作：

选择一个 $k\in[1,\frac n2]$，删除 $a$ 中 $k$ 个数，然后再选择 $k$ 个数，将这 $k$ 个数中每一个拆成两个质数的和

不能操作者输，求先手胜还是后手胜

$2\le n\le2\times10^5,1\le a_i\le2\times10^5$

题解

Sol

注意到一个数不能拆很多次：因为奇数只能拆出 $2$ 和 $x-2$，而当 $x$ 足够大时 $x-2,x,x+2$ 不能同时为质数

那么我们首先考虑奇数的情况，奇数可以分三类：

$3$ 类，不能拆的
$5$ 类，能拆出 $2$ 和一个 $3$ 类质数
$7$ 类，能拆出 $2$ 和一个 $5$ 类质数

只有 $3,5$ 的胜负是好分析的，先手在全 $3$ 的时候会负，除此之外，只有全是 $5$ 并且 $n$ 是奇数的情况，先手无法将局面转化为全 $3$，而这种情况下后手必胜，因此：

在只有 $3,5$ 的时候，先手负当且仅当全为 $3$，或全为 $5$，且 $5$ 的个数为奇数

接下来考虑加入 $7$，通过手模或者打表，我们可以直接看出条件：

在只有 $3,5,7$ 的时候，先手负当且仅当全为 $3,7$，或全为 $5$，且 $5$ 的个数为奇数

那么证明是容易的，在只有 $3,7$ 的时候，不管怎么操作得到的局面都会至少有一个 $3$ 和一个 $5$，即必胜态，而必胜态也可以通过和只有 $3,5$ 时类似的方式转化到必败态

此时我们其实可以直接猜测 $3,7$ 没有什么区别，下面再验证

接下来考虑加入偶数：偶数有很多种拆分方式，这看起来不好办，但我们仔细考虑一下刚才的证明都用到了 $3,5$ 的哪些性质

我们大胆猜测一下：我们将所有能拆出两个 $3$ 的数分为 $5$，否则分为 $3$，结论依然是先手负当且仅当全为 $3$，或全为 $5$，且 $5$ 的个数为奇数

回顾一下刚才的证明：

对于有 $3$ 有 $5$，或 $5$ 的个数为偶数的时候，一定能转化为只有 $3$ 的情况
对于只有 $3$ 的情况，如果 $n$ 为奇数，那么最后拆完一定至少剩一个 $3$，并且至少拆出来一个 $5$，如果 $n$ 为偶数，那么拆完只要不是全 $3$ 就是必胜态，而拆完一定不是全 $3$
但是对于只有 $5$ 的情况，我们可以通过拆 $5,5$，使得剩下的局面依然只有 $5$，如果 $n$ 为奇数就违反了我们的结论，因此爆了

那么我们额外分一个类，能拆出 $5,5$ 的偶数分为 $10$ 类，不能拆出 $5,5$ 的偶数分为 $x$ 类

注意到对于剩下两类我们的分析还是对的，因此考虑只有 $5$ 的时候，且 $n$ 是奇数的胜负情况：

如果没有 $10$ 类，这就是最经典的情况，拆出来至少有一个 $5$ 和一个 $3$，必败
如果有 $[1,n-1]$ 个 $10$ 类，那么我们可以操作完不存在 $10$ 类，并且依然全是 $5$，必胜
如果全是 $10$ 类，那么拆出来会有 $5$ 有 $3$，或者至少剩一个 $10$ 类，因此必败

按照这个判一下即可，注意预处理要求卷积，可以使用 bitset 或 fft，复杂度 $O(n\log n)$ 或 $O(\frac{n^2}w)$

9. CF2039F - Shohag Loves Counting [E]

题面

对于一个数组 $a_1,a_2,\cdots,a_n$，定义 $f(k)$ 表示所有长为 $k$ 的子段最大值的 $\gcd$

定义一个数组是好的当且仅当 $f(1),f(2),\cdots,f(n)$ 互不相同

现给定 $m$，求所有满足 $a_i\in[1,m]$ 的 $a$，有多少是好的，对 $998244353$ 取模

F1：$1\le m\le3\times10^5$

F2：多次询问，$1\le m\le10^6$

题解

Sol

考虑分析这个限制是什么意思：显然我们每个 $f$ 内取过 $\gcd$ 的元素是越来越少的（$f(i+1)$ 内的数是 $f(i)$ 的子集），也就是说每个数有一个时间 $tim_i$，表示最长选出 $tim_i$ 长度的区间，使得 $a_i$ 为这个区间的最大值

每次 $f(i)$ 必须变化，也就是说我们 $n$ 个元素的 $tim$ 恰好为 $1\sim n$，考虑按 $tim$ 从小到大加数，这意味着每次加入一个 $i$ 时，$i$ 一定要在第一个或最后一个，也就是说如果确定了 $a_i$ 的值，那么我们有 $2^{n-1}$ 种排列的方案

现在问题可以表述为：

定义数列 $a_1,a_2,\cdots,a_n$ 是合法的当且仅当 $a_1<a_2<\cdots<a_n$，且对于任意 $1\le i<n,\gcd(a[i:n])\neq\gcd(a[i+1:n])$
求所有 $a_n\le m$ 的序列的 $2^{n-1}$ 之和

那么我们容易写出一个从后往前的 dp，令 $dp_{a,b}$ 表示现在选到的最后一个值 $a$，后缀 $\gcd$ 为 $b$，转移就是需要从所有 $a<c,b<d,\gcd(a,d)=b$ 的 $(c,d)$ 转移过来，可以将 $b=d$ 减掉，那么就只有 $a<c,\gcd(a,d)=b$ 的限制了

将 $\gcd$ 莫反，设莫反的变量是 $b|t$，那么我们就是要求所有 $t|d,a<c$ 的 $(c,d)$，得到 $g_{a,t}$，然后我们只要对 $g_{a,t}$ 做一个高维前缀和即可得到 $f_a$

$g_a$ 也可以用高维前缀和求值，总复杂度 $O(\sum_{i=1}^md(i)\omega(i))$

10. CF2039G - Shohag Loves Pebae [E]

题面

给定一棵 $n$ 个点的树，计数有多少给每个点分配一个 $[1,m]$ 内点权的方案，使得

对于任意 $1\le u<v\le n$，树上 $u$ 到 $v$ 的路径的点权 $\text{lcm}$ 不是 $u$ 到 $v$ 路径点数的倍数
所有点权的 $\gcd$ 为 $1$

答案对 $998244353$ 取模

$2\le n\le10^6,1\le m\le10^9$

题解

Sol

纯烂题。

考虑没有 $\gcd$ 的怎么做：每个点的限制相当于不能包含一个前缀的质数因数，设 $i$ 的点权不能包含前 $d_i$ 个质数

那么要求的就是 $\prod g(m,d_i)$，其中 $g(n,a)$ 表示 $\le n$ 的不被前 $a$ 个质数整除的数个数，注意到这个是 min25 的形式

接下来考虑对 $\gcd=1$ 的限制莫反，枚举一个 $t\in[1,m]$，要求所有数是 $t$ 的倍数，设 $d$ 的最大值为 $dR$，如果 $t$ 的最小质因子 $\le dR$，那么答案一定是 $0$，否则，我们可以直接用 $\lfloor\frac m{t}\rfloor$ 的上界求原答案

具体地，我们的式子是：

$\sum_{t=1}^m\mu(t)[\text{mnp}(t)>dR]\prod_{i=1}^ng\left(\left\lfloor\frac mt\right\rfloor,d_i\right)$

我们可以对后面的式子整除分块，那么我们需要求的就是块筛处，$\text{mnp}(t)>dR$ 的位置的 $\mu$ 前缀和，这个也是一个 min25 筛

考虑后面的式子怎么计算：

$dR\le\sqrt m$，此时直接暴力快速幂，复杂度大概是 $O(\frac m{\ln m})$，再带上一个快速幂，但是看看就可以知道次数应该很小（
$dR>\sqrt m$，那么此时如果 $1\sqrt m$ 的项，因为 $t>\sqrt m$ 时如果 $d_i>\sqrt m$ 贡献一定是 $1$

复杂度 $O(\frac m{\ln m})$

11. CF2034H - Rayan vs. Rayaneh [E] ⭐

题面

给定 $n$ 个互不相同的正整数 $a_1,a_2,\cdots,a_n$，求其最大的子集 $s_1,s_2,\cdots,s_k$，满足对于任意 $i$，不存在整数 $c_1,c_2,\cdots,c_k$ 使得 $\sum_{j\neq i}c_js_j=s_i$

$t$ 组数据。

$1\le n\le10^5,1\le\sum n\le3\times10^6,1\le a_i\le10^5$

题解

Sol

这个条件相当于对于任意 $s_i$，除了 $s_i$ 之外的所有数的 $\gcd$ 不能整除 $s_i$

进一步考虑一下这意味着什么，大概就是每个数都要有一个类似“独占非因数”的东西，只有加入它之后 $\gcd$ 里才不会有这个因子

具体地，对于所有质数 $p$，若 $S$ 中的元素含 $p$ 次数有唯一最小值，那么我们标记上唯一最小值，每个元素都要被至少一个质数标记

那么考虑枚举每个数的唯一最小值是哪个质数，以及次数，那么相当于要求每个数必须是 $b_i$ 的倍数，并且不能是 $b_i\times p_i$ 的倍数，这个可以用高维前缀和预处理，判断一下 $v_{b_i}-v_{b_ip_i}$ 是否为 $0$ 即可

注意到答案 $\le2$ 我们可以比较容易地判掉，因此我们只用枚举质因子个数 $\ge3$ 且除掉某种质数后不超过 $A$ 的数，因此可以毛估估一下状态不是很多

复杂度 $O(\text{数论})$

12. CF2034G - Simurgh’s Watch [E]

题面

给定 $n$ 个区间 $[l_i,r_i]$，请给每一个区间分配一种颜色，使得对于任意集合 $P$ 内的点 $x$，如果存在任意线段覆盖 $x$，则存在一种颜色 $c$，使得颜色为 $c$ 的所有线段恰好覆盖了 $x$ 一次

要求最小化颜色数并给出构造

$1\le n\le2\times10^5$

G1：$P$ 为所有实数点

G2：$P$ 为所有整数点

题解

Sol

首先考虑 G1。

注意到答案上界为 $3$：我们首先选择 $l$ 为最小值的 $r$ 最大的区间，然后每次从 $l$ 已经被覆盖的区间里挑出一个 $r$ 最大的不断扩展，得到一个区间序列，覆盖了原来覆盖的所有位置，然后将这个序列奇数/偶数位置分别染上 $1$ 和 $2$，其他区间全染成 $3$

答案为 $1$ 是好判的，我们只用考虑答案为 $2$ 的情况

注意我们可以离散化，离散化后每个小段一定恰有一个和其他区间颜色不同的区间，考虑令 $dp_i$ 表示与众不同的线段是 $i$，是否可能

dp 的时候只会改变 $O(n)$ 个线段的状态，进行一些讨论可以得到答案是否能为 $2$

然后把 dp 倒过来对着构造，进行更多的讨论可以得到答案如果为 $2$ 的构造

那么就可以通过 G1 了。

G2 相当于在上述 dp 中加上一个所有区间颜色相同的状态，多进行一万种讨论仍可以得到答案是否能为 $2$

然后把 dp 倒过来对着构造，进行一百万种讨论可以得到答案如果为 $2$ 的构造

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

13. CF2046D - For the Emperor! [E] ⭐

题面

给定一张 $n$ 个点 $m$ 条边的有向图，第 $i$ 个点上有 $a_i$ 个人，人可以在图上任意移动

你有一个消息，需要告诉所有人，当一个人知道消息之后，他会告诉当前节点上的所有人

你初始可以选择一些人，将消息告诉他们，然后你需要安排这些人合适地移动使得所有人都知道消息

求初始最少告诉多少人消息

$2\le n\le200,1\le m\le800,0\le a_i\le n$

题解

Sol

这个数据范围已经明示流了。

考虑如何建模：首先我们可以缩一个点让图变成 dag，然后每个点都必须被“激活”，可能是通过初始告诉激活，也有可能是某个人走进来激活

那么我们可以大致有一个人->激活点匹配的想法，考虑实现这个东西

注意到一个人激活完一个点之后还可以继续激活其他的点，并且我们的代价最后应该是初始激活的人数，这个不是很好办

考虑这样的处理方式：每个点一开始有 $a_i+1$ 个人，并且每个人会匹配一个点，匹配完直接消失，如果匹配自己就意味着是初始激活，产生 $1$ 的代价，最后要求每个点都被匹配上

如果匹配不满则无解，否则答案为最小权匹配

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

14. CF2046E - Cheops and a Contest [E] ✔️

题面

有 $n$ 个人，每个人有四个属性 $a_i,b_i,s_i,col_i$，保证 $a_i\le b_i$

你需要构造一个大小不超过 $5n$ 的集合 $S$，其中每个元素是一个二元组 $(d_i,t_i)$，满足 $t_i$ 互不相同

定义一个人 $(a_i,b_i,s_i,col_i)$ 的得分 $v_i$ 为至少满足如下两个条件之一的二元组 $(d_i,t_i)$ 个数：

$a_i\ge d_i$
$s_i=t_i,b_i\ge d_i$

你需要使得对于任意 $i,j$，若 $col_i<col_j$，则 $i$ 的得分大于 $j$ 的得分，给出构造或判断无解

设 $col$ 的取值范围为 $[1,m]$

E1：$2=m\le n\le3\times10^5$

E2：$2\le m\le n\le3\times10^5$

题解

Sol

考虑对于两个人 $i$ 和 $j$，$i$ 什么时候会大于 $j$

对于除了 $s_i,s_j$ 之外的所有 $t$，它们对 $i$ 和 $j$ 的贡献都是给 $a\ge d$ 加 $1$，然后 $=s_i$ 会给 $i$ 加上 $0/1$，$=s_j$ 会给 $j$ 加上 $0/1$

也就是说，如果 $a_i\le a_j$ 的话，$i$ 想要下克上是很难的，$i$ 大于 $j$ 必须要求不存在 $d$ 在 $(a_i,a_j]$ 内，并且 $i$ 一定要吃上 $=s_i$ 的，$j$ 一定不能吃上 $=s_j$ 的

由此，我们可以得到离散化后一些位置上不能有 $d$，并且对于每个人，我们可以得到他是必须吃到/必须吃不到/随意 $=s_i$ 的额外贡献

此时对于还没有被 ban 的 $a_i$ 的位置，我们用与 $s$ 全不相同的 $t$ 加 $2$，这就让所有 $a_j<a_i$ 且 $a_j$ 到 $a_i$ 之间有没被 ban 的位置的限制满足了

对于 $a_j<a_i$ 且没有没被 ban 的位置的，我们按照 $a_i\le a_j$ 同样的方式处理，相当于限制 $i$ 一定要吃上 $=s_i$ 的，$j$ 一定不能吃上 $=s_j$ 的

最后对于每个 $s$ 的限制相当于必须在一些区间内，且必须不在一些区间内，我们只需要任选一个符合要求的点即可

用数据结构加速这个过程，复杂度 $O(n\log n)$

15. CF2046F - Yandex Cuneiform [E]

题面

给定一个包含 YDX? 的字符串 $s$，请将每个 ? 填成 YDX 的一种，使得 $s$ 可以通过如下方式生成，并构造一种生成方式：

初始 $t$ 为空串，每轮操作向 $t$ 中加入 YDX 各一个，使得每轮操作后 $t$ 中没有相邻相同字符

给出构造或判断无解

F1：$s$ 中无 ?

F2：无特殊限制

$3\le n<2\times10^5$

题解

Sol

不难猜测合法的条件就是 YDX 无相邻相同，且出现次数相等，考虑构造，每次删除 YDX 各一个：

首先 $s_1,s_2$ 一定不同，并且删除不会有任何问题，那么现在我们只需要考虑一种字符了，设为 X
如果存在一个 X 使得它两边的字符不相等，那么我们可以直接构造了
否则每个 X 周围都是 YXY 或 DXD，那么串中间一定会出现一个位置，形如 YXYXYXYXYXYDYDYDXDXDXDXDXD，此时如果 D 是 $s_1$，那么我们将第一个 XYD 位置的 Y 删除，然后将 X 删除，然后将一开始的 D 删除，Y 是 $s_1$ 的情况是类似的，只要操作第一个 YDX 位置即可

用链表维护这个过程可以做到 $O(n)$，但由于要求排名，所以复杂度还是 $O(n\log n)$

考虑 F2，我们需要将每段问号填出来，使得其满足条件

可以证明，每段问号内填出 YDX 的个数的限制都是一个区间，那么将这些限制加起来之后还是一个区间

那么就直接扫一遍加起来，判断是否符合，然后倒着回去构造

构造的时候可以直接枚举三种字符，判断填上之后剩下的部分是否还满足条件

需要一些特判。

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

16. AGC004F - Namori [E]

题面

给定一个 $n$ 个点 $m$ 条边的无向简单连通图，满足 $n-1\le m\le n$

初始每个点都是白色，一步操作内你可以将两个相邻的同色点颜色取反，求将所有点变成黑色的最小操作次数

$2\le n\le10^5$

部分分：保证 $m=n-1$

题解

Sol

Flamire 做法

首先考虑 $m=n-1$ 怎么做

考虑进行树形 dp，首先叶子必须和父亲操作，也即叶子会要求父亲做一次 W->B

那么以此类推，每个点会要求父亲做若干次 W->B 或若干次 B->W，定义 $f_u$ 表示 $u$ 子树要求 $u$ 的父亲做多少次 W->B / B->W

那么就可以 $O(n)$ 转移，可以解决部分分

考虑观察我们实际上做了什么：如果将 W->B 视作 $+1$，将 B->W 视作 $-1$，那么最后每个点的和都应为 $1$，并且我们的操作是给两个相邻点 $+1$ 或 $-1$

（注意到我们这里其实正确性不是那么严谨，但是看起来还有点对，所以不管了）

那么考虑 $m=n$ 的问题：

首先树的部分仍然可以用上面的递推，那也就是说我们环上每个点初始有一个点权，要求用若干次相邻 $+1/-1$ 操作将所有点权变为 $1$

对每条边用了多少次列式，即为 $x_i+x_{i+1}=w_i$，我们要最小化 $\sum|x_i|$

如果是奇环，那么有唯一解，直接解出来输出即可
如果是偶环，那么解出来之后奇数位置可以加上 $c$，偶数位置可以减掉 $c$，其中 $c$ 是某个定值，那么这是绝对值最小化，求中位数即可

题解做法

考虑一个经典的转化：将树黑白染色，那么现在操作就变成将一个黑色移动到一个相邻点上

那么树我们可以直接取每条边两边需要的黑白之差即可

考虑基环树的情况：

环是偶数：

设多出来的一条边运送了 $x$ 个黑色（有向），那么每条边都可以表示成 $x+\text{constant}$ 的形式，我们就是要最小化一个绝对值不等式，求中位数即可

环是奇数：

现在黑白染色会产生两个相邻同色的点，考察这条边的影响，操作这条边会使得总黑色数 $+2$ 或 $-2$，并且只有这个操作会改变黑色数，那么我们可以直接计算出这条边会操作多少次，之后将这条边删掉做树的问题即可

17. AGC006F - Blackout [E]

题面

有一个 $n\times n$ 的矩阵，初始有 $m$ 个位置为黑色，你可以进行如下操作：

如果 $(x,y),(y,z)$ 都是黑色的，你可以将 $(z,x)$ 染黑

求操作到不能进行操作之后有多少个位置为黑色

$1\le n\le10^5,1\le m\le10^5$

题解

Sol

考虑放到图上：如果有两条边 $x\rightarrow y,y\rightarrow z$，那么我们可以加上 $z\rightarrow x$

首先我们发现一件事情：如果一个连通块内出现了自环，那么这个连通块最后一定会变成环，证明是容易的

那么考虑什么样的图不会出自环，经过一些手模，我们可以发现，大小为 $2,4,5,7$ 的环都会出自环，大小为 $3,6$ 的环不会出自环，因此我们不妨猜测一下和模 $3$ 有关

进一步地，考虑一种比较经典的思路：我们将图 $012$ 染色（即所有边都是 $0\rightarrow1,1\rightarrow2,2\rightarrow0$），可以发现我们的操作一定不会破坏 $012$ 染色的性质

我们可以猜测：如果图不能 $012$ 染色，那么一定会出自环，否则我们恰好能连出来所有符合 $012$ 染色的边

但此时还有一种特殊情况：就是图染出来只有 $012$ 中的两种，此时我们无法进行任何操作，答案应当为边数

证明是容易归纳的，对每个连通块分别做一下就好了

复杂度 $O(n\alpha(n))$

18. AGC007F - Shik and Copying String [S]

题面

给定长为 $n$ 的小写字符串 $s_0,t$，求最小的 $k$ 使得存在字符串序列 $p_0,p_1,p_2,\cdots,p_k$，满足 $p_0=s_0,p_k=t$，且：

对任意 $(i,j)$，$p_{i,j}=p_{i,j-1}$ 或 $p_{i,j}=p_{i-1,j}$

$1\le n\le10^6$

题解

Sol

怀疑出题人精神状态不太正常。

考虑倒着贪心，每次把上一个相等的字符拉过来，这个看起来就很对，考虑描述这个过程

首先，我们可以把 $t$ 中的连续段进行一个匹配：

从 $i=n\rightarrow1$ 扫 $t_i$，维护一个指针 $pt$，初始为 $n+1$
如果 $i=n$ 或 $t_i\neq t_{i+1}$ 或 $i<pt$，那么我们需要将 $t_i$ 与之前的一个 $s$ 中字符匹配，此时找到 $pt-1$ 之前的第一个和 $t_i$ 相等的位置 $x$，将 $s_x$ 与 $t_i$ 匹配，并将 $pt$ 设为 $x$

如果匹配不出来说明无解，那么接下来考虑最小步数

首先把所有 $s$ 中匹配过的位置拎出来作为序列 $vs$，那么第一步之后，原来在 $vs_i$ 的字符可以前进到 $vs_{i+1}-1$，也就是说 $vs_i$ 到达 $vt_i$ 的步数为最小的 $k$ 使得 $vs_{i+k}-k\ge vt_i$，这个可以二分或双指针

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

19. AGC007C - Pushing Balls [K]

题面

数轴上有 $n$ 个球和 $n+1$ 个洞，第 $i$ 个球在第 $i$ 个洞和第 $i+1$ 个洞之间

给定 $d_1,x$，生成序列：$d_i-d_{i-1}=x(2\le i\le2n)$，其中 $d_i$ 表示第 $i$ 个东西和第 $i+1$ 个东西之间的距离

现在每次随机选一个球，让其随机向左或向右运动，运动到第一个还没有球的洞放进去

求 $n$ 次之后，所有球运动的距离之和的期望，实数。

$1\le n\le2\times10^5,1\le d_1\le100,0\le x\le100$

题解

Sol

神金啊！！！！！

注意到给定的距离是一个等差数列，这大概率意味着什么

观察到我们的答案关于每个 $d$ 是线性的，而如果我们把 $d$ reverse 一下，答案应该还是一样的，那么也就是说我们可以直接将这两种情况加在一起取平均，算这个情况的答案

那么现在所有的 $d_i$ 都相等了，考虑这样会发生什么：

首先，第一步的答案就非常好算了，一定是 $d$
考虑操作完第一步会发生什么：$d_i$ 会有 $\frac{2n-1}{2n}$ 的概率不变，有 $\frac1{2n}$ 的概率变成 $3d$，也就是说新的 $d$ 期望也是一样的

那么直接计算即可，复杂度 $O(n)$

20. AGC008F - Black Radius [E] ⭐

题面

给定一棵 $n$ 个点的树，定义 $C(u,d)$ 为所有到点 $u$ 距离 $\le d$ 的点组成的集合

现在给定一个点集 $S$，求对于所有 $u\in S,d\in[0,+\infty)$，一共有多少种本质不同的 $C(u,d)$

$2\le n\le2\times10^5$

部分分：$S=\{1,2,\cdots,n\}$

题解

Sol

首先考虑 $S$ 为全集的情况

考虑什么样的集合会被统计到答案里。

由于这个问题和树上距离有关，所以我们可以考虑一下直径中点

我们发现，可能成为 $C$ 的集合一定是距离直径中点小于等于某个值的点（即是直径重点的某个 $C$，如果我们允许 $u$ 取到边上的中点的话），证明的话考虑一下直径端点即可，如果中间有某个 $\le\frac d2$ 的点没有选进来，那么一定无法同时包含直径端点

这意味着我们可以给每个集合找到一个唯一统计的方式，接下来讨论直径中点的情况：

直径中点在点上，那么取出删掉这个点后所有子树的高度 $h$，$d$ 的取值范围就是 $0$ 到次大的 $h$
直径中点在边上，那么实际上的 $u$ 不能取到这条边上，因此我们需要考虑一下

考察什么样的 $u$ 能生成某个特定的 $C$ 集合，我们发现这个条件是以 $C$ 的直径中点 $o$ 为根时，找到 $o$ 所有完全被 $C$ 包含的儿子子树，这些儿子子树里的点就是可行的 $u$，证明也是稍微讨论一下距离即可

那么直径中点在边上的情况，我们必须有两边子树的某一边是满的，而距离再扩大时，直径中点就无法保持在这条边上，也就是说每条边恰好有一个合法的 $C$ 集合，使得直径中点在这条边上

那么我们就能解决部分分了。

改到整道题也是容易的，只要改一下 $C$ 集合被统计的条件即可：

直径中点在点上，将所有 $u$ 的子树按照高度从小到大排序，并加入一个 $0$ 表示 $u$ 本身，那么我们不断增大 $d$ 的过程就是将这些子树一个个填满，第一次填满一个有 $S$ 点的子树就合法了，那么我们可以求出合法的左端点和右端点，减一下就可以得到 $d$ 的方案数
直径中点在边上，高度更小的一边需要有 $S$ 点（如果高度一样则至少有一边有 $S$ 点即可）

复杂度 $O(n)$

21. AGC011F - Train Service Planning [E]

题面

有 $0,1,\cdots,n$ 这 $n+1$ 个车站，第 $i-1$ 个车站到第 $i$ 个车站需要 $a_i$ 的时间，并且由 $b_i=2/1$ 表示是否允许双向通行

火车会在车站上跑，一种是 $0\rightarrow n$ 的火车，另一种是 $n\rightarrow0$ 的火车，火车可以在站内停靠任意长的时间，但不能在路途中停下，即 $i-1$ 到 $i$ 或 $i$ 到 $i-1$ 一定会恰好花费 $a_i$ 的时间

给定常数 $k$，你需要安排火车的时间表，使得满足如下条件：

对于从 $0\rightarrow n$ 的火车，如果在 $s$ 时刻到达某站，在 $t$ 时刻离开该站，那么下一辆 $0\rightarrow n$ 的火车必须在 $s+k$ 时刻到达该站，在 $t+k$ 时刻离开该站，上一辆 $0\rightarrow n$ 的火车必须在 $s-k$ 时刻到达该站，在 $t-k$ 时刻离开该站
对于 $b_i=1$ 的间隔，不允许同时有两个不同向的火车经过

求安排后，$0\rightarrow n$ 的火车运行的时间加上 $n\rightarrow0$ 的火车运行的时间之和的最小值

$1\le n\le10^5,1\le k\le10^9$

部分分：$b_i=1$

部分分：$n\le200$

题解

Sol

考虑用如下方式描述这个问题：

有一个 $(\sum a_i)\times k$ 的循环矩形，在大小为 $k$ 的一维上循环
在从上到下每隔 $a_i$ 的距离会有一条线，现在我们要在每两条线之间画一条斜率为 $1$ 的线段，一条斜率为 $-1$ 的线段，如果 $b_i=1$，那么这两条线段不能相交
我们要最小化斜率为 $1$ 的线段端点之间的距离（有向），以及斜率为 $-1$ 的线段端点之间距离（有向）之和

考虑推一下坐标轴，把斜率为 $-1$ 推成竖直线段，斜率为 $1$ 推成斜率为 $2$，然后将 $a_i$ 乘 $2$，这样就是斜率为 $1$ 和竖直线段的问题

注意到一定存在最优解使得竖直线段都满足 $x=0$，否则我们找到第一段不是 $x=0$ 的线段，然后将后面所有的东西一块循环移位，一定可以将这个线段移动到 $x=0$，并且不劣

也就是说在 $x=0$ 的直线上可能有一些区间有障碍

那么我们的决策一定是固定的了，首先在第 $0$ 站选定一个起点，然后走斜率为 $1$ 的直线，直到再走要撞上障碍，此时我们等到 $x=0$，也就是 $x=k$，然后继续出发

以每个站的 $x=0$ 把整个过程分段，然后考虑 dp，那么只要找到每个点的唯一后继，进行扫描线，从第 $n$ 站往第 $0$ 站扫，那么每次就相当于将一个区间覆盖成撞到某个障碍，然后单点查询某个点会撞到哪个障碍

最后在第 $0$ 站扫一遍所有区间算答案即可

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

22. AGC012F - Prefix Median [E] ✔️

题面

给定一个长为 $2n-1$ 的序列 $a_1,a_2,\cdots,a_{2n-1}$

按照如下方式生成长为 $n$ 的序列 $b_1,b_2,\cdots,b_n$：

$b_i$ 为 $a_1,a_2,\cdots,a_{2i-1}$ 的中位数

求本质不同的 $b$ 序列种数，对 $10^9+7$ 取模

$1\le n\le50,1\le a_i\le2n-1$

题解

Sol

首先考虑 $a_i=i$ 的情况怎么算：

那么我们需要找一个刻画 $b$ 序列的方式，考虑分析一些必要条件：

首先，$b_i$ 必须在 $[i,2n-i]$ 之间
其次，每次加入两个 $a$ 元素之后，中位数的排名不会偏移超过 $1$

即 $b$ 序列需要满足 $b_i\in[i,2n-i]$，且 $b_i$ 到 $b_{i+1}$ 中间不能经过之前选过的 $b$

事实上，这也是充分的，证明考虑归纳：我们只要证明对于任意 $b$ 序列，一定能够选出来两个数 $a_{2n-2},a_{2n-1}$，使得 $b[1:n-1]$ 都没被删掉，并且每个 $b_i$ 依然在对应的区间内

讨论 $b_{i-1}=i-2/i-1/i$ 的情况，发现只要在左侧/右侧删对应个数即可，由抽屉原理保证一定有解

而对于 $a$ 有相同的情况，可以发现我们对于每个连续段只保留距离中点最近的点一定是可行的

那么我们就可以 dp 了，考虑将这个过程倒过来，也就是说每次 $b_{i+1}$ 到 $b_i$ 越过的点之后就都不能再用了

令 $dp_{i,j,k}$ 表示填完 $b_i,b_{i+1},\cdots,b_n$ 了，当前还剩 $j$ 个位置可以填数，并且我们在这 $j$ 个位置中的第 $k$ 个

转移枚举一下下一个数即可，复杂度 $O(n^4)$

23. AGC013F - Two Faced Cards [K] ✨

题面

有 $n$ 张卡，正面反面分别为 $a_i,b_i$，以及 $n+1$ 个整数 $c_i$

现在有 $q$ 次询问，每次询问给定一张额外的卡，正面反面分别为 $(d,e)$

你需要将这 $n+1$ 张卡和 $c_i$ 进行匹配，并且每张卡你需要指定使用的是哪一面，需要满足使用的面写的数字小于等于其所匹配的 $c_i$

对每个询问，求最多使用多少个正面，或判断无法匹配

$1\le n\le10^5,1\le q\le10^5$

题解

Sol

考虑如何解决单次询问：

判断一种选择值的方式是否合法，一种显然的方式是排序后是否对位小于，但这么判有点完蛋，考虑有没有其他的判法

我们可以把值放到数轴上，卡片选择的值视作 $+1$，$c$ 视作 $-1$，那么相当于每个前缀和必须 $\ge0$

那么对于一个卡片，如果 $a_i<b_i$ 那么必定选择 $a_i$，否则我们一开始默认选择 $a_i$，将其改成 $b_i$ 就是给 $[b_i,a_i)$ 加 $1$

因此单次询问也就是给定一个序列 $w$，以及一些区间 $[l,r]$，你需要选择最少的区间将它们区间 $+1$，使得最后所有 $w_i$ 都 $\ge0$，这个是经典贪心

接下来考虑如何扩展到 $q$ 次询问：

考察加入的一张卡片影响是什么，我们可以这张卡片选了正面还是反面，那么此时匹配的 $c$ 一定是大于它的最小的，也就是说我们即要求原来的 $n$ 张卡，与去掉某一个 $c$ 之后的匹配结果，一共 $n+1$ 种情况

去掉一个 $c$ 也就是给原来的 $w$ 后缀 $+1$，即我们现在对最后的 $w$ 的限制为一段前缀的 $w_i\ge0$，其余的 $w_i\ge-1$

这个不是很好办啊！

考虑能不能找到一些固定的操作：注意到 $w_i\le-2$ 的位置是无论如何都要操作的，考虑能不能在这上面搞一点事情

事实上是可以的，令 $i$ 为最后一个满足 $w_i\le-2$ 的位置，$I$ 为包含 $i$ 的区间中 $l$ 最小的，可以证明，一定存在一个最优解选择了 $I$，具体地：

考虑一个不包含 $I$ 的最优解，设 $i$ 需要 $lim$ 次操作才能使其满足限制，并且由于 $w[i+1:n]\ge-1$，那也就说后面任何一个位置需要的操作次数一定比 $i$ 小，我们取经过 $i$ 的所有操作了的区间，取出其中 $l$ 最小的，设其为 $J$，将 $J$ 替换为 $I$ 在 $i$ 左面一定不劣，在右边一定不会导致不合法

那么我们不断选择这样的 $I$，就可以使得所有 $w_i\ge-1$（如果不行则所有询问均不可能）

那么现在随着我们删除的 $c_i$ 不断变大，就是左边不断多出来位置需要 $\ge0$，从左到右贪心即可

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

24. CF104937E - Monitoring Beavers [E]

题面

给定一张 $n$ 个点 $m$ 条边的有向图，保证每个点入度都 $>0$

现在给定每条边的状态为 0 或 1，你需要进行若干次将一条边反向的操作，使得最后所有状态为 0 的边还是原来的方向，1 的边是原来的反向

你还需要额外保证：在操作过程中，每个点的入度时刻 $>0$

你需要在最小的操作次数内完成这件事情，并给出构造，或判断无解

$3\le n\le m\le10^5$

题解

Sol

首先把终止状态不合法判了。

考虑只有 1 的情况：经过若干时间的手模，我们可以发现当且仅当存在一个连通块为一个环时不行

如果一个连通块不是环，那么由于终止状态合法所以每个出度为 $0$ 的 scc 都不是单点，也就至少存在一个环

而一个环上面有一个额外入度是可以反转的，转一圈操作即可，然后我们可以用这些环把一棵内向树反转成外向树，这样每个点就都有入度了，剩下的边随便反转即可

接下来考虑加入 0 边，如果 0 边不能操作：

如果一条 1 边两个端点都有 0 边入度，那么显然这条 1 边可以直接反转
如果一条 1 边指向的点有 0 边入度，那么显然我们直接反转是不劣的

首先把这样的东西搞掉，那么剩下的图的 1 边一定要么是在没有 0 入度的点之间连，要么是从一个有 0 入度的连向没有 0 入度的

那此时不能构造的一定满足没有 0 入度的 1 边组成一个环，且没有从有 0 入度的点连过来的 1 边

这种情况下，我们需要从这个 1 环向下找到一个有 $\ge2$ 0 入度的点，然后将路径上这条链临时反转一下，把这个环造完之后再搞回来

直接实现这个可以构造出一种方案，但不是最小的。

原因是我们之前 “显然反转不劣” 的 1 边，即我们可能可以把两次反转合并

那么我们就顺着扫整个操作序列，如果存在某一个时刻度数 $\ge2$ 则认为它是一个可行点，然后求出距离每个点最近的可行点，扫到的时候把其需要构造的 1 环全插入进操作序列即可

复杂度 $O(n)$

25. AT_toyota2023_F - Forbidden Pattern [E]

题面

给定长为 $n$ 的由 AB 组成的字符串 $s$，你可以进行 $\ge0$ 次以下操作：

选择长为 $2$ 的子串，使得其不为 AB，并将其删除，两边拼起来

求能得到多少本质不同的子串，对 $998244353$ 取模

$2\le n\le10^6$

题解

Sol

考虑玩出一个类似自动机的东西来匹配满足条件的子序列。

那么首先我们需要知道一个串能删空的条件，手模一下可以发现：

首先，长度显然是偶数，如果第一个字符是 B，那么一定可行
对称地，如果最后一个字符是 A，那么也一定可行
进一步地，如果我们能在中间找到一个位置 $i$，使得 $i$ 为偶数，且 $s_i=\texttt{A},s_{i+1}=\texttt{B}$，则也一定可行

事实上，容易归纳证明这个是充要条件

下面我们用 | 在每个偶数位置分段，第三个条件即存在一个 A|B

那么接下来考虑怎么匹配让每种子序列恰好有一种匹配方式，分情况讨论，设我们现在需要匹配到了 $s[i:n]$：

下一步需要匹配出来一个 A，讨论我们用来匹配的位置下一个字符是什么，可能的情况为 AA 或 AB，这其中 AB 是更厉害一点的，因为这样我们下一步可以删空任意长为偶数的前缀了，那么分类讨论第一个 AA 和 AB 的位置关系：
- 第一个 AB 在前，即 s[i].....|AB...|AA，那么我们直接匹配这个 A，然后从 B 开始继续匹配
- 第一个 AA 在前，即 s[i].....|AA...|AB，那么我们有两种选择，一种是匹配 AA，另一种是匹配 AB，但是注意到 |AA...|AB 当中，A...|A 的部分一定是可以被删空的，也就是说我们匹配 AA 之后能到的状态包含匹配 AB 能到的状态，因此直接匹配 AA 的 A 更优（可以类似分析匹配更靠后的 AA 也一定不优）
下一步需要匹配出来一个 B，分两种情况讨论：
- $s_i=\texttt{A}$，考虑其所有可能能够删空的段，那么一定是类似 s[i].....A|A...A|A...A|A...A|B，即先有若干个位置可以删出来 A，然后第一次可以删出来 B 后，后面的每个奇偶性正确的位置都可以删出来了，那么第一个 A|B 前不可能匹配得出来 B，因此我们可以直接挪到这个 B 的位置匹配
- $s_i=\texttt{B}$，依然是讨论一下第一个 BA 和第一个 BB 的位置关系，如果 BB 在前，那么直接匹配这个 B 即可，否则 BA 在前，那么我们同时有两种选择，我们不会做了。

那考虑直接多设一个状态，表示我们当前一共有两个位置可以匹配，分别为 $i$（保证 $s_{i-1}s_i=\texttt{BA}$），以及后面第一个 BB，讨论和前面 $s_i=\texttt{A}$ 的是类似的，无非是加一个 BB 的限制

那么直接对这个进行 dp，复杂度 $O(n)$

22. QOJ1839 - Joke [E]

题面

对于两个 $1\sim n$ 的排列 $p,q$，定义 $f(p,q)$ 为满足以下条件的串 $s$ 数量：

$s$ 是长为 $n$ 的 01 串
存在一种将这两个序列归并成一个的方案，使得 $[p_i<q_i]\Leftrightarrow[s_i=\texttt{0}]$

现在给定 $1\sim n$ 的排列 $p$，和 $1\sim n$ 的排列 $q$ 的一部分，求所有把 $q$ 补全的方式的 $f(p,q)$ 之和，对 $998244353$ 取模

$1\le n\le100$

题解

Sol

首先我们可以把 $p$ 变成 $[1,2,\cdots,n]$，那么就只有 $i$ 和 $q_i$ 了

我们如果把这个画到二分图上，如果 $q_i$ 确定了就在左部 $i$ 和右部 $q_i$ 之间连一条边，那么 $s$ 就相当于在给这些边定向

考虑一个 $f(q)$ 怎么算，那么就相当于有多少定向方式使得其不会出现环

一个显然的条件是两条交叉的边 $x,y$，其中 $x$ 的左部点更靠上，不能出现 $x$ 的方向为 $1$，$y$ 的方向为 $0$

事实上，这就是充要的，必要性显然，充分性如果满足这个条件，那么任意一条路径经过的左部点和右部点的下标上一定是递增的

但是有了这个还不是很好算，因此我们考虑如何把这个转化成一个好计数的东西

我们找到最严的限制，如果我们只保留所有 $0$ 边，把所有方向为 $0$ 的 $q$ 写成一个序列，这些最严的限制就是这个序列的所有后缀最小值

注意到我们可以建立这个最严限制集合，和原来的边 $01$ 填法的一一对应：

对于原来的 $01$ 填法，我们可以按照如上规则生成一个最严限制集合
对于一个边集，如果我们钦定它是最严限制集合，那么讨论以下其他所有边，方向一定是固定的

也就是我们只要计数最严限制集合即可，而这个就是 $q$ 的上升子序列个数

套到原题上，我们现在是给定了 $q$ 的一部分，我们要求所有填 $q$ 的方案的上升子序列个数之和

令 $dp_{k,i,j}$ 表示我们上升序列最后一个元素是 $q_i=j$，并且上升序列里选了 $k$ 个不确定的 $q$，转移是一个二维前缀和，容易优化掉

最后的答案就是 $\sum dp_{k,i,j}(m-k)!$，其中 $m$ 为不确定的 $q$ 数量

复杂度 $O(n^3)$

23. AHOI2013 - 连通图 [E/K]

题面

给定一张 $n$ 个点 $m$ 条边的简单无向连通图，$q$ 次询问，每次给出一个边集，询问将这个边集里的边删除后图是否连通

$1\le n,q\le10^5,1\le m\le2\times10^5$，边集大小 $\le4$

题解

Sol

显然可以线段树分治，但是有一种更好的做法。

考虑极小割的刻画，即将图划分为恰好两个连通块的割

我们给边赋权，初始都为 $0$，找出任意一棵生成树，对于第 $i$ 条非树边，我们将只包含这一条非树边的环的边权都 $\oplus2^i$

那么我们证明：一个边集是极小割当且仅当其异或和为 $0$

首先证明极小割的异或和为 $0$：

考虑令一个点的点权为其所有邻边的权值的异或和，那么由于我们每次异或一个环，所以初始所有点的点权应该都为 $0$

而考虑割完之后，分成了两个连通块 $S,T$，那么容易发现我们删掉的边的异或和等于此时 $S$ 中所有点权的异或和（这里的点权已经去除了删掉的边）

在 $S$ 中所有点权的异或和中，每条边会被贡献两次，所以这个值为 $0$，因此极小割的异或和为 $0$

然后证明异或和为 $0$ 的一定是极小割：

考虑所有没被割掉的非树边，其一定跨过偶数条被割掉的树边（否则异或和不为 $0$），那么我们把没有被割掉的树边缩成一个点，这些非树边连接的两个点深度一定相同，而至少有两个点，也就是说图不连通

那么只要判一下是否有子集异或为 $0$ 即可

由于 $2^i$ 太大了，所以我们替换成 $2^{64}$ 以内的随机权值

24. CF1693E - Outermost Maximums [E]

题面

有一个长为 $n+2$ 的序列 $a_0,a_1,\cdots,a_{n+1}$，满足 $a_0=a_{n+1}=0$

你可以进行若干次如下操作：

选择最左边的最大值 $a_i$，将 $a_i\leftarrow\max(a[1:i-1])$
选择最右边的最大值 $a_i$，将 $a_i\leftarrow\max(a[i+1:n+1])$

求最少操作次数将所有 $a_i$ 变为 $0$

$1\le n\le2\times10^5,0\le a_i\le n$

题解

Sol

我其实并不是很懂怎么直接维护贪心。

考虑一个 $a_i$，其最少被操作多少次，可以发现一次操作后，$a_i$ 一定变为左边 $<a_i$ 的最大值或右边 $<a_i$ 的最大值

那么一个下界就是我们从 $a_i$ 开始，每次将值变为左右两边更小的值

同时这个下界也是可以取到的，一个感性理解是对于同一个值，越靠左一定越容易选左边，也就是说对于同一个值，选左边的一定是一段前缀，那么就是可以合法操作的

考虑维护这个东西，我们从左到右扫 $i$，那么每次就是一个 $a_i$ 从右边变为左边，放到值域上考虑，如果这个数在左/右边存在就挂上一个 L/R，每次就是走到下一个 L 或下一个 R，用线段树维护走一步 L/R 进来，最后走 L/R 出去

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

25. CF79E - Security System [E]

题面

二维平面上，你现在在 $(1,1)$，你每次可以向上或向右移动一步，最终你需要到达 $(n,n)$

一共有 $c^2$ 监测器，分别分布在 $([a:a+c-1],[b:b+c-1])$ 的每个整点上

每个监测器有一个警戒值，初始为 $T$，对于一个 $(x,y)$ 处的监测器，你每步移动后，设你处在 $(u,v)$，那么这个监测器的警戒值会减小 $|x-u|+|y-v|$，你需要保证任意时刻监测器的警戒值都 $\ge0$

$2\le n\le2\times10^5,0\le T\le10^{14}$，保证所有监测器都在 $[1,n]\times[1,n]$ 内

题解

Sol

注意到只有四个角有用，我们如果把最后的警戒值写成一个关于监测器位置的函数 $f(x,y)$，那么其一定形如 $\sum|x-a_i|+\sum|y-b_i|$，不难发现 $x,y$ 一定要么取最大值要么取最小值

因此考虑模拟这个过程，那么我们现在就是要以较低复杂度计算走到了 $(x,y)$，并且给定当前监测器的状态，求是否能到 $(n,n)$

注意到如果不在监测器的正方形内，那么我们是容易玩出下一步最优决策的（即走到正方形内，或走到终点）

因此我们只用考虑正方形内的情况，注意到我们一定是走一条路径到 $(a+c-1,b+c-1)$ 最优，那么考虑这条路径怎么走

怎么走对左下和右上的监测器都是一样的，因此我们只用考虑左上和右下

而这两个监视器满足一个性质：我们走出来的贡献之和是一样的，而注意到左上的最小值就是一开始向上再向右，最大值就是一开始向右再向左

而中间的值奇偶性正确则一定可以取到，我们每次取相邻的两步右上，将其变为上右，即可将贡献调整 $2$

那么直接 $O(1)$ 判断即可

复杂度 $O(n)$

26. CF1322F - Assigning Fares [E]

题面

给定一棵 $n$ 个点的树和 $m$ 条树上的链，你需要给每个点赋一个正整数的权，使得每条链上点权要么严格递增要么严格递降

求点权最大值的最小值，并构造方案，或者判断无解

$2\le n\le5\times10^5,1\le m\le5\times10^5$

题解

Sol

无趣的题目。

注意到相当于我们要给边定向，而随便定一个根，那么每条边的方向可以用并查集维护

那么现在的问题就是有一些边必须同一个方向，另一些边必须是另一个方向，并且被限制的边形成若干个连通块

直接 dp，首先二分一个 $T$ 表示最后方案中的最长链，令 $f_i$ 表示 $i$ 的父边指向上，并且子树不出现超过 $T$ 的链的情况下，子树内到 $i$ 的最长链最短为多少，注意到这也同时是父边向下，$i$ 到子树内的最长链最短为多少

在一个点 $u$ 的转移最后可以变成如下问题：

对于每个连通块，可以表示为一个二元组 $(a,b)$，你可以选择计入 $(a,b)$ 或 $(b,a)$
最后你需要使得第一维的 $\max$ 加第二维的 $\max$ 之和 $\le T$，且第一维的 $\max$ 最小

那么考虑全局最大值，其一定放在第二维，剩下的全选较小的放到第一维即可

构造方案的话再搞一遍即可

单次复杂度 $O(n)$，总复杂度 $O(n\log n)$

27. IOI2024 - Tree [K] ⭐

题面

给定一棵 $n$ 个点的树，树根为 $1$，第 $i$ 个点有点权 $w_i$

$q$ 次询问，每次给定 $[L,R]$，求以下问题的答案：

给每个点分配一个整数权值 $c_i$，使得对于任意 $u$，$u$ 的子树 $c$ 和都在 $[L,R]$ 之间，求 $\sum |c_i|w_i$ 的最小值

$1\le n\le2\times10^5,1\le q\le10^5$

题解

Sol

考虑一次询问怎么做：首先每个叶子上一定是放 $L$，然后非叶子只需要处理子树和 $>R$ 的情况

经过一些分析（如上下界网络流），可以得到如下问题：

每个非叶节点有 $(儿子个数-1)\times L$ 的流量，并且向父边连 $R-L$ 流量的边，并且每个点向汇点连 $\infty$ 流量，$w_i$ 费用的边，这张图的最小费用最大流加上叶子的贡献即为答案，认为 $fa_1=0$ 且 $w_0=0$

这个问题不是很好做，因此我们可以考虑一些情况，比如 $w_i\le1$ 的问题

$w_i\le1$ 的问题是好做的，因为我们相当于只要求最多能有多少流量匹配了 $w_i=0$ 的点，而求这个我们 $w_i=0$ 的点全删掉，对于每个连通块，设其总流量为 $C$，那么最后会贡献 $\min(R-L,C)$ 个匹配 $w_i=0$ 的流量，流向这个连通块最浅点的父亲

那么处理一下注意到 $C=c\times L$，那么我们记录一下对于原图每个 $c$ 有多少个连通块，对每个 $[L,R]$ 算的时候用一些前缀和即可做到 $O(1)$ 查询

然后考虑一般的情况，我们可以考虑一下，用如果我们用同样的方式对每个 $x$ 求解，匹配 $w_i\le x$ 的数有多少个，那么感性理解一下，这些解是包含的，因此可以同时取到，那么我们直接加起来

28. IOI2024 - Message [K] ✨

题面

通信题，你需要实现 Aisha 和 Basma

Aisha 首先会收到一个长为 $S$ 的 01 串 $M$，以及一个长为 $31$ 的 01 串 $C$，满足 $C$ 恰好有 $16$ 个 $0$

Aisha 需要用 $T$ 次 send_packet 将这个传递给 Basma，每次 send_packet 可以发送一个长为 $31$ 的 01 串，但这其中 $C_i=1$ 的位置可能会被交互库修改

Basma 收到的信息只有所有 Aisha 发送的 01 串（按顺序，被交互库修改过的），Basma 需要返回正确的 $M$

$1\le S\le1024$，$T\le66$ 时获得满分

题解

Sol

注意到 $M$ 其实是 1025-bit 的信息。

83~87 分做法

考虑传递 $C$ 数组

注意到什么都不知道的时候我们可以通过将 $16$ 个 $C_i=0$ 的位全填一样的数，通过众数传递 1bit 的信息

这是非常浪费的，因为我们必须使用所有 $C_i=0$ 的位，才能把 1bit 传过去

而如果我们得到了一个 $C_i=0$ 的位，那么我们每次用这个位置可以发送 1bit 的信息，剩下的位置可以用来填信息位

那么我们先用 $4$ 次操作，传出第一个 $C_i=0$ 的位（前 $16$ 个中一定有一个），然后接下来的 $29$ 次操作内用这个位把剩下的 $C$ 全传过去，其余 $15$ 个位传信息，之后 $16$ 个位全用来传信息

后面用 $66$ 次操作一共可以传 $66\times16-29=1027$ 个 bit，那么加上前面的 $4$ 次就是 $70$ 次

100 分做法

注意到 $66\times16-1025=31$，即我们要用 $31$ 个 bit 传递 $C$ 数组

考虑什么样的 31-bit 信息能描述 $C$

直接传肯定不行，因为在我们不知道 $C_i=0$ 的位的情况下会被扰乱

尝试找一些不会被扰乱的信息，注意到如果我们能让每个 0 指向下一个 0，那么这个信息传递过去之后，我们只要找到大小为 $16$ 的环即可

具体地，设 $d_i$ 表示一个 0 到循环意义下下一个 0 的距离，那么对于每个 $C_i=0$ 的位，前 $d_i-1$ 次信息这个位为 0，第 $d_i$ 次信息这个位为 1，其余位全用来填信息

这样我们可以得到每个 $i$ 指向了一个位置，取出来一定是一个基环树森林，而这个基环树森林至多只有一个 $16$ 的环，环上的就是所有 $C_i=0$ 的位置

然后解码信息就是容易的了

29. USACO2024DEC P - Maximize Minimum Difference [E]

题面

对于一个 $1\sim n$ 的排列 $p$，定义 $f(p)=\min_{i=1}^{n-1}|p_i-p_{i+1}|$，其中 $S$ 定义为 $f(p)$ 取到最大值的所有排列 $p$ 组成的集合

$t$ 组数据，每组数据给定 $k$ 个限制，形如 $p_i$ 必须等于 $j$，求 $S$ 中有多少排列满足这 $k$ 个限制

$2\le n\le2000,1\le tn\le2\times10^4$

题解

Sol

$\max f(p)=\lfloor\frac n2\rfloor$，对于 $n$ 为偶数只有两种构造方案，下面只讨论 $n$ 为奇数的情况

注意到 $m=(n+1)/2$ 比较特殊，如果我们把 $m$ 的数视作大数，那么 $m$ 是唯一一个能同时和小数和大数连的，并且 $m$ 只能和 $1$ 与 $n$ 相连

讨论 $m$ 的位置：

$m$ 在开始，下一个填的是 $n$：
考虑后面的怎么填，注意到此时后面每个位置是小是大已经确定了
令 $D=\lfloor n/2\rfloor$考虑按照 $m-1,m-1+D,m-2,m-2+D,\cdots$ 的顺序依次加入这些数，可以发现每个小数只能和前面的或下一个大数相连，每个大数只能和前一个或后面的小数相连，那么手玩一下，可以发现一组 $(m-i,m-i+D)$ 要么放在此时最左边，要么放在最右边，最后 $1$ 填在中间
那么这个问题可以用 dp $O(n^2)$ 解决
这种情况有 $m$ 在开头/末尾，下一个填的是 $1/n$ 共四种对称情况
$m$ 不在开始：
注意到此时 $m$ 一定被 $1$ 和 $n$ 围着，那么开头末尾一定恰好一大一小，不妨假设开头是小，依然按照上面的顺序填数，可以发现我们需要继续讨论两种情况：
- $m$ 在奇数位置：
  此时左边是 小大小大小...小大小，右边是 大小大小大...大小大
  注意到我们填数的时候如果想满足限制，那么只能先填左边，把左边全填完，然后有一个小大对被拆掉了，多出来的这个大数可以填到右边的任意一个位置，之后右边也是类似的了
  那么也就是说我们的过程可以描述成这样：
  - 左边从 $(m-1,m-1+D),(m-2,m-2+D),\cdots$ 开始从外往里填，填到最后用下一个小数拼上
  - 右边从 $(D+2,2),(D+3,3),\cdots$ 开始从外往里填，填到最后用下一个大数拼上
  可以用 $O(n^2)$ dp 解决
- $m$ 在偶数位置：
  此时左右都是 小大小大...小大，我们的过程就是每次从 $(m-1,m-1+D),(m-2,m-2+D),$ 填，每次可以选择填在两个序列之一的开头，这个可以用 $O(n^2)$ dp 解决

那么我们得到了一个 $O(n^3)$ 的做法

考虑我们执行很多次的 dp 其实可以被描述成如下的问题：

有两个递降序列，某个值域区间内的数都在两个序列中恰好出现了一次，有一些位置已经固定，你需要算将剩下的填进去的方案数

这个可以用组合数 $O(n)$ 解决

那么对于 $m$ 在开始和 $m$ 在偶数位置的情况，我们已经可以 $O(n)$ 解决了

对于 $m$ 在奇数位置的情况，相当于是两个上述问题，但是我们需要枚举中心

注意到如果把不存在限制的极长区间缩在一起，那么这个问题就类似于一个序列，要找到一个中心，使其关于这个中心，左边递降，右边递增，这个显然是 $O(1)$ 的，因此我们只需要对 $O(1)$ 种不同的中心做这个问题，也可以 $O(n)$ 解决

总复杂度 $O(n^2)$

30. IOI2024 - Sphinx [K]

题面

交互题。

给定一张 $n$ 个点 $m$ 条边的无向图，点有 $[0,n-1]$ 内的颜色，你知道图结构，但是不知道每个点的颜色

你可以向交互库提出询问，一次询问你需要提供一个长为 $n$ 的数组，值域为 $[-1,n]$，交互库会返回，所有 $-1$ 的点保留原来的颜色，否则赋值成数组中的颜色，会产生多少个同色连通块

询问之间相互独立。

你需要求出每个点的颜色。

$1\le n\le250$，询问次数最多 $2750$ 次

如果你不能求出每个点的颜色，但是返回的颜色满足两个点颜色相等当且仅当其在实际答案中颜色相等，则你可以得到 $50\%$ 的分数

有 $n\le50$，链，完全图的部分分

题解

Sol

考虑 $50\%$ 怎么做：我们可以增量构造，每次加入一个点 $i$，求出其和 $1\sim i-1$ 的点的等价关系

这个是容易求的，我们只要每次二分，求出任意一个和 $i$ 相等的边即可，相等了将其缩起来，那么这样的复杂度就是 $n\log n$ 的

那么接下来考虑如何推出每个等价类的颜色

如果做了链的部分分，我们可以按点的奇偶分类，然后对于所有同一奇偶性的点，扫每个颜色，然后整体二分出所有等于这个颜色的点，复杂度是 $n\log n$ 的

而对于整体的图，我们也可以选出一个独立集然后这样搞，但是我们不会把图划分成独立集。

注意到我们其实不用独立集的限制，我们需要只是当前询问集合内的点，不会产生不必要的相等关系

那么我们首先缩掉所有等价类，接下来取出任意一棵 dfs 树进行黑白染色，容易发现这样每个点至少有一条异色出边，而相邻点一定颜色不同，那么我们对黑集合和白集合分别二分即可，复杂度 $n\log n$