task10

[TOC]

1. 湖北省选模拟 2024 - 花神诞日 [E]

题面

给定 $n$ 个互不相同的整数 $a_1,a_2,\cdots,a_n$，以及常数 $k_1,k_2$

求有多少种方案将这些数划分为两个非空集合 $S,T$，使得 $S$ 中任意两个数的异或 $\ge k_1$，$T$ 中任意两个数的异或 $\ge k_2$

对 $10^9+7$ 取模

$1\le n\le2\times10^5,1\le k_1,k_2,a_i<2^{60}$

题解

Sol

Flamire 做法

分讨。

不妨设 $k_1\le k_2$，把 $k_1$ 和 $k_2$ 看作两个限制：

如果 $a_i\oplus a_j<k_1$，那么 $a_i$ 和 $a_j$ 一定不能在同一个集合
如果 $a_i\oplus a_j<k_2$，那么 $a_i$ 和 $a_j$ 一定不能同时属于 $T$

这个和原题是等价的

令 $h_1=\text{highbit}(k_1),h_2=\text{highbit}(k_2)$

对于字典树上每个 $\le h_1$ 的子树，其中任意两个数不能属于同一个集合，那么 $\le h_1$ 的子树一定最多只有两个元素，对于字典树上每个 $\le h_2$ 的子树，其中任意两个数不能同时属于 $T$，也就是说最多只有 $1$ 个属于 $T$ 的元素

那么我们需要决策的事情就少了很多，具体地，首先我们可以将所有 $a$ 按比 $h_2+1$ 位更高的数分为独立的子问题，答案就是所有子问题的乘积

对于一个子问题内，我们可以分为 $h_2$ 位为 $0/1$ 的 $v_{0},v_1$，其中 $v_0$ 和 $v_1$ 都至多有一个属于 $T$ 的元素

如果 $h_1=h_2$，那么 $|v_0|\le2,|v_1|\le2$，直接指数级暴力

否则 $v_0$ 和 $v_1$ 之间一定不会有 $k_1$ 产生的限制，现在我们希望求出 $v_0,v_1$ 中每个元素是否能作为本集合属于 $T$ 的元素，那么我们需要支持查询不包含某个数的异或最小的数对，这个可以用 trie 树维护

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

题解做法

对于 $a<b<c$，有 $a\oplus c\ge\min(a\oplus b,b\oplus c)$

将 $a$ 排序，那么问题转化为，我们需要将其拆成两个子序列 $b,c$，使得相邻数的异或最小值分别大于等于 $k_1,k_2$

令 $dp_{i,x,y}$ 表示前 $i$ 个数，$b$ 的上一个数为 $x$，$c$ 的上一个数为 $y$

$x$ 和 $y$ 至少有一个是 $a_i$，另一维用 trie 优化，复杂度 $O(n\log V)$

2. 湖北省选模拟 2024 - 永恒 [K]

题面

给定一个 $n\times m$ 的矩阵，每个元素为 0~9 或 #，$q$ 次操作，每次操作为两种中的一种：

1 x y c，将矩阵 $(x,y)$ 位置的元素修改为 $c$
2 sx sy tx ty v，求从 $(sx,sy)$ 开始走到 $(tx,ty)$，每步走到一个四联通的格子，走出一个不经过 # 的路径（不一定简单），将路径上经过的元素顺次连接起来得到一个权值，这个权值是否有可能模 $1145141$ 余 $v$

$1\le n,m\le500,1\le q\le2\times10^5$

题解

Sol

唐。

这个看起来就和同余啥的相关，因此我们考虑环相关。

对于一个环，如果原来的权值是 $x$，不妨设走完会变成 $ax+b$，我们考虑不断绕这个环会产生什么影响，绕 $i$ 次之后我们的值会变成 $a^ix+\frac{a^i-1}{a-1}b$

如果我们绕回来了，说明 $a^ix+\frac{a^i-1}{a-1}b=x$，解一下方程就是 $a^i=1$ 或 $x=-\frac{b}{a-1}$，也就是说如果 $a$ 关于 $p$ 的阶是 $k$，那么我们会将所有数拆成 $(p-1)/k$ 个大小为 $k$ 的等价类，以及一个大小为 $1$ 的等价类

如果我们取相邻的两个数组成的环的话，$a=100,k=2$，也就是说我们所有数被划分为了三个等价类

注意到这个限制很强，我们不妨大胆猜测一下如果一个点周围有两种不同的数，也即组成两种不同的长为 $2$ 的环，我们就能凑出所有数

证明如下：

令 $p=1145141$，注意到 $p$ 是质数，设当前数为 $b$，周围两个数分别为 $a,c$，首先在路径上走出足够长的 $\overline{babababa\cdots babab}$，接下来考虑调整这个数得到任意 $[0,p)$ 内的数，我们能进行的操作是将任意一个 $a$ 改为 $c$

找到所有位权为 $10^{(p-1)k}$ 的位，那么改变这些为会让最后模 $p$ 的值加上 $c-a$，而 $p\nmid c-a$，因此一定可以将当前的数调成任意其他数

不满足这个条件的情况就是黑白染色是，黑色的权值都相同，白色的权值都相同，这种情况显然等价类无法合并，也就是说我们需要根据值来判断是否属于同一个等价类

线段树分治维护即可

3. 湖北省选模拟 2024 - 沉玉谷 [S]

题面

给定 $a_1,a_2,\cdots,a_n$，有一个计数器 $K=0$

你需要反复进行如下操作，直到 $a$ 被删空：

选择一个 $[l,r]$，使得 $a[l:r]$ 内元素全相等，令 $K\leftarrow10^4K+10^2l+r$，并将这段区间从 $a$ 中删除，后面的补齐

求最后得到的 $K$ 有多少可能取值，对 $10^9+7$ 取模

$1\le a_i\le n\le50$

题解

Sol

Flamire 做法

显然是什么高次方 dp。

注意到补齐对下标的影响可以忽略不计，因为我们一定能根据补齐后的下标还原出补齐之前的下标

令 $dp_{l,r,i,v}$ 表示区间 $[l,r]$，删了 $i$ 次删空，外面套了一个删 $v$ 的操作（也即我们可以留下 $v$ 这种数不删）

考虑 $a_l$ 的去向，转移有两种：

如果 $a_l=v$，那么我们可以让 $a_l$ 留到最后，即从 $dp_{l+1,r,i,v}$ 转移过来
否则 $a_l$ 被删除，我们枚举删除时的右端点，需要满足 $a_k=a_l$，再枚举两边分别用了多少次操作，从 $dp_{l+1,k-1,j,a_l}\times dp_{k+1,r,i-1-j}\times\binom{i}{j}$ 转移

复杂度 $O(n^6)$，但是直接飞过去了。

题解做法

注意到之前那个做法存一个 $v$ 看起来很愚蠢，考虑不要这一维，我们直接用 $a_l$ 表示

具体地，令 $dp_{l,r,i}$ 表示区间 $[l,r]$，删了 $i$ 次删空

有以下两种转移：

