task14

[TOC]

1. BalticOI 2021 - From Hacks to Snitches [K] ✨

题面

给定一张 $n$ 个点 $m$ 条边的无向图，有 $k$ 个保安在上面移动，第 $i$ 个保安的路径可以用一个长为 $l_i$ 的顶点序列 $v_0,v_1,\cdots,v_{l_i-1}$ 描述，第 $j$ 个时刻，这名保安会从 $v_j$ 移动到 $v_{(j+1)\bmod l_i}$，保证 $v_j$ 到 $v_{(j+1)\bmod l_i}$ 有边

保证所有出现过的 $v$ 中的元素两两不同，且 $1$ 和 $n$ 不会被任意一个保安经过

求 $1$ 到 $n$，且不在任意一个点和边上和保安相遇的最短路，你可以在点上停留

$1\le n\le2.5\times10^5,1\le m\le3\times10^6,3\le l_i\le1500,\sum l_i\le2750$

题解

Sol

对不在环上的点，显然越早到达越好，对于在环上的点，如果 $t$ 时刻能到达，那么 $t+l_i$ 时刻也能到达，也就是说我们可以只记录 $O(n+L^2)$ 个状态

考虑如何跑最短路，讨论边的情况，直接暴力做的话应该是 $O(mL^2)$ 的，

那么考虑不暴力做。

首先，我们可以增加一个等待 $1$ 的时间的转移，然后考虑能不能缩减一下转移的数量：

环点到非环点，显然我们只用转移一次，那么转移完第一次之后将这条边删掉即可
非环点到环点，我们转移直接走过去的，和等待一段时间后走到紧跟守卫后面的位置的情况，剩下的状态都可以通过等待的转移得到
环点到环点，这种情况更加复杂一些，设两个环的大小分别为 $l_1,l_2$，我们要转移的边是 $u\rightarrow v$：
- 首先特殊处理一下是一个环上的相邻边的情况（因为这种边有可能出现和守卫在边上相遇的情况），这部分直接暴力就是 $O(L^2)$ 的
- 考虑第一次扫到 $u$ 点的时候进行转移：首先一个转移是直接走过去，接下来我们仿照非环点到环点的转移，考虑什么时候能直接跟在守卫的后面
  我们进行这样一个操作：走到 $v$，然后一直等待，直到下一步就要被守卫追上，然后走回 $u$，再走回 $v$
  这样失败的情况只有走回 $u$ 时撞上了 $l_1$ 的守卫，设 $l_1$ 守卫初始到 $u$ 需要 $x$ 的时间，$l_2$ 守卫初始到 $v$ 需要 $y$ 的时间，这种情况只会在 $y\bmod l_2=x$ 的情况出现
  也就是说当 $y\bmod l_2\neq x$ 的时候，我们只在第一次扫到 $u$ 的时候更新两个转移即可，更新完之后就可以把这条边删掉了
  当 $y\bmod l_2=x$ 的时候，我们继续考虑什么时候能走到守卫的后面：
  - $l_1\ge l_2$，那么 $l_2$ 上只有恰好一个位置满足 $y\bmod l_2=x$，也就是说我们在 $l_1$ 上再转一圈，如果 $y$ 没有变，即 $l_1\bmod l_2=0$，那么我们在当前的余数下转多少圈也不可能能够走到守卫后面的点，否则一定可以，更新一下守卫后面的点即可
  - $l_1<l_2$，那么我们不断转 $l_1$ 直到 $l_2$ 守卫经过了 $v$，此时 $l_2$ 守卫必定转了不满一圈，即下一次 check 一定是 $(y+l_2)\bmod l_1=x$，如果 $l_2\bmod l_1=0$，那么一定永远不可行，否则下一次一定可以，同样更新一下即可
  这意味着此时要么下一次，我们就能走到所有点，要么我们无法比第一次访问更多的点
  因此我们只需关心 $l_1,l_2$ 较大的只转了不超过一次的转移，那么我们再添加一个，从 $u$ 指向不断转 $l_1$，能到的 $l_2$ 守卫后的第一个点

考虑这样做的复杂度，除了环点到环点的部分显然都是只有 $O(m)$ 的转移的

环点到环点的转移，除了 $y\bmod l_2=x$ 的情况，显然都是 $O(m)$ 的，考虑分析这种情况带来额外的复杂度

对于两个环 $l_1,l_2$，$l_1$ 的环点 $u$ 以及余数 $x$，这种情况对于所有 $v$ 一共会发生 $\lceil\frac {l_2}{l_1}\rceil$ 次（因为 $y$ 是固定的，可以从 $dis_{u,x}$ 求出来）

当 $l_1\le l_2$ 时，这种情况一共会发生 $\lceil\frac{l_2}{l_1}\rceil\times l_1^2=O(l_1l_2)$ 次

当 $l_1>l_2$ 时，直接分析会带有 $l_1^2$ 项，这是我们不想看到的，但是我们可以考虑一件事情，就是一条 $u\rightarrow v$ 的边最多会被更新 $l_2$ 次，因为当 $x>l_2$ 时，$(u,x)$ 可以直接等到 $l_2$ 守卫的后面，这种情况下这条边就直接被删掉了，也就是说只有 $l_2$ 种余数这条边不会被删掉

那么考虑一个 $u$ 第一轮更新之后，一定有至多一条边，因为满足 $y\bmod l_1=x$ 的最多只有一个，然后这条边又最多被更新 $l_2$ 次，也即最多会更新 $O(l_1l_2)$ 次

那么总共转移边数就是 $O(m+L^2)$ 的，点数是 $O(n+L^2)$，由于值域比较小，所以我们可以不使用优先队列，而是使用桶来更新距离，复杂度 $O(m+L^2)$

2. AGC064F - No Permutations [E] ✔️

题面

给定一个 $n$，求有多少长为 $3n$ 的序列，满足 $1\sim n$ 每个数出现了恰好 $3$ 次，并且不存在任意一个 $1\le l\le2n+1$ 使得 $[l:l+n-1]$ 的子段是 $1\sim n$ 的排列，对 $998244353$ 取模

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

题解

Sol

首先考虑得到一个多项式复杂度做法。

这个限制看着很像想让人容斥的样子，因此我们先容斥，转化为一些子区间钦定是 $1\sim n$ 的排列，求方案数

注意到不同连通块之间是独立的，那么我们令 $f_i$ 表示长为 $i$ 的钦定连通块算出来的方案数是多少（我们认为连通当且仅当 $l_1<l_2$ 且 $r_1+1\ge l_2$）

考虑一个钦定连通块内会发生什么：

首先，第一个钦定区间之后，所有数都出现了 $1$ 次

接下来每个钦定区间可以认为是把前面的一部分数重排扔到后面，并且让这些数的出现次数 $+1$

也就是说我们会出现一些前缀出现次数为 $1$，后缀出现次数为 $2$ 的区间

然后出现一些前缀出现次数为 $2$，后缀出现次数为 $2/3$ 的区间

然后出现一些前缀出现次数 $2/3$，后缀出现次数为 $3$（应该是 $3/4$，但是不能有 $4$）的区间

注意到一件事情是我们出现次数的最大值减去最小值一定不超过 $1$，也就是说我们确定了一个段的长度就可以确定里面每个数出现次数的情况

那么到这里我们就可以尝试进行 dp 了，首先当 $i\in[n,2n]$ 时转移是容易的，只要 $f_i\leftarrow -f_j\times(i-j)!$ 即可

当 $i\in [2n+1,3n]$ 的时候会出现一些问题，因为如果我们一步操作内将 $2/3$ 的数放到了后面，我们需要提前保证这些数的出现次数为 $2$，否则就会不合法

那么我们转移完 $f[n\sim 2n]$ 之后，设一个状态 $g_{i,x}$ 表示长为 $i$ 的连通块，且最后一个区间中第一个出现次数为 $3$ 的数在 $x$ 的位置，$f$ 到 $g$ 的转移是 $O(n^2)$ 的，$g$ 内部的转移是 $O(n)$ 的，总复杂度 $O(n^3)$

求出 $f$ 之后，我们考虑合并 $f$，注意到由于是 $3n$，所以我们只用考虑两个 $f$ 的合并，和一个 $f$ 的情况，此时 $f$ 出现次数固定的优势就体现出来了

对于一个 $f$，我们直接用一些阶乘和组合数计算即可

对于两个 $f$，我们枚举两个段的长度 $i,j$，$f_i$ 中有一些出现次数为 $1$ 和 $2$ 的数，$f_j$ 有一些出现次数为 $1$ 和 $2$ 的数，我们要将它们匹配起来，只有 $2-2$ 之间不能匹配，这个也是可以用组合数计算的

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

但是这个做法还是有点烂。

求 $f[n\sim 2n]$ 的部分可以用分治 ntt 优化做到 $O(n\log^2n)$，因为我不会多项式求逆。

最后合并两个 $f$ 的部分就是一次卷积，可以优化到 $O(n\log n)$

剩余的部分只有中间求 $f[2n+1\sim3n]$，这部分的 dp 使其难以优化。

我们直接不 dp 了，寻找别的求解方式。

注意到我们如果从最后一个在 $[1,2n-1]$ 内的区间分开，那么后面的部分如果倒过来的话也是一个 $f[n\sim 2n]$ 的状态，而我们需要做的就是将这两个状态缝起来

那么我们枚举两边状态的长度 $i,j$，再额外枚举一个这两个状态最后一个区间重合的长度 $x$，合并的时候同样是两个序列，每个序列里有一些出现次数为 $1$ 和 $2$ 的，$2-2$ 不能匹配，继续用组合数算即可

现在得到了一个不需要 dp 的 $O(n^3)$ 做法。

把代码写出来，然后对着代码硬拆，可能会拆出来一些前缀和优化，一些卷积，以及一坨。

最后我拆出来的是类似对于所有 $i\le x<j$，将 $a_ib_xc_j$ 贡献到 $g_{i+j-x}$，这个可以用分治 ntt 解决

那么整体的复杂度就是 $O(n\log^2n)$

3. AGC065F - Always Perfect [K] ✔️

题面

给定一个偶数 $n$，求有多少 $n$ 个点的有标号无向连通图 $G$，满足任意一棵 $G$ 的生成树 $T$ 都存在完美匹配，对大质数 $P$ 取模

$2\le n\le500$

题解

Sol

首先考虑什么样的图是满足条件的：

这个生成树的条件看起来和环有一定关系，所以首先缩一下点双

那么对于一个点双，如果我们将它作为根，那么其每个点是参与其它点双的匹配，还是参与本点双内的匹配，是确定的，这个可以通过判断圆方树上子树奇偶性的来得到，称需要点双内匹配的点为 $1$，不需要匹配的点为 $0$

如果一个点双内同时存在 $0/1$ 点，我们可以说明这张图一定不合法：此时我们找到任意一条连接 $0-1$ 的边，我们把这个 $1$ 周围的其他边都删掉，只保留这一条边，由于点双的性质，剩下点一定连通，那么我们剩下的部分随便选一棵生成树，此时这个 $1$ 是叶子，而且父亲不能匹配，因此不合法

那么就只有全 $1$ 和全 $0$ 的情况了，对于全 $0$ 的情况，这个点双内部我们不需要考虑任何事情

对于全 $1$ 的情况，考虑什么样的情况下总是存在完美匹配

经过一些手模可以发现，一定只有偶环可行：否则我们找到一个度 $\ge3$ 的点 $u$，设其连向 $v_1,v_2,v_3$

我们考虑三棵生成树：

$T_1$：$u$ 是叶子且连向 $v_1$，剩下部分任意取一棵生成树，不妨设三个点的中心 $L$ 在 $v_1,v_2$ 的路径上（不包含端点）
$T_2$：保留 $T_1$ 的其余边不变，改为将 $u$ 连向 $v_2$
$T_3$：保留 $T_1$ 的其余边不变，分别断开 $v_1,v_2$ 向 $L$ 走的第一条边，使得 $v_1,v_2,v_3$ 分属三个连通块，连边 $(u,v_1),(u,v_2),(u,v_3)$

由于 $T_1,T_2$ 都有完美匹配，说明 $v_1$ 和 $v_2$ 的子树都可以内部匹配完，而 $T_3$ 中相当于 $v_1,v_2$ 都要跟 $u$ 匹配，因此不合法

那么最后合法的图形态即为：初始有一些偶环（我们把边也认为成长为 $2$ 的偶环），我们每次可以选择一些连通块，在这些连通块上分别选一个点，然后对于选出来这些点连一个边双，直到图连通

考虑对这个进行计数。

首先计数出 $f_n$ 表示 $n$ 个点的连通图数量，那么接下来考虑计算 $n$ 个点能组成多少点双：

令 $g_{n,m}$ 表示 $n$ 个点，$m$ 个点双的连通图数量，我们建出圆方树，然后把每个方点和下面的圆点分成一个结构，记 $a_i$ 表示这个结构里的圆点数量，那么我们要做的实际上就是把 $m+1$ 个结构连成一个树的结构

现在的问题就是：给定 $a_1,a_2,\cdots,a_{m+1}$（其中 $a_1=1$），要求连出一棵以 $1$ 为根的有根树，连一条边 $(fa,u)$ 的方案数是 $a_{fa}$

注意到如果把方案数改成 $a_{fa}\times a_i$，那么这就是我们会算的，相当于大小分别为 $a_i$ 的连通块想要连通的方案数，这个就是 $n^{m-1}\times\prod_{i=1}^{n+1} a_i$，而我们多乘了 $\prod_{i=2}^{m+1} a_i$，所以实际上原问题的方案数就是 $n^{m-1}\times a_1=n^{m-1}$

那么就可以列出 $g_{n,m}$ 的转移式了：

$g_{n,m}=\frac1{m!}\sum_{a_1+a_2+\cdots+a_m=n-1}\binom{n-1}{a_1,a_2,\cdots,a_m}n^{m-1}\prod g_{a_i+1,1}$

容易使用一些 dp 进行 $O(n^3)$ 计算，$g_{n,1}$ 可以通过 $g_{n,i}$ 容斥算出

接下来考虑算答案：

我们不妨枚举一下环数 $k$，和合并次数 $m$，设环长分别为 $l_1,l_2,\cdots,l_k$，那么就可以尝试列一下方案数了

首先定包含 $1$ 的环为根，不妨设其为 $l_1$

我们还是建立上文类似的方点和下面一堆圆点的结构，只不过现在每个圆点是一个环

现在连边需要在每个环中选一个点出来连，因此需要重新重新列一下贡献式，就是 $w_{fa}\times\prod l_{u,i}$

这个 $\prod l_{u,i}$ 可以提出去，变成 $\prod_{i=2}^k l_i$，而剩下的部分根据我们之前的推导，方案数是 $k^{m-1}\times w_1=k^{m-1}\times l_1$，乘上前面的就是 $k^{m-1}\times\prod l_i$

可以根据这个列式：

$ans=\sum_{l_1+l_2+\cdots+l_k=n}\binom{n-1}{l_1-1,l_2,\cdots,l_k}\prod_{i=1}^kring_{l_i}\sum_{a_1+a_2+\cdots+a_m=k-1}\binom{k-1}{a_1,a_2,\cdots,a_m}(\prod_{i=1}^kl_i)\prod_{i=1}g_{a_i+1,1}$

也可以通过 dp 进行 $O(n^3)$ 计算

4. luoguP9036 - 挑战 NPC Ⅲ [E] ⭐

题面

给定一张 $n$ 个点，$m$ 条边的无向图，以及一个整数 $k$，求图中大小恰好为 $n-k$ 的点独立集数量，对 $998244353$ 取模

$1\le n\le10^5,0\le m\le10^5,0\le k\le\min(n-1,18)$

题解

Sol

做法 1

首先可以转成点覆盖。

注意到 $k$ 其实很小，而我们如果每次找到一条两边都没有被覆盖过的边进行决策的话，只会进行 $O(2^k)$ 量级的搜索

因此考虑这样一个算法：

每次找到一个两边都没有选过的边 $(u,v)$，分别考虑选择 $u$ 和选择 $v$ 的情况继续搜索

而由于我们需要计数，所以我们希望这个方案不重复，而我们只要限制选择 $v$ 的时候强制不选 $u$ 即可

那么现在瓶颈就在于找到下一条合法的边

这个直接做是可以做的，但是我们有更聪明的做法：

考察度数最大的点，如果其度数 $\deg>k$，那么这个点必选，否则点数就爆了

不断选度数最大的点，最后剩余的每个点度数一定 $\le k$，而此时如果边数 $>k^2$，一个点只能覆盖 $k$ 条边，所以一定不合法

那么就转化为了点数和边数都是 $O(k^2)$ 的问题，因此直接暴力找下一条边，总复杂度就是 $O(2^kk^2)$ 的

做法 2

不按边搜索，按点搜索。

注意到我们想要一个点产生的影响尽可能大，因此我们可以考虑直接搜索度数最大的点

这个点如果选了，则我们需要选择的点数 $-1$，如果这个点不选，则其相连的所有点必须选，那么我们需要选择的点数 $-\deg$

当最大度数 $\le2$ 的时候我们可以直接计算，因此复杂度是 $f(k)=f(k-1)+f(k-3)+\text{poly}(k)$ 的，即 $O(f(k)\times \text{poly}(k))$

事实上，$f(k)$ 在 $k=30$ 的时候只有 $30000\sim50000$ 的量级，在 $k=40$ 的时候只有 $10^6$，因此这个做法其实是可以解决 $k$ 更大的问题的

5. ABC269Ex - Antichain [E] ⭐

题面

给定一棵 $n$ 个点的有根树，根为 $1$，对每个 $k=1,2,\cdots,n$，求有多少 $V\subseteq\{1,2,\cdots,n\}$，满足 $|V|=k$，且 $V$ 中任意两点不互为祖孙关系，答案对 $998244353$ 取模

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

题解

Sol

首先可以有一个显然的 dp：设 $dp_{i,j}$ 表示 $i$ 子树内，选了 $j$ 个点的方案数

转移式写成生成函数就是 $F_u=x+\prod F_v$

这个直接算是不好计算的。

注意到对于一条链，我们相当于是一个不断乘一个多项式，然后 $+x$ 的过程，这个可以用分治 ntt 维护

具体地，我们对树进行重链剖分，每次取出到根的重链，然后把所有轻儿子的值先计算了，对于这个重链进行一次分治 ntt

总复杂度是 $O(n\log^3n)$，如果分治 ntt 的时候按照带权中点分治的话就是 $O(n\log^2n)$

6. AGC039F - Min Product Sum []

题面

对于一个 $n\times m$ 矩阵，每个元素在 $[1,k]$ 内的矩阵 $a_{i,j}$，定义 $b_{i,j}$ 为第 $i$ 行和第 $j$ 列所有 $a$ 值的最小值

对于所有 $a$ 矩阵，求其生成的 $b$ 矩阵的所有位置乘积之和，对给定大质数取模

$1\le n,m,k\le100$

题解

Sol

考虑答案实际上只和每一行每一列的最小值相关，因此我们可以考虑对这个搞一些事情

我们从小到大加入所有行和列的最小值，设 $dp_{v,x,y}$ 表示现在考虑值 $v$，已经加入了 $x$ 行，$y$ 列，每次枚举有 $a$ 行的最小值为 $v$，有 $b$ 列的最小值为 $v$，转移系数需要对 $a$ 和 $b$ 分别容斥

那么枚举 $v,x,y,a,b,i,j$ 之后，我们有如下转移系数：