如果 $a_r=a_l$，我们可以将其纳入删除 $a_l$ 的这次操作，从 $dp_{l,r-1,i}$ 转移
否则一定存在一个端点，使得两边的操作互不影响，枚举这个断点 $m$，以及两边用的次数，由于需要保证计数唯一，我们需要保证 $[l,m]$ 是一整段，即 $a_l=a_m$，从 $dp_{l,m-1,j}\times dp_{m+1,r,i-j}\times\binom {i-1}{j-1}$

复杂度 $O(n^5)$

4. 省选联考 2024 - 最长待机 [E/K] ✔️

题面

。。。

太长了，自己看吧。

题解

Sol

套壳还是差不多得了。

设 $\omega$ 表示一个输入的数，我们可以推出如下运算律：

如果 $x>y$，那么 $w^x+w^y=w^x$
如果 $x\le y$，那么 $\omega^x+\omega^y>\omega^y$
$\omega(\sum a_i\omega^i)=\omega^{d+1}$，其中 $d$ 为最大满足 $a_d\neq0$ 的项

更多细节可以参照 this，感觉这部分和 oi 没啥关系于是不展开写了。

所有函数形成了一个树形结构，我们需要维护的是如下过程：对于一个函数 $u$，设其运行时间为 $f_u$，那么我们有需要进行操作：

$f_u\leftarrow f_{v_1}+f_{v_2}+\cdots+f_{v_k}\\f_u\leftarrow\omega\cdot f_u(e_u=1)$

每一个 $f$ 都是一个关于 $\omega$ 的升幂多项式，最后得到询问的 $f_k$ 后，答案就是 $1+\sum\max(i,1)a_i$（只有一项的话外面的 $1$ 可以不加）

那么我们需要做的就是快速维护这件事情

如果没有 $e=1$ 的点，那么这就是求序列内前缀最大值的信息，这指引我们考虑楼房重建线段树

考虑我们的过程相当于：令 $h_i$ 表示 $i$ 到根的 $e_i=1$ 的点数量，那么每个点最后贡献的次数就是 $h_i-h_{fa_k}$（可以视作 $h_i$），我们要算所有是前缀非严格最大值的 $\max(h_i,1)$ 之和，以及有多少非严格最大值，同时，对于所有 $e_u=1$ 代表的子树区间，我们只保留其中的最大值

进行如下转化：

把问题放到欧拉序上，对于每个点 $u$，如果 $e_u=0$，则认为 $in_u$ 和 $out_u$ 的位置都为空，否则在 $in_u$ 和 $out_u$ 的位置上插入一对括号，表示括号内部的数只取最大值

那么现在我们节点的值就从最大值变为：