新加入的最小值对答案的贡献：$v^{(n-x)(m-y)-(n-x-a)(m-y-b)}$
$a$ 行 $b$ 列内部可以任意排：$\frac1{a!b!}$
$i,j$ 的容斥系数：$(-1)^{i+j}\binom ai\binom bj$
容斥后计算新加进来的 $a$ 行 $b$ 列的方案数：$(k-v+1)^{(x+a-i)(y+b-j)-xy}\cdot(k-v)^{(x+a)(y+b)-(x+a-i)(y+b-j)}$

最后贡献给 $dp_{v+1,x+a,y+b}$，那么我们就得到了一个 $O(k(nm)^3)$ 的做法

考虑优化：

将式子写开，可以发现这个东西可以视作一个 $(x,y)\rightarrow(x+a-i,y+b-j)\rightarrow(x+a,y+b)$ 的分步二维卷积

每次转移一个变量即可做到 $O(knm(n+m))$

7. CF1336E - Chiori and Doll Picking [K] ✨

题面

给定 $n$ 个 $m$ 位的二进制数 $a_1,a_2,\cdots,a_n$，求有多少种选出一个子集的方式使得其异或值的 popcount 为 $k$

对 $k=0,1,\cdots,m$ 求答案，答案对 $998244353$ 取模

$1\le n\le2\times10^5,0\le m\le53$

E1：$0\le m\le35$

题解

Sol

都选一个子集异或了，因此可以先建线性基。

设线性基大小为 $k$，那么现在一共只有 $k$ 个数了

这个 $m$ 的范围看起来很能折半的样子，而 $k$ 比较小的话我们可以直接暴力，复杂度是 $O(2^k\cdot k)$ 的，精细实现一下可以做到 $O(2^k)$

那么接下来考虑 $k$ 比较大的做法。

注意我们可以进行消元，让线性基中每一行至少有一列，使得它是这一列唯一的 $1$

那么我们选一个数一定会让 popcount $+1$，然后对线性基控制不了的位做一些改变

而这个位有 $m-k$ 个，所以我们可以进行一个 $O(2^{m-k}\cdot k^2)$ 的 dp

两部分拼一下应该能通过 $m\le35$。

前半部分看起来已经不太行了，考虑后半部分能不能优化：

我们要求的实际上是异或 popcount 加上选的个数 $=i$ 的数量

因此可以写成 $\prod(1+x^ay)$，其中 $x$ 对应异或卷积，$y$ 对应普通卷积

那么考虑直接对这个式子 FWT：

$FWT(1+y\cdot x^S)_T=(-1)^{|S\&T|}\cdot y+1$

那么对于一个 $T$，我们如果想求出最后乘起来的结果的值，只需要求有多少数的 $|S\&T|$ 为奇数/偶数，这个可以通过预先预处理出来每一位有哪些数为 $1$，那么将 $T$ 中每个 $1$ 位置的这个值异或起来的 popcount 即为所求

我们现在可以得出来每个 $FWT_T$ 是 $(1+y)^p(1-y)^q$ 了，而由于一个 $T$ 在 IFWT 回去后，对每种 popcount 贡献的系数是只与 $|T|$ 相关的，因此我们可以将一个 popcount 的 $T$ 缩在一起，然后以 $O(\text{poly}(m))$ 的时间计算这个贡献

那么至此，我们 $k$ 大的部分的复杂度就是 $O(2^{m-k}+m^4)$ 的了，因此总复杂度是 $O(2^{m/2}+m^4)$

8. AGC041F - Histogram Rooks [E] ⭐

题面

一个 $n\times n$ 的网格，被挖掉了一部分：第 $i$ 列只保留了最下面的 $h_i$ 个格子

求有多少放置若干个车的方案，使得所有空白格子都能有车，或能被车一步走到

车能一步走到所有同行同列的点，但不能越过挖掉的区域

答案对 $998244353$ 取模

$1\le n\le400,1\le h_i\le n$

题解

Sol

每行每列要么有车，要么没车，而题目要求的条件相当于没车的行列不能相交

那么我们枚举一些不交行列，认为它们就是最后的没车集合，而剩下的部分我们需要要求其有车

这个可以继续进行容斥，再额外选一些行列，钦定它们没车

因此最后即为：我们选择一个不交行列集合 $S_1$，和一个行列集合 $S_2$，满足 $S_1\cap S_2=\varnothing$，贡献 $(-1)^{S_2}$ 的系数，然后再乘上 $2$ 的没被覆盖的格子数次方

这个图形可以建笛卡尔树，令 $dp_{i,j,0/1}$ 表示第 $i$ 个节点，子树内当前一共选了 $j$ 和 $S_1$ 或 $S_2$ 的列，并且是否选了至少一个 $S_1$ 的列

转移首先做一个子树背包的东西，然后加入一些新的列，设列有 $exw$ 个，并且我们要新选 $i$ 个 $S_1$ 或 $S_2$：

不选 $S_1$，此时有 $(-1)^i\binom {exw}i$ 的系数
选 $S_1$，此时有 $(-1)^i\binom{exw}j\sum_{j=1}^i(-1)^j\binom ij=(-1)^{i+1}\binom{exw}j$ 的系数

做完背包之后考虑乘上当前节点的系数，不妨设当前的节点矩形有 $h$ 行 $w$ 列：

没选 $S_1$ 列，此时如果我们选了 $x$ 行 $S_1$ 或 $S_2$，那么分配 $S_1$ 还是 $S_2$ 的系数是 $(1+(-1))^x$，因此只要考虑 $x=0$ 的情况，即 $2^{h(w-i)}$
选了 $S_1$ 列，此时不能选 $S_1$ 行，也即选了的都为 $S_2$，系数为 $\sum_{j=1}^h(-1)^j\binom hj2^{(h-j)(w-i)}$，推一下可以发现这个等于 $(2^{w-i}-1)^h$

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

9. JOISC2022 - 鱼 2 [] ✔️

题面

有 $n$ 条鱼，第 $i$ 条鱼的大小为 $a_i$，$q$ 次操作，每次操作为一下两种中的一种：

单点修改一条鱼的大小
取出一个子区间的鱼 $a_l,a_{l+1},\cdots,a_r$，求以下问题的答案：

不断进行如下操作：选择两条相邻的鱼，让较大的鱼吃掉较小的鱼，如果相等则任选一个鱼吞掉另一个鱼，吃的一方保留自己的编号，大小变为两鱼大小相加

求有多少个鱼可能成为最后留下的一条鱼

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

题解

Sol

常做常新。

考虑直接用线段树维护这个东西，这意味着我们需要找到一个方便记录且方便合并的信息

注意到每一个鱼都有一个极大的区间，表示它左右吃，吃到哪里会吃不动，而如果两条鱼的极大区间是一样的，我们可以认为它们是完全相同的，即为一个等价类

对于一个线段树上的节点 $[L,R]$，如果一个鱼的极大区间在 $[L+1,R-1]$ 内，那么不论外面再拼上什么，它都不会再有用了

因此我们只需要保存以 $L$ 为左端点的极大区间的鱼，以及以 $R$ 为右端点的极大区间的鱼

而注意到这两种分别都只有 $O(\log V)$ 个，因为出现一个极大区间值域一定翻倍

那么直接维护每一种等价类即可，合并复杂度可以做到 $O(\log V)$

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

10. CF1874G - Jellyfish and Inscryption [] ⭐

题面

给定一张 $n$ 个点 $m$ 条边的有向无环图，你需要从 $1$ 走到 $n$，保证每个点都能被 $1$ 到达且能到达 $n$，每个点有以下若干种类型：

0：无事发生
1 a b，你经过这个点会获得一个二元组 $(a,b)$
2 x，你可以选择一个之前的二元组，然后将其的 $a$ 值 $+x$
3 y，你可以选择一个之前的二元组，然后将其的 $b$ 值 $+y$
4 w，你会获得一个 $w$

最后可以选择你获得的任意一个 $(a,b)$，将其的 $a$ 乘上 $10^9$

你的分数为 $\sum a_ib_i+\sum w_i$，求最大的可能分数

$2\le n\le200,n-1\le m\le2000,1\le a,b,x,y\le200,1\le w\le10^6$

题解

Sol

首先可以发现 $10^9$ 是一个足够大的数，也就是我们要先最大化最大的 $a_ib_i$，然后再最大化 $\sum a_ib_i+\sum w_i$

最大化最大值是好做的，获得成为最大值的二元组后一定是，我们从 $n$ 倒着开始 dp，令 $g_{i,j}$ 表示结点 $i$，$\sum x=j$ 的时候第一关键字 $\sum y$，第二关键字 $\sum a_ib_i+w_i$

对于一个序列，最优策略并不是很好考虑，但是考虑如果最后把 $a$ 加成了 $a^\prime$，此时 $b$ 的最优策略一定是每次找前面最大的 $a^\prime$ 的位置将其 $+y$

这同时也说明了，如果我们将 2/3 操作改成给前面的若干个 $a/b$ 加上总量为 $x/y$ 的数，最优解不变

那么我们可以写出一个 dp，每次直接钦定 $a^\prime$，令 $f_{i,j,k}$ 表示第 $i$ 个点，当前前面最大的 $a^\prime$ 为 $j$，并且当前我们x幼还 $k$ 的债让 $a$ 变成 $a^\prime$

那么这样状态是 $O(n^3V^2)$ 的，但是我们可以注意到如下性质：

如果某条路径，满足路上第一个 1 点后面的 $\sum x>V,\sum y>V$，那么我们一定可以将前面的某个点选成最大的点，一定比当前更优

因此我们对 $a$ 和 $b$ 分别做一遍这个 dp，只后两维保留到 $V$，然后转移可以使用一些前缀和优化做到 $O(1)$

总复杂度为 $O(mV^2+mnV)$

11. ARC147F - Again ABC String [] ⭐

题面

给定 $n,X,Y,Z$，求满足以下条件的长为 $n$ 的 ABC 串数量，答案对 $2$ 取模：

令 $A_i,B_i,C_i$ 分别为长为 $i$ 的前缀内出现了多少 A/B/C，对于 $1\le i\le n$，以下条件必须成立：
- $A_i-B_i\le X$
- $B_i-C_i\le Y$
- $C_i-A_i\le Z$

$T$ 组数据。

$1\le T\le10,1\le n\le10^9,0\le X,Y,Z\le10^9$

题解

Sol

注意到我们每个字符的操作相当于我们有三个数，每次给一个数 $+1$，然后给其循环的下一位 $-1$，那么考虑如下模型：

有一个 $X+Y+Z+3$ 的环，初始有三个棋子分别在 $0,X+1,X+Y+2$，每次你可以选择一个棋子向后移动 $1$，求移动 $n$ 次后不交的方案数

对 $2$ 取模启示我们要找一些双射，而我们求的又是不交路径数，因此我们可以考虑对交点搞一些事情

具体地，我们找到最后一次相交的位置，那么我们将这个位置之后的路径交换一定对应着另一种方案，因此我们可以通过 $3^n$ 减去两两棋子最后在同一位置的方案数 $\bmod2$，来计算答案（因为这样最后三个棋子在同一位置恰好也被算了奇数次，所以不需要额外容斥）

那么以 $0$ 和 $X+1$ 最后相遇为例，我们要计算的就是：

$\sum_{r\equiv X+1\pmod{X+Y+Z+3}}[x^r](x^{-1}+1+x)^n$

注意到模 $2$ 意义下有一个性质：$(x^{-1}+1+x)^{2^k}=x^{-2^k}+1+x^{2^k}$，证明可以考虑直接展开：

$(x^{-1}+1+x)^{2^k}=\sum_{a,b}\binom{2^k}{a,b,2^k-a-b}x^{a-b}\\$

而由 Kummer 定理，这个组合数的值不为 $0$ 当且仅当 $a,b$ 为 $2^k$ 的不交子集，枚举一下取值即可得到上述结论

那么我们就可以将答案式变为：

$\sum_{r\equiv X+1\pmod{X+Y+Z+3}}[x^r]\sum (x^{-p_i}+1+x^{p_i})$

其中 $p_i$ 为 $n$ 的所有二进制位。

那么如果 $X+Y+Z+3$ 很小，我们可以直接使用循环卷积解决

如果 $X+Y+Z+3$ 比较大，那么我们可以直接枚举 $r$ 的取值，然后用数位 dp 解决

那么复杂度就是 $O(T\sqrt n\log n)$，可以通过

12. CF1519F - Chests and Keys []

题面

有 $n$ 个箱子和 $m$ 种锁，Alice 可以给每个箱子上若干个锁，给第 $i$ 个箱子上第 $j$ 种锁会花费 $c_{i,j}$ 的代价

然后 Bob 会开这些箱子，Bob 会向 Alice 购买一些钥匙，第 $j$ 个钥匙能打开所有第 $j$ 种锁，并且购买这种锁需要花费 $b_j$ 的代价，Bob 打开第 $i$ 个箱子会获得 $a_i$ 的收益

Alice 想使得 Bob 不管如何购买钥匙并且打开箱子，Bob 获得的收益都小于等于代价，求达成这个 Alice 需要花费的最小代价

$1\le n,m\le6,1\le a_i,b_i\le4,1\le c_{i,j}\le10^7$

题解

Sol

条件相当于对于任意箱子的子集 $S$：

$\sum_{i\in S} a_i\le\sum_{j\in\text{lock}(S)}b_j$

注意到这个条件很像 Hall 定理，那么我们套一下，就可以得到如下模型：

左部点有 $n$ 个，右部点有 $m$ 个，左边第 $i$ 个点的流量限制为 $a_i$，右边第 $i$ 个点的流量限制为 $b_i$，Alice 可以花费 $c_{i,j}$ 的代价在左部 $i$ 和右部 $j$ 之间加一条 $\infty$ 边，求让左部点的流量都能匹配上右部点的最小花费

数据范围很小，因此我们可以直接记忆化搜索：

令 $dp_{i,j,S}$ 表示我们当前在考虑 $i-j$ 的边，$a[1:i-1]$ 已经都匹配好了，此时 $b$ 的状态为 $S$ 的最小花费

复杂度 $O(能过)$

13. CF1545D - AquaMoon and Wrong Coordinate [K]

题面

有 $n$ 个人，第 $i$ 个人初始在 $x_i$，以每时刻 $v_i$ 单位的速度向正方向运动

现在给定 $0,1,\cdots,k-1$ 时刻每个人的位置的可重集，不过其中有一个 $1\le id\le k-2$ 时刻的某一个位置被修改了

你需要求出这个被修改的位置的时刻，以及修改之前是什么数

$5\le n\le1000,7\le k\le1000$

题解

Sol

由于保证 $0$ 时刻和 $k-1$ 时刻是对的，我们可以取一下差值求出 $\sum v_i$

那么我们就知道哪个时刻 $id$ 是错的了，只要比较一下是否在等差数列上即可

但是我们还要求出错的是哪个数，正确的值一定是在这个时刻的某一个位置上 $+k$，其中 $k$ 是可以求得的

还需要再找一些常量。

注意到如果我们令 $sum_t$ 表示 $t$ 时刻坐标的平方和，那么 $sum_t+sum_{t+2}-2sum_{t+1}=2\sum v_i^2$

那么我们可以先求出来 $\sum v_i^2$，然后再对比一下 $sum_{id-1}+sum_{id+1}-2sum_{id}$ 需要改变多少，解一下即可

复杂度 $O(nk)$

14. AGC014F - Strange Sorting [K] ✨

题面

给定一个 $1\sim n$ 的排列 $p_1,p_2,\cdots,p_n$

每次操作，令 $a$ 为 $p$ 的所有前缀最大值按顺序排列，$b$ 为所有非前缀最大值按顺序排列，将 $p$ 替换为 $b+a$

经过若干次操作后 $p$ 会被排序，求操作次数

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

题解

Sol

过分啊。

注意到 $1$ 其实非常没用，因为加入 $1$ 并不会改变其他数是否是前缀最大值

那么我们只考虑 $2\sim n$ 的过程，先将这些数排好序，然后此时 $1$ 会插入在其中的某个位置，如果这个位置恰好是开头，那么我们就不需要一次额外操作，否则就需要一次额外操作

考虑怎么判定这件事情：

我不会啊。怎么判定。说不定你可以手模打个表啥的。

题解说：如果 $2\sim n$ 一开始就是排好序的，那么这是好判定的，否则你可以考虑排好序之前的一次操作，设此时局面 $2\sim n$ 中最靠前的元素为 $f$，我们可以证明 $f\neq2$，因为如果 $f=2$，那么在当前局面未排好序的情况下，下一步一定也排不好序

因此 $1,2,f$ 是三个不同的数，我们可以继续发现：$1,2,f$ 着三个数从开始到当前这一步，相对位置关系在循环位移的意义下一定是等价的，证明如下：

首先我们证明一个引理，如果 $x$ 某一时刻成为了非开头的前缀最大值，那么它之后就再也不可能回到开头：这是因为 $x$ 成为了非开头的前缀最大值，下一步操作必有一个 $y<x$ 在 $x$ 前面，而这之后 $x$ 如果想要摆脱 $y$，则必须成为非开头的前缀最大值，那么一直这样进行下去可以得到一定不行

而 $f$ 在这次操作时是开头元素，因此 $f$ 前面一定没有成为过非开头的前缀最大值

有了这个引理之后，我们可以分情况讨论一步操作的影响了：

$1$ 在第一个位置，那么 $1$ 是前缀最大值，此时分两种情况讨论：
- $2$ 在第二个位置，那么 $2$ 是前缀最大值，而由我们前面的引理，$f$ 不是前缀最大值，此时后移的是一个 $1,2,f$ 的前缀，符合条件
- $2$ 不在第二个位置，那么 $f,2$ 均不是前缀最大值，无论后面 $f,2$ 怎么排列，我们后移的还是一个前缀，符合条件
$2$ 在第一个位置，那么 $1$ 和 $f$ 都必定不是前缀最大值，因此后移的也是一个前缀，符合条件
$f$ 在第一个位置，那么 $1$ 和 $2$ 都必定不是前缀最大值，符合条件
$1,2,f$ 均不在第一个位置，那么三个数都不是前缀最大值，符合条件

因此原命题得证。

那么考虑最后一次操作之前的局面，$f$ 和 $2$ 的顺序一定是 $f$ 在前，讨论此时 $1$ 和 $f,2$ 的位置关系，可以发现不需要一次额外操作当且仅当 $1$ 在 $f,2$ 之间，而这个等价于三个数呈 $f,1,2$ 的循环移位相对位置，那么判断一下即可

有了这些结论之后，我们也是能够从 $i\sim n$ 的 $f$ 值推出 $i-1\sim n$ 的 $f$ 值的，那么我们就这样每次扩展一个数即可

复杂度 $O(n)$

15. CF2062G - Permutation Factory [E] ⭐

题面

给定两个长为 $1\sim n$ 的排列 $p,q$，你需要进行若干次交换两个 $p$ 中元素，使得 $p=q$

交换 $i,j$ 的代价是 $\min(|i-j|,|p_i-p_j|)$，求最小代价和，并要求构造方案

$2\le n\le100$

题解

Sol

这个题看上去很不能做啊，但是它能做，这是怎么回事呢？

这个代价和两维都有关系，所以我们考虑画到二维平面上，由于是 $\min$，所以可以看作我们选择 $|i-j|$ 和 $|p_i-p_j|$ 中的一个做贡献