将所有匹配括号操作完后，左边的 ) 的数量，以及这些 ) 括住的最大值
中间的元素的最大值
将所有匹配括号操作完后，右边的 ( 的数量，以及这些 ( 括住的最大值

这样可以支持合并，查询的时候我们传一下后两个信息即可

细节比较多，复杂度 $O(n\log n+m\log^2n)$

5. USACO24JAN - Island Vacation [E]

题面

给定一棵 $n$ 个点 $m$ 条边的无向边仙人掌，每个点有一个属性 $p_i$

你现在在节点 $1$，你会重复如下过程：

如果当前没有出边，结束过程
以 $p_i$ 的概率结束过程
从当前出边中选择一条走过去，并将这条边拆掉

对 $i=1,2,\cdots,n$，求在 $i$ 结束过程的概率，对 $10^9+7$ 取模

$2\le n\le10^4$

题解

Sol

shaber。

缩点，令 $g_u$ 表示进入一个点的子树并回来的概率，可以用一次 dfs 求出来，转移的时候需要做背包然后乘一堆乱七八糟的系数。

令 $f_u$ 表示到达一个点的概率，可以再用一次 dfs 从 $g$ 推出来，转移的时候需要再做背包然后乘一堆乱七八糟的系数

然后就可以算答案了，细节很多，全让你唐完了

复杂度 $O(n^2)$

6. USACO24JAN - Merging Cells [S]

题面

给定 $c_1,c_2\cdots,c_n$，初始时第 $i$ 个元素的标号为 $i$，每一时刻，会随机选择两个相邻的元素，将它们合并，合并遵循如下规律：

合并完元素的值为 $c_a+c_b$
设 $c_a$ 的标号为 $x$，$c_b$ 的标号为 $y$，如果 $c_x\neq c_y$，那么新的标号为 $c$ 值更大的标号，否则标号为 $\max(x,y)$
合并完后两边的元素补齐

最后剩下一个元素，对每个 $i=1,2,\cdots,n$，求最后剩余的元素标号为 $i$ 的概率，对 $10^9+7$ 取模

$2\le n\le5000$

题解

Sol

考虑对一个 $i$ 怎么求，初始时标号为 $i$ 的节点一定是 $[i,i]$，接下来我们每一步可以在左边或右边拼上一个区间，满足这个区间的和小于（等于）当前的和

那么我们得到了一个单次 $O(n^3)$ 的 dp，总复杂度 $O(n^4)$

经典套路，反向一下转移，只用做一次 dp，复杂度 $O(n^3)$

把这个 dp 用前缀和优化，复杂度 $O(n^2)$

7. USACO24JAN - Mooball Teams III [S]

题面

给定 $n$ 个点 $(x_i,y_i)$，求有多少方式给这 $n$ 个点每个点染成 R，B，. 中的一种使得：

R 和 B 均至少有一个点属于这种颜色
存在一条平行于坐标轴的直线，使得所有 R 点在这条直线的一侧，所有 B 点在这条直线的另一侧

求方案数，对 $10^9+7$ 取模

$1\le n\le2\times10^5$，保证 $x_i,y_i$ 分别为 $1\sim n$ 的排列

题解

Sol

考虑枚举每条横线和竖线，求 R 和 B 分属两边的方案数，这是 trivial 的

但是会算重，先用点-边容斥把两边的全容斥掉，那么我们就剩下一种方案可以同时被横线和竖线切开的算了两次

这种我们对横线扫描线，然后钦定竖线经过右下角的某个点，用线段树维护每条竖线的方案数，做完了之后再做一遍左下角-右上角的，复杂度 $O(n\log n)$

8. USACO23DEC - Cowntact Tracing [K] ⭐

题面

给定一棵 $n$ 个点的树，以及一个这 $n$ 个点的子集 $S$，$q$ 次询问，每次给定常数 $L$，求以下问题的答案

最少选出多少个点，满足距离这些点 $\le L$ 的点的集合的并集恰好为 $S$，求最小点数或判断无解

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

题解

Sol

外星人贪心。

当 $S$ 为全集时，这个问题有一个显然的贪心：我们直接从子树向上贪心，如果当前不选会导致下面的点无法被覆盖就选当前点，不难发现这样是优的。

考虑 $S$ 不为全集，那么有一些点不能被覆盖，也即限定距离 $\le L$ 的范围内的点都不能被选择

如果有一个需要被覆盖的点，距离最近能选择的点的距离 $>L$，那么就是不合法的，同时不难发现这是不合法的充要条件

考虑扩展上面的贪心，向上扫的时候，我们需要选择当前点 $u$ 当且仅当子树内最深的未覆盖点 $c$ 满足 $dis(c,fa_u)+d_{fa_u}>L$，其中 $d_{fa_u}$ 表示距离 $fa_u$ 最近的可选点的距离，这里选择 $u$ 指选择距离 $u$ 最近的可选点

这样做看起来很对（

注意到这里距离 $u$ 最近的点一定在 $u$ 子树内，否则就存在点满足 $dis(c,fa_u)+dis(fa_u,w)\le L$，因此不会出现子树之间的选择相互影响的情况

模拟这个贪心即可，复杂度 $O(qn)$

9. USACO23DEC - A Graph Problem [S]

题面

给定一张 $n$ 个点 $m$ 条边的无向联通图，边的边权为 $1\sim m$ 的排列，你需要模拟以下过程：

初始 $S=\{s\}$，$h=0$
每次选择一个向 $S$ 中有连边并且连边权值最小的点 $x$，设最小连边为 $e$，令 $h\leftarrow 10h+e,S\leftarrow S\cup\{x\}$

对 $s=1,2,\cdots,n$，求最后 $h$ 的值，对 $10^9+7$ 取模

$2\le n\le2\times10^5,n-1\le m\le4\times10^5$

题解

Sol

Flamire 做法

prim。

由于边权互不相同，所以最小生成树唯一，只用考虑这棵树上的问题

考虑换根，经过一条权值为 $w$ 的边相当于是找到第一个 $=w$ 的位置 $X$，第一个 $>w$ 的位置 $W$，设原序列为 $AXBW\cdots$，新序列为 $BXAW\cdots$，直接平衡树维护即可

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

题解做法

prim 不好考虑，我们考虑 kruskal，每次从小到大加边 $(u,v)$，设两边的连通块为 $S,T$，那么 $S$ 中的点一定是先扩展完 $S$ 内的所有点，再扩展加入的边，再按照 $v$ 的序列扩展 $T$，$T$ 中的点同理

那么我们需要支持查询一个点的值，并给一个连通块打上 $ax+b$ 的 tag，这个我们可以直接把 tag 打在并查集上，路径压缩的时候合并 tag

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

10. USACO23DEC - Train Scheduling [E]

题面

有 $n$ 辆火车，每个火车的类型为 A 或 B，你需要安排火车，满足如下条件：

第 $i$ 辆火车必须在 $t_i$ 时刻出发，设它的出发时间为 $a_i$，那么 $[a_i,a_i+T)$ 时间段它将持续在其轨道上
同一时刻只有一种类型的火车可以在轨道上，但对火车的数量没有限制

求 $\sum a_i-t_i$ 的最小值

$1\le n\le5000,1\le T\le10^{12},0\le t_i\le10^{12}$

题解

Sol

这个看上去就是 dp，首先对火车排序，不难发现火车的相对顺序一定不变

我们不妨直接设 $dp_{i,j}$ 表示送完了 $A_i$ 和 $B_j$ 这两辆火车，最小的时间

但是这样没有办法转移，因为我们不知道 $A_i$ 和 $B_j$ 送走的时间，那么不妨直接假设 $A_i$ 和 $B_j$ 是准点送走的，考虑转移

不妨假设 $A_i+T>B_j+T$，那么我们有两种选择：

将 A 的时间一直延长到 $A_{i+1}+T$，把 $A_{i+1}$ 也准点送走
将 $[A_i+T,A_i+2T)$ 的时间划给 B，把当前耽误的 B 全部送走

第二种转移依然无法处理，我们无法表示的状态是什么样的：一定是从当前的 $dp_{i,j}$ 开始，不断交替给 A 和 B 分别安排 $T$ 的时间，并且可以发现，如果某个 $T$ 的时间没有送走任何火车，那么一定是不优的，也就是说我们最多会交替 $n$ 次

而这个交替的过程中只和 $A_i,B_j$ 中较大的相关，因此我们可以新设状态 $f_i$ 表示当前 $A_i$ 准点送走，并且时间 $[A_i+T,A_i+2T)$ 属于 B，最小的时间，对于 B 同理设 $g_i$，这个转移可以暴力交替 $T$ 段，单个状态 $O(n)$

总时间复杂度 $O(n^2\log n)/O(n^2)$ 取决于是否愿意把 upper_bound 之类的东西搞掉

11. 省选联考 2024 - 虫洞 [K] ✨

题面

。。。

太长了，自己看吧。

题解

Sol

结论：合法的连通块任意两个点等价，并且两个点能连边当且仅当它们同构

令 $F_i(x)$ 表示 $i$ 个点连 $x$ 次边能形成的无标号不同连通块种类数

有转移式：$F_i=\sum_{j|i}F_j\cdot jx$，即枚举上一次一条边连接的两个连通块的大小 $j$，那么对于第 $i$ 个连通块连向第 $i+1$ 个连通块的边，只有 $\frac ij$ 连回 $1$ 的需要决策，其余均可以通过旋转 $i+1$ 使其同构

解一下方程变为 $F_i=\frac1{1-ix}\sum_{j|i,j\neq i}F_j\cdot jx$

注意到 $F_i$ 的分母为 $\prod_{j|i}\frac1{1-jx}$，将 $F_i$ 拆为部分分式维护，可以做到 $O(n\log^2n)$

把 $F$ 点乘 $(i-1)!$ 即可得到有标号连通块数，dp 或 exp 即可做到 $O(n^2)/O(n\log n)$

对于初始图有边的情况，我们把同一个等价类的分一组，做一个每个点初始大小为 $S$ 的问题，这个需要改一下上面式子中的系数

需要哈希判断连通块同构，由于初始的图满足条件，因此可以考虑直接从任意一个点开始 dfs，然后用 dfs 序给点标号进行哈希

12. CF1172E - Nauuo and ODT [E]

题面

给定一棵 $n$ 个点的树，点有颜色，颜色为 $[1,n]$ 内的整数，定义 $dis(i,j)$ 为 $i$ 到 $j$ 上经过的点不同颜色种数

$m$ 次修改，每次修改一个点的颜色，求 $\sum_{u=1}^n\sum_{v=1}^ndis(u,v)$

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

题解

Sol

题解区都是 lct，所以我们应该使用树剖来解决这个问题。

首先容斥一下，对每个颜色考虑，那么我们需要做的事情就是每次加一个点或删一个点，求所有连通块的 $siz^2$ 之和

注意到我们操作一个点产生的影响是 $O(deg)$ 的，我们需要考虑一些手段来优化，可以尝试每个点存所有儿子的信息，但是这样做会使修改难以维护，因此我们另一种手段：考虑在每个点存所有轻儿子信息

即，我们在每个点维护 $vsiz_u$ 和 $vsiz2_u$，分别表示轻儿子所属的连通块大小之和，以及大小平方和

那么查询一个点所属连通块大小，就是不断往上跳，跳到该连通块内最浅的点，然后查一段 $vsiz$ 的区间和

一次修改对答案的影响就容易维护了，考虑如何维护修改本身

我们修改时需要更改祖先的 $vsiz_u,vsiz2_u$，而这些只有当前节点为轻儿子的时候会更改，因此总共会更改 $O(\log n)$ 次，可以直接暴力跳维护

由于需要区间和，$vsiz_u$ 需要用树状数组维护，$vsiz2_u$ 直接用数组维护即可

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

13. CF1254E - Send Tree to Charlie [S]

题面

给定一棵 $n$ 个点的树，初始第 $i$ 个点的权值为 $i$，接下来进行 $n-1$ 次操作：

每次选定一条未被删除的边 $(u,v)$，交换 $u$ 和 $v$ 的权值，并删除这条边

现在给定最后的权值序列，有些位置空缺，求有多少方式填补空缺得到一种可能的最后权值序列，对 $10^9+7$ 取模

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

题解

Sol

根据最近某场 arc 的结论，如果全是空缺，那么答案即为 $\prod deg_i!$

对于一个权值 $i$，如果它从 $u$ 到了 $v$，不妨设其经过的路径为 $(u,p_0),(p_0,p_1),\cdots,(p_{k-1},p_k),(p_k,v)$

那么 $(u,p_0)$ 一定是 $u$ 的邻边中第一个被交换的，$(u,p_0),(p_0,p_1)$ 在 $p_0$ 的邻边中被交换的顺序一定相邻并且按这个顺序

以此类推可以得到限制，容易发现限制最多有 $2n$ 条，大于这么多就可以退出

把这些限制放到一起判一下合法即可。

算答案就是找到每个点限制出来的链数，求一个阶乘的乘积即可

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

14. CF1656G - Cycle Palindrome [E]

题面

给定 $a_1,a_2,\cdots,a_n$，你需要找一个 $1\sim n$ 的排列 $\sigma$ 使得序列 $b_i=a_{\sigma_i}$ 是一个回文串

给出构造或判断无解

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

题解

Sol

首先把出现次数不合法的情况判掉。

手玩一玩除了中间的元素最开始就必须连成自环，可以发现可操作的空间很大，很难无解。

那么我们大胆猜测，只要中间的那个元素不会一开始连出自环，就一定有解

首先，对于 $n$ 为奇数的情况，中间那个元素存在一种选择不连成自环，那么我们让中间连向这个元素，就可以把这两个点缩在一起，转化成 $n$ 为偶数的情况

对于 $n$ 为偶数的情况，我们首先将回文串的限制视作，每一个 $a_i$ 的值组成了一个点的集合，而每对 $i$ 和 $n+1-i$ 必须指向同一个集合里的点

如果 $n=2$ 显然有解。考虑 $n\ge4$ 的情况。

那么我们只要把 $1$ 和 $n$ 的出边安排上就可以缩为规模更小的问题，那么一定能找到两对不交的数 $(a,b)(c,d)$，使得它们分别属于同一个集合，而这四个数当中至少有一个不与 $1$ 和 $n$ 相等的，我们选择包含一个这样数的集合，分类讨论一下一定能连出来一种不成环的方案

按照构造模拟即可

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

15. CF1427G - One Billion Shades of Grey [K] ✔️

题面

给定 $n\times n$ 的方阵 $a$，保证最外面一圈都是 $[1,10^9]$ 的正整数，中间的数可能是 $-1$ 或 $0$

你需要给所有 $a$ 为 $0$ 的位置赋值一个 $[1,10^9]$ 的整数，所有不包含 $-1$ 的相邻元素对的差的绝对值之和最小

求最小值

$3\le n\le200$

题解

Sol

别看见什么都想切糕。

注意到所有元素只可能取边界上某个格子的值，那么考虑对值域分段处理，首先考虑只有两种值 $1,2$ 怎么处理：

我们将 $S$ 对所有 $1$ 连 $\infty$ 边，所有 $2$ 对 $T$ 连 $\infty$ 边，相邻格子之间连 $1$ 的双向边，不难发现这张图的最小割就是最小答案

那么不妨猜测对于每个值 $k$，我们把 $>k$ 的视作 $2$，$\le k$ 的视作 $1$，求出答案全部加起来就是原问题的答案，事实上这是对的，感性理解一下就是我们的源点在不断增加，汇点不断减少，那么源点能到的点也在不断扩张

由于我们只需要对每个值域段跑一边，所以现在复杂度是 $O(n\cdot n^3)=O(n^4)$ 的

考虑优化，注意到我们每次改变是将一个汇点变为源点，改动非常小，因此可以考虑使用上一次最大流的残量网络求下一张图的最大流，即网络流退流

具体地，最大流一定形如若干条不交的从源点到汇点的路径，当把 $u$ 从汇点变为源点时，退掉所有连向 $u$ 的路径（最多 $3$ 条），然后将 $u$ 变为汇点，再进行增广

注意到流量每增加 $1$，也即增广一轮，复杂度是 $O(m)=O(n^2)$ 的，而不难发现流量最多增加 $O(n)$ 次，因此总复杂度是 $O(n^3)$

事实上，可以发现新图的最大流 $\le$ 原图最大流 $+3$，因此每一轮流量最多 $-3+6$，也是 $O(n^2)$ 的

16. CF1466H - Finding satisfactory solutions [S]

题面

自己看。

题解

Sol

小唐题。

题面说唯一确定一个排列，那么考虑怎么确定这个排列

提出如下一种算法：

先将每个人连向自己最喜欢的物品建一张图，那么成环的人一定会选最喜欢的物品，否则这个环上的人可以凑一块

那么将这些人和这些物品全部删除，继续做这件事情，直到所有人都成环

容易验证这个是符合题目条件的。

考虑如何求方案数，容易发现环长大小相等的环都是等价的，因此我们可以只记录一下每种长度的环有多少个，爆搜一下就可以发现当 $n\le40$ 时状态数最大只有 $1440$

令 $dp_S$ 表示当前只剩 $S$ 中的环的方案数，转移可以枚举最喜欢的物品形成了哪些环，然后容斥，从 $T\subset S$ 转移，转移系数随便推推就好。

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

17. CF1785F - Minimums or Medians [E]

题面

给定 $S=\{1,2,\cdots,2n\}$，每次可以选择删除 $S$ 中最小的两个元素或者删除 $S$ 中最中间的两个元素

求 $k$ 步操作后能得到多少不同的 $S$ 集合，对 $998244353$ 取模

$1\le k\le n\le10^6$

题解

Sol

我们只关心最后的集合，那么手玩一下最后会形成什么结构的集合

可以发现最后删除的一定会形成若干连续段，并且第一个连续段较为特殊，考虑枚举第一段的长度 $2a$，那么中点会不断向右移，我们可以猜测最后删除的位置是在一段区间内的

具体地，我们再枚举以 $n$ 为中心的段的长度 $2b$，那么剩下的段一定是任意分布在 $[n+b+1,n+k]$ 内，且每段长度都为偶数，把长为 $2$ 的段缩到一起，这就是一个组合数，枚举 $a,b$ 就可以单次 $O(1)$ 计算

把求和式写出来是若干个组合数前缀和，可以组合数前缀和

复杂度 $O(k)$

18. NOIP2021 - 棋局 [E]

题面

自己看。

题解

Sol

唐。

不难发现最难处理的是道路 $3$，我们需要统计一个连通块内有多少点，并且支持删点

删点太唐了，改成加点，然后把每个点拆成 $4$ 个，那么每次就是要合并若干个连通块，然后查询一个连通块能访问到多少点

注意到两个连通块内的点可能重复，所以需要使用集合合并的手段，可以使用线段树合并

查询时需要查所有 $col$ 不相等且 $lv$ 更小的点，将下标按照 $col$ 为第一关键字，$lv$ 为第二关键字排序，查询的就是一个区间

我们还需要处理道路 $1$ 和 $2$，容易发现这两个是几乎等价的，本质就是我们有 $l,r,u,d$，分别表示四个方向上最多能走到哪里

道路 $2$ 和道路 $3$ 经过的点可能重复，因此我们把道路 $2$ 和道路 $3$ 均能到的点减掉，这需要我们查询一个集合的某一行/某一列的一个区间内的点的个数因此我们需要存两种下标的线段树，一种以行为第一关键字，一种以列为第一关键字，注意到道路 $2$ 能到的点只有最远的 $4$ 个点可能有棋子，可以手动判掉，否则一定没有棋子，不需要考虑 $col$ 和 $lv$ 的限制，因此直接在新下标上区间查询即可

复杂度 $O((nm+q)\log nm)$

19. CSP-S 2021 - 交通规划 [E]

题面

唉，我真的不想抄了。

题解

Sol

对于一组询问，可以直接暴力网络流。

对于多组询问，不能暴力网络流，显然我们需要考虑一些和 $k$ 相关的事情

注意到最小割可以转成最短路，分析一下就可以知道一定存在一种方式使得我们选出来的是若干条边不交的路径

令 $dp_{l,r,0/1}$ 表示 $[l,r]$，外层颜色为 $0/1$ 割出里面所有东西的最小代价，预处理从 $k$ 个点出发的最短路后容易做到 $O(k^3)$ 转移

复杂度 $O(knm\log nm+k^3)$，被卡常了。

20. NOIP2020 - 移球游戏 [E]

题面

$n+1$ 个栈，前 $n$ 个栈每个栈里有 $m$ 个 $[1,n]$ 的元素，保证每个元素 $i$ 在 $n$ 个栈内总共出现了 $m$ 次

你每次可以选择两个栈 $x,y$，使得 $x$ 非空，且 $y$ 的元素个数 $<m$，将 $x$ 的栈顶弹出并压入 $y$ 的栈顶

给出构造在 $820000$ 次操作内将同种颜色的球都移到同一根柱子上

$2\le n\le50,2\le m\le400$

题解

Sol

注意到用空柱子 $z$，我们可以用 $a+b$ 的代价给柱子 $x$ 长为 $a$ 的前缀和柱子 $y$ 长为 $b$ 的前缀和归并，这里归并指将两个序列组成的集合打乱，重新分为一个大小为 $a$ 和 $b$ 的集合

那么对于 $n=2$ 的情况，我们可以每次将长为 $m/2$ 两个序列归并，手模一下容易得到一个操作次数 $5m\sim6m$ 的做法

套上一个分治，把 $\le M$ 的视作 $0$，$>M$ 的视作 $1$，然后做 $O(n)$ 排序把每个柱子都变为纯色，再进去递归，操作次数就可以做到 $6mn\log n$ 或 $5mn\log n$

21. CSP-S 2020 贪吃蛇 [K] ✔️

题面

有 $n$ 条蛇，能力值分别为 $a_1,a_2,\cdots,a_n$，重复如下过程：

找到能力值最大的蛇 $x$，有多个取原下标最大的
找到能力值最小的蛇 $y$，有多个取原下标最小的
蛇 $x$ 可以决策是否把蛇 $y$ 吃掉，如果把 $y$ 吃掉则蛇 $x$ 的能力值变为 $a_x-a_y$，$y$ 之后将不再被考虑，如果不吃则整个过程结束

当最后只剩一条蛇时过程同样结束

每个蛇会在保证自己不被吃的前提下尽可能多吃其他蛇，求最后过程结束时剩余的蛇的条数

$t$ 组数据，第二组数据开始每组的输入以给定 $k$ 组对上一组数据 $a$ 的单点修改的方式给出

$3\le n\le10^6,1\le t\le10,0\le k\le10^5,0\le a_i,y\le10^9$，保证每组数据的 $a$ 都不降

题解

Sol

厉害题。

首先注意到可以暴力：对每条蛇，先假设它吃，递归下去搜索，如果返回来发现自己被吃了，那么就把这一步改成不吃，需要支持取最小值和最大值，以及插入删除元素，容易用 set 维护，复杂度 $O(Tn\log n)$，无法通过

然后这个暴力和正解没啥太大关系。

其实是有一点关系的，我们希望把 $\log$ 优化掉，所以我们不能用带 $\log$ 的东西，而题目又保证 $a$ 不降，这启发我们尝试用单调性去掉 $\log$

观察性质：如果当前吃完之后 $a_n-a_1$ 不为最小值，那么 $a_n$ 一定会选择吃

证明：$a_{n-1}$ 下一次会吃 $a_2$，而 $a_{n-1}-a_2\le a_n-a_1$，也就是说如果 $a_{n-1}$ 吃了，那它一定会保证自己之后不死，而 $a_n$ 比 $a_{n-1}$ 的配置高，所以它也不会死。如果 $a_{n-1}$ 不吃那 $a_n$ 显然没死

那么我们考虑现在的问题，我们不断模拟吃的过程：

如果当前吃完了不是最小值，那么直接吃，注意这样吃出来的蛇能力值一定是不增的，因此可以用单调队列维护（一个存原来的值，一个存吃出来的值）
如果吃完了是最小值，下一条蛇一定吃这个最小值，因此当前的蛇吃不吃取决于下一条蛇吃不吃，这样一直推下去，直到某一条蛇吃完不是最小值，或者只剩两条蛇，这两种情况都是必吃的，那么推上来就是一层吃一层不吃，可以直接算出最终答案

直接用单调队列模拟这两种情况，容易发现两个队列都具有单调性，可以 $O(1)$ 查询最小最大值，复杂度 $O(Tn)$

22. AGC009D - Uninity [E] ⭐

题面

给定一棵 $n$ 个点的树，求最小点分树深度

$1\le n\le10^5$

题解

Sol

答案是 $O(\log n)$ 的。

Flamire 做法

令 $f_u$ 表示表示 $u$ 子树的最小深度，那么容易发现 $f_u\in\{\max f_v,\max f_v+1\}$，我们只需判断 $f_u$ 是否等于 $\max f_v$ 即可

如果一个 $f_v$ 是最大值，意味着我们这次分治中心一定要选到 $v$ 的子树中，否则包含 $v$ 子树的连通块一定还需要 $f_v$ 次分治

那么如果有两个最大值就寄了。

如果有一个最大值 $f_v$，那么分治中心一定删在 $v$ 内，我们可以把分析重新用在 $v$ 上，得到 $v$ 最多只能有一个 $f_v$ 的儿子，一直推下去，我们删的位置一定是往下走 $f_v$ 链，走到某一个点没有 $f_v$ 的儿子为止

也就是说此时的分治中心与 $v$ 的第一个分治中心是一样的。

那么我们不妨从这个点割开，子树中的已经没问题了，剩下需要考虑的只有包含 $u$ 的连通块，我们希望能继续运用刚才的方法确定，唯一的区别在于 $v$ 的子树里删掉了一个子树，我们仍然需要得到此时的 $f$ 值

这是可以预处理的，具体地，令 $f_{u,0}$ 表示原来的 $f$ 值，$f_{u,i}$ 表示在 $f_{u,i-1}$ 的基础上，再删掉从 $u$ 开始不断走 $f_{u,i-1}$ 最后到的点，剩下的连通块的答案

那么在考虑 $u$ 的时候，我们每次就可以 $O(\text{儿子个数})$ 求出该删哪个子树，顺着模拟即可

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

题解做法

把问题转化为，给每个点分配一个 $tag_u$ 使得如果 $tag_u=tag_v$，那么存在一个 $w$ 在 $u-v$ 的路径上使得 $tag_w>tag_u$

考虑已经填好了 $u$ 子树内的点，要填 $u$ 的点，令 $S_u$ 表示 $u$ 子树内，有哪些点存在到 $u$ 的路径上只有小于该点权值的 $tag$，$S_u$ 为这些点权值的集合，那么对 $tag_u$ 的限制就是：

对于任意儿子 $v$，$tag_u\not\in S_v$
对于任意两个儿子 $v,w$，$tag_u>\max(S_v\cap S_w)$

每次贪心取最小的 $tag_u$ 就是对的，证明可以考虑如下的事情：

定义 $w_u$ 表示 $\sum_{x\in S}M^x$，其中 $M$ 是一个足够大的数

那么我们做的事情相当于要求 $w_u>\sum w_v$，而取最小的合法 $tag_u$ 是最小的合法的 $w_u$

那么复杂度就是 $O(n\log n)$ 的，似乎可以用 __builtin 函数做到 $O(n)$

23. AGC009E - Eternal Average [S]

题面

给定 $n,m,k$，现在有 $n$ 个 $0$ 和 $m$ 个 $1$，每次操作从中选出 $k$ 个数将它们删除，并加入它们的平均数

保证 $k-1\mid n-m-1$，那么最后可以操作到只剩一个数，求这个数有多少种可能，对 $10^9+7$ 取模

$1\le n,m\le2000,2\le k\le2000$

题解

Sol

懵了半天，为什么有人会出这样的 sb 题。

将最后的数写成小数 $0.c_1c_2c_3\cdots c_r$，那么该小数合法当且仅当 $\sum c_i\le m$ 且 $\sum c_i$ 与 $m$ 在模 $k-1$ 意义下同余，并且 $\sum k-1-c_i\le n$ 且 $\sum k-1-c_i$ 与 $n$ 在模 $k-1$ 意义下同余

直接背包，容易做到 $O(nm)$

24. AGC008E - Next or Nextnext [E]

题面

给定 $a_1,a_2,\cdots,a_n$，求有多少 $1\sim n$ 的排列 $p$ 使得 $p_i=a_i$ 或 $p_{p_i}=a_i$

答案对 $10^9+7$ 取模

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

题解

Sol

烂完了。

考虑从 $p$ 中一个环会变成什么。

手模一下可以发现其一定会变成一个基环树外面接一堆链，或者在长度为偶数的情况下，可以变为两个长度相等的环

长度相等的环是一些组合计数。

基环树的情况，我们需要把链拼回环上，判一下链接的点往回走这么长会不会碰到别的链，每个链会乘上一个 $0/1/2$ 的系数

复杂度 $O(n)$

25. CF1942H - Farmer John’s Favorite Intern [E]

题面

给定一棵 $n$ 个点的树，初始每个点上都有 $0$ 个果子，你需要进行一些操作使得第 $i$ 个节点的果子数 $\ge b_i$

依次给定 $m$ 次操作，对每个 $i=1,2,\cdots,m$，求是否能以某种顺序执行前 $i$ 个操作，使得过程中果子个数非负并且最后的树满足条件

每个操作为以下两种中的一种：

1 x v，growth 操作，重复 $v$ 次，每次选择 $x$ 子树中的一个点，或者 $x$ 的父亲，将其果子数 $+1$
2 x v，harvest 操作，重复 $v$ 次，每次选择 $x$ 子树中的一个点，将其果子数 $-1$

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

题解

Sol

注意到这是一个匹配问题，我们询问的是右部点能否完全匹配

建模 1（Flamire）

注意到网络流等于最小割，因此我们的目的是割掉一些 g，h，与 b 使得剩下的操作没有两个能匹配

匹配即有 g 和 h 呈祖先关系，或 g 为 b 儿子或祖先，我们需要保证没有这种情况

g 和父亲有关，所以我们把点 $u$ 的 g 放到父亲处理，此时可以发现一种类型是否要割只和子树中有哪些类型的边没有割有关：

如果子树内有 g，那么不能选 h
如果子树内有 h 或 b，那么不能选 g

直接用 $2^2=4$ 种状态表示即可

注意到子树至少可以保留一种不割，所以可以再剪掉一个状态

建模 2（le0n）

考虑求 $|N(S)|-|S|$ 的最小值

令 $S$ 为 h 和 b 的子集，那么容易发现如果一个 h 选了，那么子树中所有减操作都选一定不劣

分三种状态：子树内一个减操作也没选，子树内选了一些减操作，子树内所有减操作全选了

把上面任意一种建模套上 ddp 即可

复杂度 $O(n\log^2n\cdot3^3)/O(n\log n\cdot3^3)$

26. AGC010E - Rearranging [E] ⭐

题面

给定 $a_1,a_2,\cdots,a_n$，先手需要重排 $a$，然后后手可以任意次交换两个互质的数

先手需要最小化最后的数组的字典序，后手需要最大化最后的数组的字典序，求最后的数组

$1\le n\le2000,1\le a_i\le10^8$

题解

Sol

字典序，考虑确定第一个数的值

我们在不互质的数之间连一条无向边，那么注意到后手一定无法改变有边之间的元素的相对顺序

如果这张图分为了若干连通块，那么后手一定可以对这些连通块的答案做归并排序，因此我们可以对每个连通块分别求解

注意到如果图联通，那么第一个元素一定可以是最小值，因为我们可以直接把最小值排在最前面，然后任意找一个 bfs/dfs 序往后排，容易发现最小值不会被改动

那么我们把最小值删掉（所有最小值的点都是完全等价的，所以任取一个即可），然后对于剩下的连通块都做同样的事情

问题在于如何快速维护这件事情，如果每次 dfs 一遍我们单层分治的复杂度就是 $O(n^2)$ 的，而又有 $n$ 层，所以复杂度爆了。

注意到我们只关心联通关系，而这个图拥有同一个质因数的点会连成一个团，把这些点全连出来显然太浪费了，对每个质因子 merge 一次即可

复杂度 $O(n^2\omega(a))$

似乎存在好的写法，但是我觉得太神秘了。

27. CF1930I - Counting Is Fun [K] ✔️

题面

给定长为 $n$ 的 $01$ 串 $p$，求有多少长为 $n$ 的 $01$ 串 $q$ 满足对于每个 $i$ 都存在一个 $[l,r]$，使得 $l\le i\le r$ 且 $q[l:r]$ 内 $p_i$ 的出现次数 $\ge\lceil\frac{r-l+1}2\rceil$

对 $998244353$ 取模

$1\le n\le10^5$

题解

Sol

把条件写成前缀和形式，第 $x$ 个位置为 0 表示存在 $sum_j\ge sum_i$ 使得 $j\le x<i$，1 表示存在 $sum_j\le sum_i$ 使得 $j\le x<i$

这个限制看起来很能容斥，只有同时钦定的都为 0 或都为 1 才会有值，不妨考虑钦定 1 的情况，那么可以列出转移式：

$h_i\leftarrow -t_i\\h_i\leftarrow -h_j\times f_{i-j-1}$

其中 $t_i$ 表示从 $(0,0)$ 开始走 $i$ 步 $(+1,-1)/(+1,+1)$，且起点为过程中 $y$ 坐标最小值，$f_i$ 表示从 $(0,0)$ 开始走 $i$ 步 $(+1,-1)/(+1,+1)$，且起点为过程中 $y$ 坐标最小值，终点为过程中 $y$ 坐标最大值，并且只有 $p_i=1$ 的位置的 $h$ 才有值，其余的 $h$ 强制为 $0$

注意到 $t_i=\binom i{\lfloor i/2\rfloor}$，那么如果我们能求出 $f$，就可以通过分治 ntt 求出 $h$，从而算出答案

考虑如何计算 $f_n$，不妨固定终点为 $(n,h)$，定义 $w(n,h)$ 为从 $(0,0)$ 走 $n$ 步走到 $(n,h)$ 的方案数，那么根据反射容斥可以得到式子：

$f_n=\sum_{h=0}^\infty\sum_{i=-\infty}^\infty w(n,h+2i(h+2))-w(n,h+2+2i(h+2))$

这个式子看着不是很能直接优化，因此考虑求每一项 $w(n,x)$ 的系数，可以发现这是 $(2i+1)(h+2)=x+2$ 的解的个数减去 $(2i+1)(h+2)=x$ 的个数，只和 $x$ 有关，设为 $c_x$

那么 $f_n=\sum_{x=-n}^nc_xw(n,x)$，但是这个式子好像不能直接用卷积算

注意到 $w(n,x)$ 格路计数的组合意义，也即 $w(n,x)=y^x^n$，我们考虑分治解决这个问题，把 $c_x$ 放在每个 $(0,x)$，每个点的值为 $(-1,+1)/(-1,-1)$ 方向上的点的权值之和，那么 $f_n$ 就是 $(n,0)$ 的权值

容易通过卷积求出 $x=n/2$ 的点的值，那么我们发现对于右边的计算只用保留 $y\in[-n/2,n/2]$ 内的点，因此我们卷积也只需保留 $[-n/2,n/2]$ 内的点，对两边分别向下递归处理即可

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

28. CF1936E - Yet Yet Another Permutation Problem [E]

题面

给定 $1\sim n$ 的排列 $p$，求有多少排列 $q$ 满足对于任意 $1\le i<n$ 都有 $\max(q[1:i])\neq\max(p[1:i])$

对 $998244353$ 取模

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

题解

Sol

令 $a_i\leftarrow\max(p[1:i])$

注意到如果 $\max(q[1:i])\le a_i$ 那么很好做，这个可以转化为每个数的位置必须在一个单调后缀内，排序一下就可以算了

那么考虑把 $\neq$ 变成 $\le$，首先对于每个 $\neq$ 我们可以枚举它是 $\le a_i-1$ 还是 $\ge a_i+1$，然后对于 $\ge$ 我们可以容斥成 $\le$，那么最后得到对于每个 $a_i$，我们钦定这个点 $\le a_i-1$ 会有 $1$ 的系数，钦定这个点 $\le a_i$ 会有 $-1$ 的系数，不钦定会有 $1$ 的系数

注意到我们把所有钦定取一个后缀最大值，得到 $r_1,r_2,\cdots,r_n$，那么最后的方案数为 $r_1!\prod_{i=1}^{n-1}\frac{(r_{i+1}-i)!}{(r_i-i)!}$

考虑 dp 这个式子，令 $f_{i,0/1}$ 表示 $i$ 的后缀，$i$ 选了 $\le a_i-1$ 或 $\le a_i$，每次转移一段的不钦定，那么有转移式：

$f_{i,o}\leftarrow f_{j,p}\times\frac{(a_j-1+p-i)!}{(a_i-1+o-i)!}$

（$a_j-1+p$ 的含义即为取 $f_{j,p}$ 时钦定的值，需要保证 $j$ 钦定的值大于等于 $i$ 钦定的值）

可以把这个看成一个下标为 $a_j$ 的多项式和下标为 $a_j-i$ 的多项式做的差卷积，如果直接用分治 ntt，每层贡献的区间取 $[a_{m+1}-1,a_r]$，由于 $a$ 递增，复杂度算出来仍然是 $O(n\log^2n)$

但是直接做会出问题，因为我们还有大于等于的限制，注意到大于等于的限制只在同一个 $a_i$ 内会出问题，那么我们按 $a_i$ 的值分块，对块间分治 ntt，块内容易推出前缀和优化的形式，复杂度为 $O(n\log^2n)$

29. AGC011E - Increasing Numbers [S]

题面

给定 $n$，求最小的 $k$，使得存在 $a_1,a_2,\cdots,a_k$，满足 $a_i$ 的十进制数位均单增，且 $\sum a=n$

$1\le n\le10^{500000}$

题解

Sol

可以转化为，在 $n$ 上退一些位，得到 $\overline{n_1n_2\cdots n_m}$，其中 $n_i$ 可能 $\ge10$，答案为满足 $n_1\le n_2\le\cdots\le n_m$ 的 $\lceil\frac {n_m}9\rceil$ 最小值

对这个最小值二分，每次从 $n_i$ 往前推 $n_{i-1}$ 至多为多少，最后如果大于等于原来的值则可行，否则过程中会 $<0$，无解

复杂度 $O(n\log ans)$，我不知道答案是什么量级的。

30. AGC013E - Placing Squares [E/K]

题面

给定 $n,m$，以及 $x_1,x_2,\cdots,x_m$，你需要将一个 $1,2,\cdots,n$ 的序列切成若干段，满足 $x_i$ 和 $x_{i+1}$ 之间没有被切，一种方案的权值为每段长度的平方之积

求所有合法方案的权值和，对 $10^9+7$ 取模

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

题解

Sol

非常具有教育意义。

Flamire 做法

注意到 $m=0$ 的情况就是 $f_i\leftarrow f_j(i-j)^2$

考虑打表，然后 bm，得到 $f_0=0,f_1=1,f_2=5,f_i=4f_{i-1}-2f_{i-2}+f_{i-3}$

定义 $S$ 为 $\begin{bmatrix}f_0&f_1&f_2\end{bmatrix}$，$T$ 为递推式的转移矩阵

考虑容斥，钦定它经过若干个点，那么对于没有钦定 $i$ 的方案，我们需要将它乘上 $T^{x_i-x_{i-1}}$，对于钦定了 $i$ 的方案，我们需要将它先乘上 $T^{x_i-x_{i-1}}$，然后取出当前 $x_i$ 位置的值 $w$（即矩阵内第一个数），然后后面用 $-wS$ 再接着乘

那么每个状态存一个 $1\times3$ 的矩阵，一直乘到最后就是答案了

复杂度 $O(m\log n\cdot3^3)$

myee 做法

转移式为 $f_i=\sum_{j<i}[j\not\in S]f_j(i-j)^2$

考虑拆项，令 $A_i$ 表示 $\sum_{j<i}f_j$，$B_i$ 表示 $\sum_{j<i}f_j(i-j)$，$C_i$ 表示 $\sum_{j<i}f_j(i-j)^2$，则 $A,B,C$ 之间可以互相转移

对每个 $j\not\in S$ 的段分别用矩乘优化即可，复杂度 $O(m\log n\cdot3^3)$

题解做法

考虑组合意义，平方等价于在每个段内再选一个黑球和白球，令 $dp_{i,0/1/2}$ 表示考虑前 $i$ 个，当前的段选了多少个球，转移容易矩阵优化

复杂度 $O(m\log n\cdot3^3)$

31. CF1054G - New Road Network [E]

题面

给定 $m$ 个 $1\sim n$ 的点集，请构造一棵点集为 $\{1,2,\cdots,n\}$ 的树使得每个点集在树上都是一个连通块

给出构造或判断无解

$1\le n,m\le2000$

题解

Sol

Flamire 做法

任意指定一个根 $R$，那么所有不包含 $R$ 的连通块一定属于同一棵 $R$ 的子树，根据这个将子树用并查集并起来

对于包含 $R$ 的集合，对于每棵子树，相当于限制一些点必须在同一个连通块内，并且这个连通块内存在点连向 $R$，也就是说对于每棵子树，设其集合为 $H$，我们取出所有包含 $R$ 且与 $H$ 有交的连通块，那么这棵子树的根一定在这些连通块的交内部，如果交为空则无解

可以发现我们把子树并起来一定是不优的，因为之前的并查集条件说明了此时每个子树已经是一个连通块，这时如果我们把两个子树连通块分到一个子树中，那么把它们单独划出来成为若干棵子树一定仍是合法的

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

考虑 bitset，最难做的操作是并查集 merge，这个可以每次找第一个 1 属于的集合，再找不属于这个集合的第一个元素，可以用 bitset 操作实现，复杂度 $O(n^3/w)$

题解做法 1

考虑叶子，注意到去除所有只有一个点的集合后，设包含点 $i$ 的连通块集合为 $A_i$，那么对于叶子 $A_x\subseteq A_{fa_x}$

一个自然的想法就是每次找到 $A_x\subseteq A_y$ 的一对点，然后将 $x$ 接到 $y$ 上并把 $x$ 这个点删掉，剩下的部分递归做这个问题，直接用 bitset 实现是 $O(n^4/w)$ 的

删掉 $x$ 之后 $A$ 可能产生改变的原因是有些集合的元素个数变为 $1$，这些集合会被删除，观察可以发现改变的 $A$ 只有可能是 $A_{fa_x}$，那么我们下一次只需要 check 所有包含 $fa_x$ 的对即可，复杂度降为 $O(n^3/w)$

题解做法 2

连通块的限制相当于 $S_i$ 集合之间至少连了 $|S_i|-1$ 条边，而由于是树，所以也至多连了 $|S_i|-1$ 条边

也就是说如果我们找到一棵树总共连了 $\sum(|S_i|-)1$ 条同集合之间的边，那么一定找到了一组解，而这也是该值可能的上界

那么我们对于 $i$ 和 $j$，连权值为 $|A_i\operatorname{AND} A_j|$ 的边，求最大生成树，求出来解合法当且仅当权值为 $\sum(|S_i|-1)$，否则无解

复杂度 $O(n^3/w)$

32. AGC037F - Counting of Subarrays [K] ⭐

题面

给定 $a_1,a_2,\cdots,a_n$ 以及常数 $L$，你每次可以将 $\ge L$ 个相同相邻的数 $x$ 合并成一个 $x+1$

求有多少 $a$ 的子区间最后可以合并成一个数

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

题解

Sol

myee 做法

其实本来我想的也是这个，但我写代码写不明白了，看了 myee 老师的题解后顿时大彻大悟。

特判掉长度 $=1$ 的情况

考虑对子区间右端点 $r$ 扫描线，然后对于每个仍然合法的 $l$，维护出一个便于在右边添加元素的结构

显然这个结构应该是一个单调递降的序列，每次在右边添加一个数就将小于它的全部合并

现在我们需要维护的东西是 $O(n^2)$ 的，显然不太行，观察一下可以发现一个序列后缀形成的结构一定是原序列形成的结构的后缀，这意味着我们只用维护一个结构，其余的结构可以挂到每个后缀上

维护结构的部分就解决了，接下来考虑如何询问

询问我们可以直接暴力向上跳，然后把每一层产生的询问记忆化一下，注意到类似于一个 $L$ 进制的加法器，所以复杂度是可以均摊分析的

复杂度应该是 $O(n\log n)$？我并没有仔细分析，总之跑的很快。

ovo 做法

特判掉长度 $=1$ 的情况。

考虑判定一个区间 $[l,r]$ 是否合法，我们找到其中的最大值 $x$，那么最后我们期望将这个区间合并成 $\ge L$ 个 $x$

对于这个区间内部所有 $\le x-1$ 的连续段，分治下去处理

对于本层，我们进行一个 dp：令 $f_{r,i}$ 表示右端点为 $r$，且最后会合并出来 $i$ 个 $x$ 的左端点 $l$ 个数

为了维护这个 dp 并统计大答案，我们需要知道每个子区间的合并出来 $i$ 个 $x$ 的前缀与后缀个数，以及这个子区间一共能合并出多少 $x$，把原来的 dp 改成正反两遍 dp 处理就可以

一层内的 dp 可以用一些手段做到区间长度，考虑一个区间每向上传一次区间长度就可以除 $L$，因此复杂度 $O(n\log n)$

33. CF1450G - Communism [K] ✔️

题面

给定一个长为 $n$ 的字符串 $s$，字符集大小为 $20$，以及一个常数 $k=\frac ab$

你可以进行任意多次操作：选择一种字符 $c$，定义 $l_c,r_c$ 分别为 $c$ 最左最右出现位置，$v_c$ 为 $c$ 的出现次数，如果 $k(r_c-l_c+1)\le v_c$，那么你可以选择任意一个 $s$ 中其他字符 $d$，将 $s$ 中所有 $c$ 变为 $d$

求有多少字符 $x$ 使得可以通过操作让最后 $s$ 所有字符全为 $x$

$1\le n\le5000$

题解

Sol

神仙题。

考虑最后合并出来的结构，字符之间一定形成了一棵树，那么我们考虑对这个树进行 dp

定义 $dp_S$ 表示 $S$ 集合是否能够全变成某一个其他字符，那么我们有两种转移：

合并两棵子树，$dp_S\leftarrow dp_T\operatorname{AND}dp_{S-T}$
加一个根，需要满足新的集合依然能够继续往外合并，$dp_S\leftarrow dp_{S\oplus x}$

直接枚举子集肯定不太行，考虑慧眼观察一下

注意如果树上两个兄弟 $x,y$ 区间有交，那么我们可以把 $y$ 这棵子树接到 $x$ 下面，合法性依然不会改变（两个区间有交的字符，如果两个都可以操作，那么合并起来一定可以操作）

也就是说对于第一种转移我们只用考虑区间不交的情况，容易做到 $O(|\Sigma|2^{|\Sigma|})$