考察交换对 $(i,p_i)$ 和 $(j,p_j)$ 产生的影响，如果我们将移动看作 $(i,p_i)\rightarrow(i,p_j),(j,p_j)\rightarrow(j,p_i)$，那么总距离是 $2|p_i-p_j|$，如果看作 $(i,p_i)-(j,p_i),(j,p_j)-(i,p_j)$，那么总距离是 $2|i-j|$

那么我们就可以将这个看成两个点集之间的移动，一个想法就是把 $p$ 和 $q$ 中的点对应起来，代价和为曼哈顿距离

下界是显然的，接下来我们可以证明任意一个方案总是可以取到的：

我们首先考虑所有 $|i-j|$ 的移动，将问题放到一维上，那么假设 $i$ 要到 $a_i$，此时如果 $i,j$ 满足 $a_j\le i<j\le a_j$，那么我们交换这两个就是合法的，并且让总的 $|i-a_i|$ 减少了

容易发现一定可以找到这样的一对 $(i,j)$，具体地，考察 $a_1$ 和满足 $a_i=1$ 的 $i$，如果 $a_1\ge i$，那么直接交换 $(1,i)$ 即可，否则我们在 $i\rightarrow a_i$ 不断跳，一定会有一步向后跨过 $i$，取这一步和 $i$ 交换即可

那么我们只要运行一个二分图最大权匹配，然后按照如上构造方案即可

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

16. CF2062H - Galaxy Generator [E]

题面

一个 $n\times n$ 的点阵范围内，有一些整点

两个点之间存在直接联系当且仅当其 $x$ 坐标或 $y$ 坐标相同，并且连线上不存在其他整点

两个点连通当且仅当其可以通过若干条直接联系相互到达

你可以加入一个点 $P$，当且仅当加入这个点后，$P$ 和至少三个点直接联系

对于一个点集 $S$，定义 $f(S)$ 表示向 $S$ 中加入若干个点后，能得到的最少连通块数

现在给定一个点集，求这个点集所有子集的 $f(S)$ 之和，答案对 $10^9+7$ 取模

$1\le n\le14$

题解

Sol

考虑一个 $f(S)$：转化到二分图上连边，那么连通块就是边的连通块

孤立点没有任何影响，因此可以直接扔掉，接下来我们默认每个点都至少有一条边

此时加边操作就是相当于选择两条边 $(i,u)$ 和 $(i,v)$，然后将 $(i,[u,v])$ 的所有边均加上

也就是说，我们的每个连通块是一个区间对一个区间 $[l_1,r_1]-[l_2,r_2]$，并且连通块之间的区间不会相交

那么我们就完成了对于连通块结构的刻画，接下来考虑计数

一个简单的想法是我们求出 $f_{a,b,c,d}$ 表示左部点恰为 $[a,b]$，右部点恰为 $[c,d]$，内部的边形成连通块的方案数

那么这个看起来就像是容斥，但是怎么容斥呢？

首先我们有一个想法是容斥第一个连通块，那么设第一个连通块是 $[a,i]-[e,f]$，我们需要计算的就是 $[i+1,b]$ 和 $[c,e-1]\cup[f+1,d]$ 形成若干个连通块的方案数，并且连通块不能跨过 $[e,f]$

这个看着有点爆了，但是 $n$ 很小，我们直接设一个新的状态 $g_{a,b,S}$ 表示左部 $[a,b]$ 内的所有点，进行连边，最后连出来的所有连通块包含的点集为 $S$

此时我们容斥也方便了，直接减掉所有 $g_{a,b,S}$ 满足 $S$ 为 $[c,d]$ 的真子集即可，转移 $g$ 的时候枚举左部 $a$ 的连法转移

复杂度 $O(2^nn^4)$

17. CF2057F - Formation [E]

题面

给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，满足 $2a_i\ge a_{i+1}$

现在你可以执行 $k$ 次单点 $+1$ 操作，你需要保证操作完之后依然满足 $2a_i\ge a_{i+1}$ 的性质，求操作后最大 $\max(a_1,a_2,\cdots,a_n)$

$q$ 次询问，每次给定一个 $k_i$，求在 $k=k_i$ 的情况下问题的答案

$1\le n,q\le5\times10^4,1\le a_i,k_i\le10^9$

题解

Sol

我们一定是对着一个元素加，让他成为最大值

将第 $i$ 个位置加到 $K$，需要将每个 $a_j(j<i)$ 加到 $\lceil\frac K{2^{i-j}}\rceil$，那么我们只需要考虑 $\log V$ 个位置

由于一开始的序列是满足条件的，我们加的时候一定有一个界 $h_i$，表示 $h_i$ 及之前的位置均已经 $\ge\lceil\frac K{2^{i-j}}\rceil$，而对于 $i-h_i$ 相同的数，在 $K$ 变化时，我们只需要关心 $\sum_{j=h_i+1}^i a_j$ 最大的那个

也就是说我们可以将一个数分为 $\log V$ 个阶段，表示其 $h_i$ 的取值，那么总共只有 $O(n\log V)$ 次阶段的更新

而我们如果将询问排序，那么任意时刻我们只需要考虑一个询问，对于当前段，容易在 $\log V$ 的时间内计算任意 $K$ 的最小操作次数

那么我们首先计算一下右端点的操作次数，判断当前询问的答案是否在段内，若是则进行一个二分

这样的复杂度是 $O(n\log^2V)$ 的

18. WC2025 - nim 游戏 [K] ✔️

link

19. WC2025 - 士兵 [K]

题面

有一个长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$，你可以执行若干次区间 $-1$ 的操作，执行一次区间 $-1$ 的操作会花费 $m$ 的代价

你执行完所有操作之后，对每个 $i$，如果 $a_i\le0$，你会额外获得 $b_i$ 的收益

求收益减代价的最大值

$1\le n\le5\times10^5,1\le a_i\le10^9,|b_i|\le10^9$

题解

Sol

考虑 $dp_{i,j}$ 表示前 $i$ 个位置，第 $i$ 个位置被覆盖了 $j$ 次的最大收益

容易发现最优解中 $j$ 的取值一定要么是某个 $a_i$，要么是某个 $a_i-1$，那么我们的状态就是 $O(n^2)$ 的了，进行一些简单的搞就可以得到一个 $O(n^2)$ 的做法

接下来考虑优化，注意到我们的转移其实就是依次干了一下事情：

$dp_{i,j}\leftarrow dp_{i-1,j}$
$dp_{i,j}\leftarrow dp_{i,j+1}$
$dp_{i,j}\leftarrow dp_{i,j-1}-m$
$dp_{i,j}:=dp_{i,j}+b_i(j\ge a_i)$

这个看起来可以优化啊！

那么我们维护的其实是一个每一段的斜率都在 $[-m,0]$ 之间的折线，一次 $+b_i$ 相当于在某个位置的斜率上进行了修改

修改之后我们要继续维护 $[-m,0]$ 这个斜率范围，也就需要进行一些修改，我们分情况讨论：

$b_i\ge0$，那么会出现的只有斜率 $>0$，此时我们就是找到第一个 $\le v$ 的数，然后将一段摊平成 $v$
$b_i<0$，那么会出现的只有斜率 $<-m$，此时我们就是找到最后一个 $+im$ 之后 $\le v$ 的数，然后将一段摊平成 $v-im$

这些操作可以通过线段树上二分来维护，复杂度 $O(n\log n)$

20. UOJ Goodbye Jiachen - 红桃皇后 [K]

题面

定义一个 $2^n$ 个人之间的比赛如下：

将这些人两两匹配，胜者继续通过这种方式决出第 $1\sim2^{n-1}$ 名，败者继续通过这种方式决出第 $2^{n-1}+1\sim 2^n$ 名

那么一共会进行 $n2^{n-1}$ 场比赛

现在给出每场比赛的胜负关系，要求构造一种可能的排名，或者计数可能的排名数量，答案对 $998244353$ 取模

构造部分：$0\le n\le18$

计数部分：$0\le n\le12$

题解

Sol

不会搜索啊。

分析分析会发现没有什么能直接做的东西。

那可以初步考虑一下搜索。

那么我们就需要一个快速将这个集合分成两部分的方式，注意到我们取败者组的第一名，他一定是入度为 $1$ 的点，并且他所有能到达的点恰好是败者组的所有点

因此可以直接枚举这个败者第一名，然后搜索下去，复杂度是 $O(n!2^n\text{poly}(n))$ 的

事实上，加一个记忆化就可以获得 80 分了，这是怎么回事呢？

可以发现，过程中所有可能被切出的集合一定要有一个入度为 $0$ 的点 $s$，和一个出度为 $0$ 的点 $t$，那么此时一对 $s,t$ 只能生成一个可能被搜到的集合，这个集合就是 $s$ 在 $G$ 中能到达的点和 $t$ 在 $G$ 反图中能到达的点的交

也就是说我们生成的状态数不会很多，是多项式量级的

实际，出题人说这个最大是 $3^n$ 的，就是我们先选定一个标准划分，可以说明所有合法集合，找到它第一次被切开的位置，这时左右两边之间的边一定是一个完美匹配

那么状态数就是 $F(n)=2F(n-1)+F(n-1)$，状态大小和就是 $G(n)=2G(n-1)+2G(n-1)$ 的

而超立方体图也确实取到了这个界

至此，我们已经可以说明复杂度是 $O(4^nn^2)$ 的了

但事实上，对于构造的我们还可以更优，因为还可以证明一个结论，即如果存在任意一个解，那么我们第一步取任意形成完美匹配的合法划分都是可行的，这个也可以通过这张图的性质证明

那么构造部分的复杂度是 $F(n)=2^nn^2+2F(n-1)$ 的，即 $O(2^nn^3)$

这也是 80 分的复杂度。

优化到 100 分的话，注意到我们 $2^nn^2$ 的瓶颈在于我们要以 $n$ 个点为起点跑 bfs，并验证分割出来的集合之间的边是不是完美匹配

这个可以用位运算并行实现，即将第 $i$ 个点的 vis 标记一开始设为 $2^i$，然后按拓扑序扫每条边 vis[v]|=vis[u]，判断完美匹配也可以类似做

那么一层递归里的复杂度就优化成了 $O(n2^n)$

最后的复杂度是构造 $O(2^nn^2)$，计数 $O(4^nn)$

21. 联合省选 2022 - 填树 [S]

题面

给定一棵 $n$ 个点的树，以及一个常数 $K$，每个点有一个区间 $[l_i,r_i]$

你可以选择一条链上的点，将它们填上数，满足填的 $x_i\in[l_i,r_i]$

求有多少种填法使得所有填了的所有的 $x$ 的极差 $\le K$，以及这些填法的权值和之和，对 $998244353$ 取模

$1\le n\le200,1\le l_i\le r_i\le10^9,1\le K\le10^9$

题解

Sol

极差 $\le K$ 可以点减边进行容斥掉，我们对每个 $[a,a+K]$，计算所有点权都在这个区间内的答案，然后减去所有 $[a,a+K-1]$ 的答案

那么我们就要计算所有给定长度的区间的答案，对于一个区间，就是求树上的所有链的点权乘积和，可以用 dp 算出

而我们可以将这个过程分成 $O(n)$ 段，每一段一个点的点权都是关于 $a$ 的一次函数，乘起来不超过 $n$ 次，取一个前缀和就是 $n+1$ 次，那么拉插一下即可

复杂度 $O(n^3)$

22. 联合省选 2022 - 学术社区 [E]

题面

$n$ 个人发了 $m$ 条消息，每条消息为以下三种中的一种：

学术消息：有一个参数 $a_i$，表示其由第 $a_i$ 个人发出，不会对答案造成贡献
楼上型消息：有两个参数 $a_i,b_i$，由某个人 $a_i$ 发出，如果下一条消息由 $b_i$ 发出，则会获得 $1$ 的收益
楼下型消息：有两个参数 $a_i,b_i$，由某个人 $a_i$ 发出，如果上一条消息由 $b_i$ 发出，则会获得 $1$ 的收益

保证每个人至少发了一条学术消息

多组数据。

$1\le m\le77777,1\le m\le2.5\times10^5$

题解

Sol

我们要将这些消息连成一条链。

但是连成一条链不是很容易，注意到我们连的贡献只和相邻的元素有关，因此我们可以考虑用每个点去匹配它的后继

那么这样就是一些边的贡献为 $0$，一些边的贡献为 $1$，一些边的贡献的 $2$

贡献为 $0$ 的边我们可以直接不连，只需要讨论以下贡献为 $2$ 的边怎么处理了

可以猜测一下贡献为 $2$ 的边一定匹配上了，即如果我们能凑出贡献为 $2$，那么一定是凑上更优的，这个可以用简单的调整证明

那么我们只需要匹配最多的 $1$ 边就可以了。

但是这样匹配出来会有环，怎么办呢。

这时候每个人至少发了一条学术消息的性质就可以用上了，匹配出环的情况我们用学术消息来代一下，从环的某一个位置断开，这样操作完之后也是一个首尾都是原来人的链，因此我们可以继续将这个链当作“学术消息”来用

那么写一个最大匹配算出答案，然后构造即可

构造的时候先把所有环搞掉，然后再构造所有链，要不然会出问题。

复杂度 $O(m\sqrt m)$

23. 联合省选 2022 - 序列变换 [E]

题面

给定一个长为 $2n$ 的合法括号串，其中每个左括号都有一个权值，你可以进行如下两种操作：

对于原串中一个 (A)(B) 的子段，其中 $A,B$ 都是合法括号串（可以为空），交换中间的两个括号，将其变为 (A()B)，花费的代价为 $x$ 乘 (A) 中第一个左括号的权值，加上 $y$ 乘 (B) 中第一个左括号的权值，其中 $x,y\in\{0,1\}$
对于原串中一个 AB 的子段，其中 $A,B$ 都是合法括号串，你可以将其变为 BA

求将原串操作至没有 (A)(B) 子段的最小代价

$1\le n\le4\times10^5,1\le w_i\le10^7,x,y\in\{0,1\}$

题解

Sol

$x=y=0$ 是好做的。

这个操作看着很神秘，并且有交换两个合法子段这个操作，于是我们可以直接考虑上树

那么第二个操作就是交换两个儿子，也就是说儿子之间没有顺序，第一个操作相当于如下：

      o                            o
   /     \                         |
  x       y          ---->         x
/ A \   / B \                  /   |   \
-----   -----               / A \  y  / B \
                            -----     -----

并且我们最后需要达到的状态是一根链

容易发现我们可以从上到下考虑操作，每次将当前层的点只留一个，剩下的全部下放

那么注意到我们操作了 $h$ 次之后，当前层的点会包含所有深度 $\le h$ 的还没有放到链上的点

而对于 $x=0,y=1$ 和 $x=y=1$ 的情况，我们一层最小的代价分别是 $sum-mn$ 和 $sum+(cnt-2)mn$，并且我们把最大值挂到链上一定是可以取到这个代价，并对后面更优的

因此直接模拟即可，复杂度 $O(n\log n)$

对于 $x=1,y=0$ 的情况，我们现在的代价是 $(cnt-2)mn+w$，其中 $w$ 是我们要留在上面的点的点权

我们加上一个 $tot$，表示所有点权的和，那么这个 $w$ 就可以扔掉了，需要最后减掉一个在最下面的节点

其实这里已经可以枚举一下留到最后的是哪个元素，然后讨论一下直接做了，但是有更优美一点的做法

注意到我们集合大小一定是 $1,\cdots,1,2,\cdots,2,\ge3,\ge3,\cdots,\ge3,2,1$ 的，而对于 $\ge3$ 的部分，我们一定可以同时将最小值和最大值传下去

那么现在不确定的决策只有 $2,2,\cdots,2$ 段内的答案，注意到这里面贡献一定都全是 $0$，我们只需要决策选出哪个数传到最后即可

分两种情况讨论：

传进来这个数不需要留到最后，那么我们传一个最小值就行了
传进来这个数需要留到最后，那么这种情况是优的当且仅当其大于 $\ge3$ 段中所有的东西，也就是说其一定不会影响最小值，那么我们直接传一个最大值即可

分别跑一下这两种情况取最小值即可，复杂度 $O(n\log n)$

24. 联合省选 2022 - 最大权独立集问题 [E/K] ✔️

题面

给定一棵 $n$ 个点的二叉树，点有点权，你需要按照某种方式依次删掉这 $n-1$ 条边，删掉一条边 $(u,v)$ 会产生 $d_u+d_v$ 的代价，然后交换 $d_u,d_v$

求最小代价

$1\le n\le5000,1\le d_i\le10^9$

题解

Sol

如果我们把每个权值到的地方画出来，我们发现这个只由每个点的邻边之间的相对顺序决定，并且最后的答案就是

令 $dp_{u,i,j}$ 表示 $u$ 的子树内，从父亲边下来的箭头还能走 $i$ 的距离，从 $u$ 子树内走到 $u$ 子树外的节点是 $j$

注意到这个状态是 $O(n^2)$ 的，复杂度类似树形背包分析

转移直接枚举六种方式，可以用一些手段，同样优化到树形背包的分析，复杂度也是 $O(n^2)$ 的

25. QOJ9840 - Tree Partition [E] ⭐

题面

给定一棵 $n$ 个点的树，你需要删除 $x$ 条边，使得删完之后每个连通块内点的编号都是一个连续的区间

对 $x=0,1,2,\cdots,k$ 求删边的方案数，对 $998244353$ 取模

$1\le n\le2\times10^5,1\le k\le\min(n,400)$

题解

Sol

令 $dp_{i,j}$ 表示编号上前 $i$ 个点，分成 $j$ 个段的方案数，那么我们就需要一种刻画一段区间内的点是一个连通块的方案数

我们同时对这个树建出大根重构树和小根重构树，那么限制就相当于小根树上 $l$ 的子树包含所有 $[l,r]$ 的点，大根树上 $r$ 的子树包含所有 $[l,r]$ 的点

因此我们可以对小根树求出 $wl_i$，表示第一个 $\ge i$ 的点 $j$，且 $j$ 不在 $i$ 的子树内，对大根树求出 $wr_i$，表示第一个 $\le i$ 的点 $j$，且 $j$ 不在 $i$ 的子树内

那么我们的条件就是 $wl_l\ge r$ 且 $wr_r\le l$

直接用树状数组可以做到 $O(nk\log n)$

但是这个题并不想让我们带 $\log$，考虑如何把这个转移的 $\log$ 优化掉

做二维数点我们显然需要一些操作的性质，注意到如果我们填表并对 $r$ 扫描线的话，$wl_l\ge r$ 的限制就是单点修改，这个看起来没有什么可以优化的

那么考虑 $wr_r\le l$ 的限制，这个就是说我们要对当前子树中含有的编号最大的连续段求和

我们可以使用两个并查集完成这件事情，具体地，我们对 $r$ 扫描线，一个并查集 $D_1$ 维护此时所有编号形成的子树，另一个并查集 $D_2$ 维护所有编号连续段，扫到 $r$ 的时候，我们进行如下操作：

首先，将 $D_1$ 中 $r$ 和其所有儿子的等价类合并
然后不断判断，如果 $D_2$ 中包含 $r$ 的连续段为 $[i,r]$，判断 $i-1$ 在 $D_1$ 中是否和 $r$ 属于一个连通块，如果属于就在 $D_2$ 中对应更新
最后我们查询一下 $D_2$ 就可以同时得到 $wr$ 和 $wr$ 对应的 dp 和

在这个处理上进行单点修改是容易的，那么我们就在 $O(n\alpha(n))$ 的时间内解决了一层的转移

实际上还需要一点点卡常，可以先跑一遍把所有做的操作存下来，然后直接跑 $k$ 遍

这样时间复杂度就是 $O(nk+n\alpha(n))$，空间复杂度 $O(n)$

26. QOJ8806 - Summer Driving [E] ✔️

题面

给定一棵 $n$ 个点的树，初始有一个车在 $R$，Alice 和 Bob 可以轮流在开车，Alice 先手，每轮会进行如下的操作：

Alice 首先将开车移动经过恰好 $A$ 条之前没被经过的边
Bob 接着开车移动经过至多 $B$ 条边，不要求没被经过

这样进行若干轮之后 Alice 会无法操作，此时进入最终阶段，Bob 再开车移动经过至多 $B$ 条之前没被经过的边，然后游戏结束

Alice 希望终点的编号越大越好，Bob 希望终点的编号越小越好，求最后终点的编号

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

题解

Sol

注意到如果 $A\le B$，那么 Alice 不管怎么操作，Bob 一定能让最后的终点在 $1$

因此我们只考虑 $A>B$ 的情况，那么以 $R$ 为根，我们可以定义出状态：

$f_u$：Alice 从 $u$ 出发，不能走父亲边，其它边都可以走，终点的值
$ef_{u,v}$（ $ef_v$ ）：Alice 从 $u$ 出发，不能走父亲边以及 $u$ 到儿子 $v$ 的边，其它边都可以走，终点的值
$g_u$：Bob 从 $u$ 出发，终点的值

那么 $f_u$ 和 $ef_v$ 的转移分别就是取 $u$ 深度 $+A$ 的所有 $g$ 取 $\max$，如果不存在这样的点，则替换为 $w_u$，表示 $u$ 子树内前 $B$ 层的标号最小值，即最后一步操作

$g_u$ 的转移则是，取出不在 $u$ 的到根链上（可以取 $u$），距离 $\le B$ 的点的 $f$，和在 $u$ 到根链上，距离 $<B$ 的点的 $ef$，取 $\min$

点分治不好写，我们采取一种更好写的做法。

$f$ 和 $ef$ 的转移都是容易的，考虑 $g$ 的转移。我们在 lca 处处理所有转移，那么 lca 在 $u$ 处的转移，一定可以写成若干次给 $u$ 某个儿子子树中深度 $=i$ 的点的 $g$ 值对一个值取 $\min$，而转移 $f$ 和 $ef$ 时我们只需要一层的 $g$ 的最大值

因此我们可以考虑长剖线段树分别维护 $f,w,g$，线段树上维护一层的 $g$ 的最大值，那么合并两棵子树转移 $g$ 的时候，我们处理转移可以分为两种：

重子树 -> 轻子树：枚举轻子树的深度，对重子树深度前缀进行区间查 $\min f$
轻子树 -> 重子树：枚举轻子树贡献的深度，对重子树深度前缀进行区间 chkmin 轻子树该层最小的 $f$

那么总复杂度就是 $O(n\log n)$ 的

27. QOJ7199 - Bomb [E] ⭐

题面

数轴上有 $n$ 个炸弹，第 $i$ 个炸弹的位置在 $x_i$，你需要给每一个炸弹赋一个权值 $r_i$，这个炸弹爆炸时会引爆所有 $[x_i-r_i,x_i+r_i]$ 内的炸弹

求最小的 $\sum r_i^2$ 使得任意一个炸弹爆炸都会连锁引爆其余所有的炸弹

$1\le n\le3000,1\le x_i\le10^6$

题解

Sol

可以尝试分析一些贪心，会发现并不是很能贪。

考虑强行 dp：我们直接确定前 $i$ 个点的情况

注意到这个所有点都能互相到达可以看成所有点都能到 $1$，并且 $1$ 能到所有点

那么首先如果前面存在一个点，它能到的区间 $[x,y]$ 满足 $y<i$，那么后面的点再怎么选也救不回来了，因此我们不需要考虑这种情况

那么此时 $1$ 能到的区间必须是 $[1,i]$，否则就爆了。

此时考虑我们转移到 $i+1$ 的时候，需要将哪些点的 $[x-r,x+r]$ 的右端点向后延，注意到我们此时只用保留最靠右的那个，因为其它的点一定能到达它，所以延长其它点并没有意义

而此时我们也可以说明，不能到 $1$ 的一定是一段后缀，所有点一定要能到 $i$，要不然就无法延续了

那么我们就可以简单设出状态了，令 $f_{i,j}$ 表示前 $i$ 个点，最后一个能到 $1$ 的点为 $j$，最小的代价

$f$ 的转移有两种：

$i+1$ 没有延长到 $j$，那么我们需要把 $i$ 延续，让它能到 $i+1$，即加上 $(x_{i+1}-x_i)^2$ 转移到 $f_{i+1,j}$
$i+1$ 直接能到 $1$，那么我们需要把 $i$ 延续，并让 $i+1$ 至少能到 $j$，但此时我们不知道 $i+1$ 要有多长，因此我们枚举这个长度，再设一个状态

令 $g_{i,j}$ 表示前 $i$ 个点，所有点都能到 $1$，并且 $1$ 能到的最右端点为 $j$，其中 $j>i$

$g$ 的转移：

$i+1$ 直接挂在 $i$ 上，加上 $(x_{i+1}-x_i)^2$ 贡献到 $g_{i+1,j}$
$i+1$ 不挂在 $i$ 上，什么也不加贡献到 $f_{i+1,i}$
$i+1$ 成为新的最右端点，枚举这个端点加上 $\max(x_{i+1}-x_i,x_k-x_{i+1})$ 贡献到 $g_{i+1,k}$

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

注意到我们 $O(n^3)$ 的转移都是枚举长度，而这个长度是两个东西取 $\max$，那么注意到我们如果找到这个分界点 $pt$，对于 $\le pt$ 的部分，我们转移的代价都一样，而转移得越长显然越优，对 $>pt$ 的部分，我们转移更长的，显然不如一个一个点连过去，也就是说我们只要转移 $pt$ 和 $pt+1$ 即可

不过这个说法还是有一点纰漏的，我之前也没有考虑到。因为我们需要说明直接贡献到 $f_{i+1,i}$ 不会损失最优解，考虑此时我们计算不到的就是 $i+1$ 一直向右连，连到某个点 $x$，$x$ 又连回了 $i$，并且 $x$ 的右端点并没有超过原来的 $j$，此时我们 $g$ 中的状态会贡献到错误的 $j$ 上，但是注意到这种方案没有从 $x$ 开始一个一个连到 $i$ 优，所以不会出问题

复杂度 $O(n^2)$

28. QOJ10101 - Longest Increasing Subsequence [E] ⭐

题面

给定一个长为 $n$ 的序列 $a$，值域为 $[1,m]$，并且元素互不相同

你需要构造一个长为 $m-n$ 的序列 $b$，包含 $[1,m]$ 中没被 $a$ 包含的数，使得 $\text{LIS}(a+b)=\text{LIS}(b+a)$

给出构造或返回无解

$1\le n<m\le10^6$

题解

Sol

注意到有一个很愚蠢的方式就是把 $b$ 中元素都降序排

这个构造在一些情况下是对的，具体地，我们找到 $a$ 中 LIS 的最大开头 $x$，和 $a$ 中 LIS 的最小结尾 $y$

如果我们同时拥有 $y$ 的数，或者同时不拥有，那么降序排就一定是对的

否则我们考虑解决一下这个问题，不妨假设我们有的是 $>y$ 的数，那么不管我们怎么操作，新的 LIS 一定至少是原来的 LIS $+1$

那么考虑如下一个策略：我们将 $b$ 中元素升序排序，寻找最小的 $p$ 使得 $\text{LIS}(b[1:p]+a)$ 为原来的 LIS $+1$，此时我们判断令 $b$ 为 $b[p+1:m-n]$ 降序排，然后 $b[1:p]$ 升序排，是否满足条件，如果不满足条件就无解

这是正确的。

证明可以考虑：

如果我们这个排法不合法，那么一定是在计算 $a+b$ 的 LIS 的时候，我们的 $b[1:p]$ 段被某个 $a$ 中的子序列截胡了，使得其 LIS 大于原 LIS $+1$，称这个子序列为 $e$，并且被截胡的子序列开头是 $b_q$，此时我们得到的条件叫做 $|w|+p\le e+p-(q-1)$

同时我们称 $b[1:p]+a$ 的 LIS，在 $a$ 中的部分称为 $w$

那么如果这种情况下这个问题有解，考察此时的 $b+a$ 的 LIS，设其在 $b$ 和 $a$ 中的部分分别叫 $u,v$，那么 $v$的开头一定 $\ge b_p$，否则无法达到原 LIS $+1$，也就是说 $|v|\le|w|$，而此时我们考虑 $a+b$ 的 LIS 的时候，再继续用 $e$ 去截 $u$，截到的长度一定大于等于 $|u|-(q-1)$，那么我们就是在比较 $|u|+|v|$ 和 $|e|+|u|-(q-1)$ 的大小，可以发现做差之后就是原来的式子，因此一定也满足 $\text{LIS}(b+a)<\text{LIS}(a+b)$，从而不可能有解

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

29. QOJ10104 - World of Rains [E] ⭐

题面

有一个二维平面上 $n\times m$ 的矩形，一开始这个平面里都没有雨滴

给定一个长为 $S$ 的序列 $d_1,d_2,\cdots,d_S$，接下来会有 $S+1$ 个时刻，每一个时刻会依次发生如下三个事情：

降雨：所有当前没有雨滴的位置，你可以独立选择是否添加雨滴
移动（除了 $S+1$ 时刻）：原来在 $(x,y)$ 的雨滴会移动到 $(x+1,y+d_i)$
消失：所有在矩形外面的雨滴会消失

你需要求出所有 $S+1$ 个时刻上的 $n\times m$ 矩形，一共有多少种不同的状态，对 $998244353$ 取模

多组数据，$1\le n,m,S\le5\times10^5,|d_i|\le10^9,\sum S\le5\times10^5$

题解

Sol

注意到如果我们看作这个矩形在平面上移动，那么我们要算的其实就是所有出现过的空格子的存在时间加 $1$ 的乘积

如果我们把矩形移动过程中的底边拉出来，会有若干个行数为 $1$，列数为 $n$ 的矩形，我们将它按位置排到一起，那么一个最后一行的存在时间就是向下走的格子数，使得其还在这个图形内

那么我们按列扫描线，维护所有行的连续段，一个连续段内的贡献是可以用一些阶乘预处理的

复杂度可以做到 $O(S\log S)$

30. QOJ10111 - Dividing Chains [E]

题面

对于一个序列 $a_1,a_2,\cdots,a_n$

首先有一个集合 $S=\{1,n+1\}$，接下来我们重复进行如下操作 $n-1$ 次：

选择任意一个 $1\le x\le n$，满足 $x\not\in S$
找出 $S$ 中 $x$ 的前驱 $l$ 和后继 $r$，你可以选择是否将 $[l,r-1]$ reverse
将 $x$ 加入 $S$

现在给定一个递增的序列 $a$，你需要计算最后可以得到多少序列 $a$，对 $998244353$ 取模

$1\le n\le500,1\le a_i\le n$

题解

Sol

这个东西是一个不断合并的过程，我们可以看作每次拿两个位置相邻，且值域也相邻的段合并起来，最后可以合并成一个就是合法的序列

考虑对最后一步进行 dag 容斥，我们枚举一个划分点的集合，认为每个划分点两边都可以合并

那么看起来这个意思就是所有段的值域依次递增或递降，那么我们就可以列出一个 $O(n^3)$ 的 dp 了，令 $f_{l,r}$ 表示 $[l,r]$ 区间可合并的方案数，那么我们再开一个辅助数组，每次并上去一个段即可

但是这样不对。

首先全相等的情况比较难处理，因此我们先判掉。

此时可以发现还有一种额外情况，就是我们分了若干个全 $mn$ 段，并且中间有一个不是全 $mn$ 段的，这样虽然段的值域不是递增或递降，但还是合法的，对于 $mx$ 同理

那么我们把两种数的情况也判掉，剩下的推一下式子可以发现一定是恰好两个 $mn$ 没有被分到中间的段里时贡献才不为 $0$，把这种情况加上即可

复杂度 $O(n^3)$

31. QOJ4878 - Easy Problem [K] ✨

题面

有 $n$ 只鸡排成一排，第 $i$ 只鸡最多能吃 $a_i$ 的食物，有 $m$ 个喂食器，第 $i$ 个喂食器能给 $[l_i,r_i]$ 内的鸡喂总量不超过 $c_i$ 的食物

现在对于 $p=1,2,\cdots,n$，求如果只保留区间包含 $p$ 的喂食器，最多能够给鸡喂多少食

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

题解

Sol

完全不会啊。

这个题就是要求我们求一个最大匹配，这是一个区间图，因此我们可以贪心，但是我们有这个条件，即所有区间都经过一个点 $p$，因此可以考虑使用更容易维护的方式

如果我们确定了每个喂食器，分别有多少容量在左边和右边喂食，那么我们就可以根据 hall 定理简单地算出两边的最大匹配，就是前缀 $a$ 和减去前缀喂食器容量之和

那确定左边和右边喂食的容量，这个我们可以使用贪心，具体地，我们认为一开始所有容量都在右边匹配，我们每次找出 $l$ 最小的喂食器，如果将其右边的容量 $-1$ 不会使右边的匹配改变，那么我们就可以将这个容量改到左边

具体地，我们开两棵线段树，右边的线段树每个位置 $i$ 维护 $[r 在 [p,i] 内的喂食器的容量之和]-\sum a[p:i]$，左边的线段树类似维护，称这个值为 $f$，那么 $\max f$ 就是失配数，我们的操作相当于判断后缀 $-1$ 会不会使 $\max f$ 变小，如果不会则进行 $-1$

考虑换一个方式维护这件事情，我们找到 $f$ 数组最靠左的最大值位置 $s$，那么我们找到，$r$ 在 $s$ 左边最小的 $l$，将这个区间操作，重复进行操作直到无法进行为止

我们从左到右移动 $p$，移动一次的时候我们会删除一些区间并加入一些区间，考虑这对我们贪心过程的影响：

我们删除区间之后，每个区间分到左边的流量应该不会变得更少，也就是说我们可以在当前的基础上继续贪心
加入的区间都是 $l$ 最大的，也就是说并不会影响我们之前的贪心过程

那么最后的结论就是我们在加入区间之后，继续执行贪心即可

考虑分析这样的复杂度：这个复杂度就是我们取出一个区间的次数 $\times\log$，考虑分析我们会取出多少次区间

我们取出一个区间的操作是将 $s$ 减小到左边最大值，或者这个区间已经把容量用完了扔掉了，而这种事情显然只会发生 $O(m)$ 次

令势能为线段树上 $左儿子最大值<右儿子最大值$ 的节点数量，那么我们会执行 $O(n)$ 次区间加的操作，这些操作只会让势能增加 $O(n\log n)$，而我们每次操作至少会让势能减少 $1$（在 $s$ 和前面最右最大值的 lca 处），因此最多取出 $O(n\log n)$ 次区间

那么最后的复杂度就是 $O(n\log^2n)$

32. AWTF2022 - Jewel Pairs [K] ✨

题面

有 $n$ 个宝石，第 $i$ 个宝石的颜色为 $c_i$，价值为 $v_i$

两个宝石可以匹配当且仅当 $c_i\neq c_j$ 且 $v_i+v_j\le L$，其中 $L$ 为一个给定的常数

你需要求一个这 $n$ 个宝石之间的匹配（不一定全匹配上），使得所有匹配上的宝石的 $v_i$ 之和尽可能大

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

题解

Sol

存在这样一个结论：我们按照所有宝石按 $v$ 从大到小排序，依次考虑所有宝石 $x$，维护一个当前匹配的集合 $S$，如果将 $x$ 加入 $S$ 还存在一个匹配包含 $S$ 中所有的宝石，那么就将 $x$ 加入 $S$，最后得到的 $S$ 就是最优解

考虑维护这件事情。

首先我们把所有 $v>\frac L2$ 的东西考虑了，此时我们要做的事情就是相当于对一个大点的集合，判断其是否能够和一些小点进行匹配

我们令 $w_i=L-v_i$，那么一个小点 $i$ 和一个大点 $j$ 能匹配的条件就是 $v_i\le w_j,c_i\neq c_j$，以大点为 $S$，小点为 $N(S)$ 使用 Hall 定理

摊在值域上考虑，容易发现我们 $S$ 和 $N(S)$ 选择的东西一定形如：一段区间 $[l,r]$ 内，选择所有颜色 $=c$ 的大点，和颜色 $\neq c$ 的小点，然后选择所有 $<l$ 的大点和小点

这个东西可以写成 $l$ 和 $r$ 的一些前缀和加减，并且可以发现最优的选择一定满足 $l$ 和 $r$ 处都有 $=c$ 的点，否则往里缩一下一定更优，因此我们可以从小到大遍历 $w_i$，对每个 $c$ 维护处 $mn_c$ 表示当前 $S-|N(S)|$ 的最大值，以及其它求这个东西的辅助数组，从而做到 $O(1)$ 加入一个新大点并判断是否合法

那么这样做完之后，我们就能得出有哪些大点会在最后的匹配里，我们把其余没有用到的大点都删除。

此时考虑有哪些小点可以匹配，注意到我们小点的匹配是和颜色众数有一定关系的

对每种颜色 $f(c)$，我们求出 $c$ 颜色的小点，在最后的方案里，最少有多少个不和大点匹配，这个可以模拟匈牙利的过程，把 $c$ 颜色的小点放在前面进行匹配，由于匈牙利不会退掉已经匹配的点，所以实际上相当于我们把 $c$ 颜色的小点和所有大点去求最大匹配，这个也是可以通过一些求和算出来的

算出 $f(c)$ 之后，我们令 $rem$ 为此时的小点数减大点数，那么匹配之后我们一定会剩下 $rem$ 个小点内部匹配，分两种情况讨论：

$2\max f(c)>rem$，那么我们找到那个超过的颜色 $c$，我们要去除恰好 $2f(c)-rem$ 个 $c$ 颜色的小点，这样就可以使得剩下的小点全部匹配，并且这个去除是优先去除权值较小的
这个可以通过求一个颜色 $c$ 和右部点字典序最大的匹配得出，我们把没匹配上的最小的 $2f(c)-rem$ 个删去，这样是正确的，因为对于任意最大匹配，我们可以经过调整，让这个匹配的颜色为 $c$ 的点都是我们选出来的这个字典序最大的匹配，具体地可以通过把两个匹配叠合起来说明
$2\max f(c)\le rem$，此时讨论 $rem$ 的奇偶性：
- $rem$ 为偶数，此时我们可以说明一定存在一种匹配方式使得剩下的东西不存在颜色的绝对众数，我们任选一个匹配，如果此时剩下的颜色存在一个绝对众数 $c$，那么我们再取达成 $f(c)$ 的匹配，这个匹配满足 $2f(c)\le rem$，那么我们把两种匹配叠合一下，每次调整一条增广路，失配的颜色为 $c$ 的小点会不断 $-1$，一定有一个时刻恰好是 $\frac12 rem$，此时小点一定不存在绝对众数
- $rem$ 为奇数，那么我们就需要删掉一个任意颜色的点，此时我们也是把大点和小点求一个字典序最大的匹配，删除最小的点

总复杂度可以在 $O(n\log n)$ 内解决，除了排序之外都是线性的