解题思路分析

cyffff · 2024-03-05 20:48:39 · 个人记录

计数

Merging Cells P

有 n 个初始大小为 s_{1\dots n} 的细胞从左到右排成一行。当存在多个细胞时，均匀地随机选择一对相邻细胞，其中较大的细胞会吞掉较小的细胞，若它们大小相同则编号较大的细胞会吞掉编号较小的细胞。对 \forall i\in[1,n] 求出最终 i 细胞存活的概率。

**** 区间 DP，但是传统设计 $f_{l,r,i}$ 表示 $[l,r]$ 得到 $i$ 的概率，时间复杂度 $O(n^4)$，难以优化。思维方向是**降维或者正难即反**。上述做法枚举了最后一次合并，将小区间合并成为大区间，不妨考虑**时光倒流**将大区间分裂成为小区间，设计 $f_{l,r}$ 表示最终答案在 $[l,r]$ 的概率。 $$f_{l,r}=\sum_{1\le k<l}^{s(k,l-1)\le s(l,r)}\dfrac{f_{k,r}}{r-k}+\sum_{r<k\le n}^{s(r+1,k)<s(l,r)}\dfrac{f_{l,k}}{k-l}$$ 时间复杂度 $O(n^3)$，需要继续优化。显然对于一个区间 $[l,r]$ 只有一个区间内的 $k$ 是合法的，可以双指针求出。以合适的方式选择前缀和、后缀和优化即可做到 $O(n^2)$。 **** ### [永恒 / Eternity](https://www.luogu.com.cn/problem/P10707) 对于一个由自然数组成的可重集 $S$，定义其权值为子集异或和的最大值。求有多少大小为 $n$ 的可重集 $S$ 满足其权值为 $m$。 $n\le 10^5$，$m\le 2^{60}$。 **** 限制子集异或和最大值，考虑对线性基进行 DP。为了避免将张出空间相同的线性基记重，我们需要对消元后的线性基进行计数，即要求不存在两个线性基内元素，其中一个包含另一个的最高位。设 $f_{i,j}$ 表示只考虑不低于 $i$ 的位，已经在线性基内插入了 $j$ 个数的方案。 - 如果 $m$ 的第 $i$ 位为 $1$：线性基第 $i$ 位要么有数，要么这 $j$ 个数异或起来第 $i$ 位为 $1$，即选取奇数个数第 $i$ 位填一，$f_{i,j}=f_{i+1,j-1}+2^{j-1}f_{i+1,j}$； - 如果 $m$ 的第 $i$ 位为 $0$：线性基第 $i$ 位必须无数，并且这 $j$ 个数异或起来第 $i$ 位为 $0$，即选取偶数个数第 $i$ 位填一，$f_{i,j}=2^{j-1}f_{i+1,j}$。考虑将线性基对应回序列，容易发现大小相同的线性基的方案数也是相同的。大小为 $i$ 的线性基能异或出 $2^i$ 个数，直接插板得到 $\displaystyle\binom{2^i+n-1}{n}$，但有一些方案的线性基只是原线性基的子集。我们设 $g_i$ 表示一个大小为 $i$ 的线性基能由多少个大小为 $n$ 的可重集得出，$h_{i,j}$ 表示对于一个大小为 $i$ 的线性基 $A$，有多少个大小为 $j$ 的线性基 $B$ 能异或出的数是 $A$ 能异或出的数的子集。将 $A$ 没有数的位忽略，从小到大考虑每一位转移： - $B$ 这一位有数：前 $i$ 位中 $B$ 没有数的 $i-j$ 位在 $A$ 中的数都可以任意异或到这个数上，$h_{i,j}\gets 2^{i-j}h_{i-1,j-1}$； - $B$ 这一位无数：$h_{i,j}\gets h_{i-1,j}$。显然，$g_i=\displaystyle\binom{2^i+n-1}{n}-\sum_{j=0}^{i-1}h_{i,j}g_j$，答案即为 $\displaystyle \sum_{i=0}^{\log m+1}f_{0,i}g_i$，时间复杂度 $O(n\log m)$。一个重要的思考方向是如何**规定转移顺序以消除后效性**。 **** ### [[2024 联考 II Day12] 自然选择号](http://192.168.102.138/JudgeOnline/problem.php?cid=2189&pid=0) 有一个 $n\times m$ 的网格图，格子有黑白二色。给出 $b_{1\dots m}$ 表示第 $i$ 列的黑格数量，令 $a_{1\dots n}$ 表示第 $i$ 行的黑格数量，求出有多少种可能的 $a$，对 $10^9+7$ 取模。 $n,m\le 80$。 **** **计数问题先考虑判定问题**。建二分图，行 $i$ 需要恰好匹配 $a_i$ 列，列 $i$ 需要恰好匹配 $b_i$ 行。有两种思路处理： - 使用 **Hall 定理**，则对于任意的 $S\sube[n]$，$\displaystyle\sum_{i\in S}a_i\le \sum_{j=1}^m\min(b_j,|S|)$； - 网络流建模，要求最大流即最小割等于 $s=\sum b$，则考虑割了 $S$ 这些行和 $T$ 这些列，要求 $\displaystyle\sum_{i\in S}a_i+\sum_{j\in T}b_j+(n-|S|)(m-|T|)\ge s$。两个结果是等价的，于是对 $a$ 的限制就是 $a$ 中前 $i$ 大的和需要小于等于 $r_i$，直接 DP 即可做到 $O(n^5)$，可以通过。 **** ### [[2023 NOI模拟 Day10] Hitori 的旅行](http://192.168.102.138/JudgeOnline/problem.php?cid=2002&pid=0) 给你一个 $n$ 个点 $m$ 条边的有向无环图以及一个整数 $w$，每个点有点权 $v_i(v_i\le w)$，定义一种旅行方案为选定一个起始点 $s$，从 $s$ 引三条不同的路径到达三个点 $a,b,c$，定义该方案的权值为 $v_a+v_b+v_c$。对于 $\forall k\in[1,3w]$ 求出权值为 $w$ 的方案数量。答案对 $10^9+7$ 取模。 $n\le 10^4$，$m\le 3\times 10^4$，$w\le 400$，$T\le 5$。 **** 考虑容斥掉三条路径不同的限制。计算 $F_{u,1/2/3}(x)$： $$F_{u,i}=x^{i\cdot v_u}+\sum_{v}F_{v,i}(x)$$ 其中 $u\to v$ 有边。则答案就为 $\frac16\sum_{i}\left(F_{i,1}^3(x)-3F_{i,1}(x)F_{i,2}(x)+2F_{i,3}(x)\right)$。直接 FFT 时间复杂度 $O(nw\log w+mw)$，无法通过。注意到多项式次数较低，但是运算次数较高，**考虑拉格朗日插值，那么只需要维护点值序列**。时间复杂度 $O((n+m)w+w^2)$，可以通过。 **** ### [[省选联考 2024] 重塑时光](https://www.luogu.com.cn/problem/P10221) 给定整数 $n,k$。对于一个长为 $n$ 的排列 $p$，其有 $n+1$ 个间隙，将 $k$ 块隔板分别插入某个间隙，得到 $k+1$ 段可以为空的子段。给定 $m$ 条限制 $(u,v)$，定义一个排列 $p$ 是好的当且仅当对于所有限制 $(u,v)$，$p$ 中 $u$ 的出现位置均早于 $v$ 的。求对于随机的排列 $p$ 以及随机的间隙插入方法，有多大的概率可以重排子段使得重排后的排列为好的。答案对 $998244353$ 取模。 $n\le 15$，$m\le \frac{n(n-1)}{2}$。 **** 重新描述题意：给你一个 DAG，对于每个 $t\in[1,k+1]$，求每个点定一个颜色 $c_i\in[1,t]$，要求将每个颜色的所有点缩起来之后不成环，且每个颜色至少有一个点。对答案的贡献为每个颜色的点的导出子图的拓扑序数量的乘积。记 $\text{in}(s)$ 表示 $s$ 内点的入点集合与 $s$ 的并集。设 $f_s$ 为 $s$ 内点集的导出子图的拓扑序数量，$g_{s,i}$ 表示 $s$ 内点已经钦定了 $i$ 个非空颜色的答案，$h_{s,i}$ 表示 $s$ 内点已经钦定了 $i$ 个非空颜色且这些颜色之间互相没有连边的答案： $$f_s[i\notin\text{in}(s)]\to f_{s\cup\{i\}}$$ $$h_{s,i}f_t[\text{in}(s)\cap t=\varnothing][s\cap \text{in}(t)=\varnothing]\to h_{s\cup t,i+1}$$ $$g_{s,i}h_{t,j}[\text{in}(s)\cap t=\varnothing]\cdot (-1)^{j+1}\to g_{s\cup t,i+j}$$ 其中 $g$ 的转移为枚举出点为 $0$ 的颜色对应的点集。直接枚举超集计算可以做到 $O(3^nn^2)$。我们要求的只有 $g_{u,i}$，**注意到这是一个类似背包的问题，则不妨将第二维看为多项式，代入 $\bm{k+2}$ 个点值计算转移，最终拉插即可**，时间复杂度 $O(3^nn+2^nn^2)$。 **** ### [[2024 联考 III ACM] Xiang](https://codeforces.com/gym/542554/problem/J) 求有多少 $n$ 个点的有标号无根树满足每个点度数不超过 $d$ 且存在一条链同时包含节点 $1\sim k$。对 $998244353$ 取模。 $n\le 500$。 **** 特判 $k\le 2$。称 $1\sim k$ 为关键点，**尝试向仅考虑关键点的状态中加入非关键点**。将包含所有关键点的最短的链取出，将该链上所有关键点从左至右重编号为 $1\dots k$，将答案乘上 $\dfrac{k!}{2}$ 即可。关注这条链，链上每个点分别挂了一些链外子树。将链分为三部分：第一部分包含 $1$ 到 $2$ 路径上所有点（包含 $1$ 且不包含 $2$）与其挂的子树以及节点 $2$；第三部分包含 $k$ 与其挂的子树；称一个第二部分为对于一个 $i\in[2,k-1]$，$i$ 到 $i+1$ 路径上所有点（包含 $i$ 且不包含 $i+1$）与其挂的子树以及节点 $i+1$。我们在第一部分中钦定一个一度点作为 $2$，$i$ 的第二部分中钦定一个一度点作为 $i+1$，于是整棵树由一个第一部分，$k-2$ 个第二部分，一个第三部分组成。设 $f_i$ 表示 $i$ 个点的有标号树，每个点的度数 $\le d$ 且钦定了一个不是 $1$ 的一度点的方案数；$g_i$ 表示 $i$ 个点的有标号树，每个点的度数 $\le d$，$1$ 的度数 $\le d-1$，钦定了一个不是 $1$ 的一度点的方案数；$h_i$ 表示 $i$ 个点的有标号树，每个点的度数 $\le d$，$1$ 的度数 $\le d-1$ 的方案数。则 $f_i,g_i,h_i$ 分别表示大小为 $i$ 的第一二三部分的数量。由 Prufer 序列，如果 $i$ 的度数为 $d_i$，那么构成树的方案数为 $\displaystyle\binom{n-2}{d_1-1,d_2-1\dots,d_n-1}$。考虑求 $f_i$，设 $t_{i,j,0/1}$ 表示考虑完前 $i$ 个点，他们的度数和为 $j$，是否已经钦定了一个非 $1$ 一度点即可。$g,h$ 同理。求出 $f,g,h$ 后做个背包就能求出答案，总时间复杂度 $O(n^3)$。 **** ### [[2023 NOI模拟 Day15] 矩形](http://192.168.102.138/JudgeOnline/problem.php?cid=2007&pid=0) 有一个 $n\times m$ 的矩形，每个格子上有一个数，这些数构成 $1\sim nm$ 的排列。定义一个子矩形为选取一个行的集合和一个列的集合，保留所有同时属于两个集合的格子所形成的矩形。求有多少个子矩形满足每一行和每一列均单增或单减。 $n,m\le 20$。 **** 枚举行的集合，对列进行 DP。我们可以先根据选取的行的集合排除掉一些列，此时便无需关注列的限制。行的限制我们需要记录每一行是单增还是单减，但是我们发现**只需要记录选取的任意两列就能唯一确定状态**，所以令 $f_{i,j}$ 表示最后选的两列为 $i,j$ 的方案数，直接转移即可做到 $O(2^nn^3)$。进一步地，我们将状态改为 $f_{s,i}$ 表示选取的最后一列为 $i$ 且行状态为 $s$ 的方案数，虽然状态数很大，但是只需枚举选取的最后一列即可确定 $s$。时间复杂度 $O(2^nn^2)$。 **** ### [[2023 NOI模拟 Day23] 匹配](http://192.168.102.138/JudgeOnline/problem.php?cid=2034&pid=2) 给定四个整数 $n,m,l,r$ 和一个数组 $p_{1\dots 2n,0\dots m}$，你需要构造一张以 $1\sim n$ 为左部点、$n+1\sim 2n$ 为右部点的二分图满足其边数为 $m$ 且最大匹配在 $[l,r]$ 中，记该二分图中点 $i$ 的度数为 $\text{deg}(i)$，求出 $\sum_{i=1}^{2n}p_{i,\text{deg}(i)}$ 的最小值。保证有解。 $n,m\le 40$。 **** 二分图的最大匹配为 $x$ 的充要条件为可以将左部点划分为两个不交集合 $A,B$，右部点划分为两个不交集合 $C,D$ 满足： - $|A|+|D|=x$。 - $B,C$ 间无边。 - $A,C$ 间有大小为 $|A|$ 的匹配，$B,D$ 间有大小为 $|D|$ 的匹配。不妨考虑对左右分别 DP 再合并计算答案。以左部点为例，考虑依次钦定每个点的度数并将其划分入集合 $A$ 或 $B$。根据 Hall 定理，题目的限制可改写为： $$\begin{cases}l\le |A|+|D|\le r\\\sum_{p=1}^n\text{deg}(p)=\sum_{q=n+1}^{2n}\text{deg}(q)=m\\\sum_{p\in A}\text{deg}(p)\ge\sum_{q\in C}\text{deg}(q)\\\sum_{p\in B}\text{deg}(p)\le\sum_{q\in D}\text{deg}(q)\\|A|\le \sum_{q\in C}[\text{deg}(q)\ne 0]\\|D|\le \sum_{p\in B}[\text{deg}(p)\ne 0]\\\forall p\in A,\text{deg}(p)\ne 0\\\forall q\in D,\text{deg}(q)\ne 0\end{cases}$$ 于是设 $f_{i,a,b,c,d}$ 表示考虑了前 $i$ 个点，后四维分别为 $\sum_{p=1}^i\text{deg}(p)$，$|A|$，$\sum_{p\in A}\text{deg}(p)$，$\sum_{p\in B}[\text{deg}(p)\ne 0]$ 时的最小代价即可。令 $n,m$ 同阶，时间复杂度 $O(n^6)$，可以通过。 **** ### [简单的树上问题](https://www.luogu.com.cn/problem/P10717) 给你一颗 $n$ 个结点的树，有 $k$ 次操作，第 $i$ 次操作： - 每个点初始都处于未激活状态； - 以 $p_{i,j}$ 的概率激活点 $j$； - 对于每个未激活的点 $i$，如果存在激活的结点 $j,k$ 且 $i$ 在 $j$ 到 $k$ 的路径上，则 $i$ 也会被激活。给出 $v_{i,s}$ 表示当 $i$ 在 $s$ 这些操作被激活时的权值。对于某种可能的情况，记 $S_i$ 为结点 $i$ 在哪些操作中被激活了，整棵树的权值为 $\prod_{i=1}^nv_{i,S_i}$。请求出这棵树的权值的期望。 $n\le 100$，$k\le 8$。 **** $k=1$ 时设 $f_{u,0/1/2}$ 分别表示「$u$ 子树内没有结点被激活」/「$u$ 子树内有结点被激活且钦定子树外没有结点被激活」/「$u$ 子树内有结点被激活且钦定子树外有结点被激活」时 $u$ 子树内的期望权值。合并子树的过程中需要将仅有一个子树内有结点被激活与有大于等于两个子树内有结点被激活分开讨论，为后者新建一个状态 $3$，此时子树外是否有结点被激活均可。令 $t_{0/1/2/3}$ 分别表示已经合并的子树的信息，共有 $8$ 种转移： - $(0,0)\to 0$； - $(0,1),(1,0)\to1$； - $(0,2),(2,0)\to2$； - $(2,2),(3,0/2)\to3$；我们再考虑 $u$ 是否在初始时被激活，将 $v$ 乘入，再将 $3$ 状态下放给 $1/2$ 状态，$u$ 结点就计算完毕了。考虑 $k$ 更大的情况。注意到直接给定了 $2^k$ 种情况的权值，提示我们将 $k$ 次操作一同考虑。将 $k$ 次操作中 $u$ 的状态压缩，状态改写为 $f_{u,\{0,1,2\}^k},t_{\{0,1,2,3\}^k}$。于是我们可以得到一个非常暴力的做法： - 加入一个子树，枚举 $k$ 次操作的转移，转移共有 $8$ 种，复杂度为 $O(8^k)$； - 决定 $u$ 的初始激活状态，直接枚举 $u$ 初始激活的操作集合，复杂度为 $O(8^k)$； - 将 $3$ 状态传至 $1/2$ 状态，直接枚举每个 $3$ 传给 $1$ 还是 $2$，复杂度为 $O(8^k)$。总复杂度 $O(n8^k)$，无法通过。不妨从看起来比较好下手的第三部分开始优化，我们注意到**这是一个类似高维后缀和的操作，我们可以类似地逐位下传**，复杂度降至 $O(k4^k)$。第二部分也可通过类似的思路逐位加入 $u$ 的初始激活信息做到 $O(k4^k)$。接下来就是最为困难的第一部分了，我们依旧尝试用类似的思路解决。注意到 $0/2/3$ 是好求的，因为这些状态不会向外转移。由此我们发现 **$3$ 状态的信息可由 $0/2/3$ 减去 $0/2$ 得到**，我们转移前使用高维前缀和将每一维为 $0/2$ 的状态加给 $3$ 状态，只考虑 $0/1/2$ 的 $5$ 种转移和 $(3,3)\to 3$ 共 $6$ 种转移，转移完再做高维前缀差分。加入一个子树复杂度降至 $O(6^k)$。总复杂度 $O(n6^k+nk4^k)$，可以通过。 **** ### [Tenzing and Random Operations](https://www.luogu.com.cn/problem/CF1842G) 给你一个长为 $n$ 的序列 $a_{1\sim n}$ 和一整数 $v$，对该序列进行 $m$ 次操作。每次操作中，等概率地随机选择一整数 $i \in [1, n]$，对所有的 $j \in [i, n]$，赋值 $a_j \gets a_j+v$，求出 $m$ 次操作后 $\prod_{i=1}^n a_i$ 的期望值。答案对 $10^9+7$ 取模。 $n\le5000$，$m\leq10^9$。 **** 若令 $c_i$ 为在 $i$ 位置处进行的后缀加操作次数，不仅状态难以设计，其方案数 $\displaystyle\binom{m}{c_1,c_2,\dots,c_n}$ 也无法计算。考虑区分 $m$ 次操作加的 $v$，设第 $i$ 次操作了位置 $p_i$，则答案为： $$\displaystyle\frac{1}{n^m}\prod_{i=1}^n\left(a_i+\sum_{j=1}^mv[p_j\le i]\right)$$ 我们发现最后乘入贡献的操作数量只有不超过 $n$ 个，而未乘入贡献的操作并不需要关心其位置。**考虑贡献延后计算，在将值乘入贡献时再为其确定是哪一次操作、操作的位置是什么**。设 $f_{i,j}$ 表示已经考虑了前 $i$ 个位置，已经确定了 $j$ 次操作及其位置的贡献和，可以转移。时间复杂度 $O(n^2)$。 **** ### [Emotional Fishermen](https://www.luogu.com.cn/problem/CF1437F) 给你一个长为 $n$ 的序列 $a_{1\sim n}$，定义一个排列 $p_{1\sim n}$ 是好的当且仅当对于 $\forall i\in[1,n]$ 均有： - 令 $x=a_{p_i},y=\max_{j=1}^{i-1}a_{p_j}$，满足 $2x\le y$ 或 $2y\le x$。求有多少个排列是好的，对 $998244353$ 取模。 $n\le 10^5$。 **** **将计数问题转化为概率问题可避免对无关部分的讨论，使形式更简洁。** **考虑最终序列的所有前缀最大值，设其为 $b_{1\dots k}$，尝试向其中插入序列剩余的数**。由题目的限制及前缀最值的限制，所有 $2a_j>b_{i-1}$ 且不为 $b_{i-1}$ 的数均在 $b_i$ 后面。观察限制的形式，发现其不会成环，可将其看作**树拓扑序计数问题**。后缀和优化 DP 即可，时间复杂度 $O(n\log n)$。 **** ### [The Maximum Prefix](https://www.luogu.com.cn/problem/CF1810G) 给你一个长为 $n$ 的序列 $p_{1\sim n}$，由其生成一个长为 $n$ 的序列 $a_{1\sim n}$，其中 $a_i$ 有 $p_i$ 的概率为 $1$ 以及 $1-p_i$ 的概率为 $-1$。再给你一个长为 $n+1$ 的序列 $h_{0\sim n}$，定义一个序列的权值为 $h_v$，其中 $v$ 为该序列的最大前缀和。对 $\forall k\in[1,n]$ 求出 $a_{1\sim k}$ 的期望权值，对 $10^9+7$ 取模。 $n\le 5000$。 **** 朴素做法是设 $f_{i,j,k}$ 表示前缀 $i$，最大前缀和为 $j$，当前和为 $k$ 的概率。状态数为 $O(n^3)$，需要优化。尝试减少状态：能否在过程中只维护一个量求出前缀最大值？ **既然求的信息与前缀有关，那么不妨尝试改变插入方向，将向后插入改为向前插入**。设 $f_{i,j}$ 表示考虑了 $i$ 之后的位置，最大前缀和为 $j$ 的概率。 $$p_i\cdot f_{i,j}\to f_{i-1,j+1}$$ $$(1-p_i)\cdot f_{i,j}\to f_{i-1,\max(0,j-1)}$$ 答案为 $\sum_{j}f_{0,j}h_j$。这样就 $O(n^2)$ 求出了单个 $k$ 的答案。 **注意到我们要求的是每个前缀的答案，这与我们的转移方向相反。不妨设 $g_{i,j}$ 表示状态 $f_{i,j}$ 对答案的贡献系数，这也相当于将转移路径反向**。 $$g_{i,j}\gets p_i\cdot g_{i-1,j+1}$$ $$g_{i,j}\gets (1-p_i)\cdot g_{i-1,\max(0,j-1)}$$ 时间复杂度 $O(n^2)$。 **** ### [Range Argmax](https://www.luogu.com.cn/problem/AT_agc056_b) 给定整数 $n$ 以及 $m$ 个区间 $[l_i,r_i]$，求出可以通过如下方式生成的序列 $x_{1\sim m}$ 的个数。 - 取一个长为 $n$ 的排列 $p_{1\sim n}$。令 $x_i$ 为 $\argmax_{j=l_i}^{r_i} p_j$。 $n\le 300$，$m\le \frac{n(n - 1)}2$。 **** 答案不是 $n!$，因为多个 $p_{1\sim n}$ 会对应到相同的 $x_{1\sim m}$。此问题为**容易记重的判定型计数，一种思路为钦定单射**，将一种 $x_{1\sim m}$ 唯一对应至一 $p_{1\sim n}$。钦定方法通常要求选择最左的合法位置，于是可以从大至小考虑每个值 $v$，将 $v$ 放在能放置的最左侧的位置。这样问题就转化为求能生成多少种 $p_{1\sim n}$，且此时不会记重。假设 $p_k=n$，那么所有包含 $k$ 的区间 $[l_i,r_i]$ 都有 $x_i=k$。同时我们还需要限制 $1\sim k-1$ 都无法取到 $n$，那么考虑 $k'\in[1,k)$，只要存在一个区间 $l_i\le k'<k\le r_i$，那么 $x_i=k$ 便限制了 $p_{k'}<p_k$。**为了使 $[1,k)$ 所有位置都受限制，我们可以直接限制其中限制最严格的最大值**。 **寻找子问题与原问题的相似子结构**，可以设计出 $f_{l,r,k}$ 表示考虑所有 $[l_i,r_i]\sube [l,r]$ 的 $x_i$，$p_{l\sim r}$ 中最大值的位置一定要在 $[k,r]$ 中的方案数，有转移： $$f_{l,r,k}=f_{l,r,k+1}+f_{l,k-1,t_{l,r,k}}\cdot f_{k+1,r,k+1}$$ 其中 $t_{l,r,k}$ 表示 $\displaystyle\min_{l\le l_i\le k\le r_i\le r} l_i$，可以预处理。时间复杂度 $O(n^3+nm)$。 **** ### [Red and Blue Chips](https://www.luogu.com.cn/problem/AT_agc064_d) 给你 $n$ 个长为 $1$ 的字符串 $s_{1\sim n}$，字符集为 `R` 或 `B`，保证 $s_n$ 为 `B`。你需要对每个 $i=1,2,\cdots ,n-1$ 执行以下操作： - 选择一个整数 $j$ 使得 $i< j\le n$，且第 $j$ 个字符串的最后一个字符是 `B`，然后把 $s_i$ 整体拼接在 $s_j$ 的前面。问最后可以得到多少种 $s_n$，对 $998244353$ 取模。 $n\le 300$。 **** 答案无法直接计算，因为多种拼接方法会对应至同一个结果串。此问题为**难以判定的判定型计数，一种思路为转述条件**，原本的判定条件太过复杂而难以处理，寻找等价的问题与对应限制以便计数。注意到每个字符都在最终串里，题意所述拼接方式会使得一个字符多次移动，不利于设计状态。**由于字符 $i$ 的最终位置只依赖于 $\ge i$ 的字符，那么我们倒序处理，将字符 $i$ 直接插入 $>i$ 的字符的最终顺序中**，将 $s_i$ 插入到当前的某个 B 前即可，容易验证这种方法生成的最终串与原方法一致。此时仍难以判定，我们再换一种描述方式，当前串从左至右第 $i$ 个 B 前有 $x_i$ 个 R，那么插入一个 R 相当于将某个 $x_i$ 加一，而插入一个 B 相当与在某个非结尾的位置插入一个 $0$。记共有 $c$ 个字符 B，一组序列 $x_{1\sim c}$ 的合法条件就明确了：记 $p_i$ 表示初始串中第 $i$ 个 B 的位置，那么 $x_c$ 加 $x_{1\sim c-1}$ 中的前 $k-1$ 大之和需要不小于 $n-p_{c-k}-i$。设 $f_{i,j,k}$ 表示向序列 $x$ 中填入了所有 $\ge i$ 的数，已经填了 $j$ 个，和为 $k$ 的方案数，转移枚举序列中 $i$ 的数量 $t$ 即可。需要特殊处理 $x_c$，作为初始值。注意到有效状态与转移的 $i(j+t)\le n$，复杂度量级为 $\sum_{i,j,k,t}[i(j+t)\le n]=O(n^3)$。 **** ### [Card Guessing](https://www.luogu.com.cn/problem/CF1765C) 有四种花色的牌各 $n$ 张，将它们随机打乱。接下来你从牌堆中逐张地取出牌，取牌之前你将会猜这张牌的花色为「之前抽出的 $k$ 张牌中出现次数最少的花色」。如果有多种花色都是最少的，你将会随机地猜⼀种。如果之前抽出的牌不⾜ $k$ 张，就按之前的所有牌中的最少花色来猜。求你猜对的期望次数，对 $998244353$ 取模。 $n\le 5000$。 **** 由期望的线性性，我们肯定是拆到每个位置猜对的方案数进行计算，为此我们只需要考虑其之前 $\min(p-1,k)$ 个位置中每类牌的数量 $c_{1,2,3,4}$ 以及其中的最小值 $c_{\min}$。那么此时方案数乘猜对的概率即为： $$\binom{\sum c}{c_1,...,c_4}\cdot\binom{4n-\sum c}{n-c_1,...,n-c_4}\cdot\dfrac{n-c_{\min}}{4n-\sum c}$$ $$\dfrac{(\sum c)!}{\prod c_i!}\cdot\dfrac{(4n-\sum c-1)!}{\prod(n-c_i)!}\cdot{(n-c_{\min})}$$ 枚举 $c_{\min}$，逐个将 $c_{1\sim 4}$ 卷入当前答案，时间复杂度 $O(n^3)$。考虑有最小值的限制，不妨考虑以值域维度的某个方向作为转移方向。设 $f_{i,j,k}$ 表示已经填了所有 $c_p\ge j$，其中已经填了 $i$ 个 $c_p$，$\sum c$ 为 $k$ 时的贡献和。在第一次转移到 $i=4$ 的状态时乘入贡献即可。时间复杂度 $O(n^2)$。其中的思想为**通过改变 DP 顺序，使得目标限制和过程中某状态或最终状态吻合，减少一维枚举或状态。** **** ### [MEX counting](https://www.luogu.com.cn/problem/CF1608F) 给定整数 $n$ 和 $k$ 以及一个长度为 $n$ 的整数序列 $b_{1\sim n}$。求有多少个值域为 $[0,n]$ 的序列 $a$ 满足 $\forall i\in[1,n],|\text{mex}\{a_1,a_2,\dots,a_i\}-b_i| \le k$，对 $998244353$ 取模。 $n \le 2000$，$k \le 50$。 **** 题目的限制非常之强，以至于我们只能按照下标顺序从左至右生成解。注意 $\text{mex}$ 限制的复杂性，在于我们添加了一个等于当前 $\text{mex}$ 的数时会引发一系列的更新，这依赖于已决策部分中大于当前 $\text{mex}$ 的数的具体数值，向这方面考虑必然只能得到指数级做法。 **既然「已决策部分」信息难以记录，那么不妨「暂不决策」大于当前 $\text{mex}$ 的数**。设 $f_{i,j,k}$ 表示已经填到了 $a_i$，当前 $\text{mex}$ 为 $j$，$a_{1\sim i}$ 中大于 $j$ 的数有 $k$ 个的贡献。考虑其转移，最为复杂的一种转移即为 $a_i=j$ 时要考虑之前暂未决策的部分对状态的影响，需要枚举新的 $k'$，复杂度较高。注意到 $\text{mex}$ 只关注每种数是否存在，而完全不决策大于 $\text{mex}$ 的部分无法接受，那么**考虑「部分决策」大于当前 $\text{mex}$ 的数**，将这些数划分为若干个内部两两相等的等价类，并为这些等价类定下大小顺序。设 $f_{i,j,k}$ 表示已经填到了 $a_i$，当前 $\text{mex}$ 为 $j$，$a_{1\sim i}$ 中大于 $j$ 的数有 $k$ 种的贡献。$a_i=j$ 的转移会转移到一条斜线 $f_{i+1,j+c,k-c}(l\le c\le r)$ 上，使用前缀和优化即可。由于对于一个 $i$，合法的 $j$ 只有 $O(k)$ 种取值，时间复杂度 $O(n^2k)$。考虑本题状态的生成顺序：对于一个状态，我们将 $(i,a_i)$ 画在坐标系上，按照下标顺序确定 $a_i$ 相当于确定一个向左的半平面内的点；按值域确定则是确定一个向下的半平面；而本题中的转移顺序则为确定一个左下矩形，而其中矩形的上方部分既不能先决策，也不能完全不决策。 **** ### [Bus Analysis](https://vjudge.net.cn/contest/654718#problem/C) 数轴上有 $n$ 个点 $p_{1\dots n}$，有两种线段，第一种长为 $20$，费用为 $1$，第二种长为 $75$，费用为 $3$。定义一个点集的权值为使用这两种线段覆盖点集内所有点的最小费用，求出这 $n$ 个点的所有子集的权值之和。 $n\le 1000$。 **** **考虑到数子集不好确定前驱与后继，尝试将覆盖的长度写入状态以便判断是否可覆盖**，设 $f_{i,j}$ 表示考虑完前 $i$ 个，还能向后覆盖 $j$ 的最小费用。难以统计与去重，尝试**交换值域与定义域**，设 $f_{i,j}$ 表示考虑完前 $i$ 个，费用为 $j$，还能向后覆盖的最大距离，$g_i$ 表示最小费用。令 $x=g_i$，则在覆盖前 $i$ 个的过程中花费 $\ge x+3$ 的代价一定不优，所以我们只需要考虑 $f_{i,x\sim x+2}$ 这几个位置的值即可。 **对最优化 DP 做计数为经典的 DP of DP**。设 $f_{i,x,a,b,c}$ 表示考虑完前 $i$ 个，有多少子集满足最小代价为 $x$，上述 $f_{i,x\sim x+2}$ 分别为 $a,b,c$。令 $d=p_{i+1}-p_i$，转移有： - 当子集不包含该点时，$f_{i,x,a,b,c}\to f_{i+1,x,\max(a-d,0),\max(b-d,0),\max(c-d,0)}$。 - 当子集包含该点时， - 若 $a<d$，则 $f_{i,x,a,b,c}\to f_{i+1,x+1,\max(b-d,20),\max(c-d,20),75}$。 - 若 $a\ge d$，则 $f_{i,x,a,b,c}\to f_{i+1,x,a-d,b-d,c-d}$。最终答案为 $x\sum_{a,b,c}f_{n,x,a,b,c}$，则可在转移过程中 $x$ 增加时计入答案，将 $x$ 一维省去。令 $v=75$，则复杂度为 $O(nv^3)$。 **** ### [Avoid Permutations](https://www.luogu.com.cn/problem/AT_arc118_e) 对于一个长为 $n$ 的排列 $p_{1\sim n}$，定义其权值为在网格图上从 $(0,0)$ 走到 $(n+1,n+1)$ 且不经过任意 $(i,p_i)$ 的方案数。给你一个残缺的排列 $p$，求其每种补全方案的权值之和。 $n\le 500$。 **** 首先将不经过任意点的限制容斥掉。钦定过 $k$ 个点 $(i,p_i)$，容斥系数为 $(-1)^k$。我们只关心钦定经过的点的 $p$，其余未填位置贡献一个阶乘的系数即可。那么设 $f_{i,j,c}$ 表示钦定经过 $(i,p_i=j)$，有 $c$ 个 $-1$ 位置未考虑的方案数。转移下一个钦定经过的点，时间复杂度 $O(n^5)$。 **转换视角，将对钦定序列 DP 转为对路径本身 DP，将断点转移替换为单步转移**。对路径本身 DP，到达一个点时决策其是否成为钦定经过的关键点，注意一行或一列内不能有超过一个关键点，那么设 $f_{i,j,c,0/1,0/1}$ 表示当前走到点 $(i,j)$，钦定了 $c$ 个可动关键点，第 $i$ 列、第 $j$ 行内是否有关键点，时间复杂度 $O(n^3)$。 **** ### [[ZJOI2022] 树](https://www.luogu.com.cn/problem/P8329) 有两棵有根树 $T_1,T_2$，其中第一棵树中父亲的编号小于儿子的编号，第二棵树中父亲的编号大于儿子的编号。给你一个整数 $n$，对 $\forall i\in[2,n]$ 求出，有多少 $i$ 个结点的 $T_1,T_2$ 满足对于任意结点 $p$，其恰好在其中一棵树上为叶子结点。 $n\le 500$。 **** 按照编号顺序依次决定每个点在哪颗树上为叶子。那么第一棵树的生成顺序为不断加叶子，第二棵树的为不断合并子树，将需要的信息设入状态。设 $f_{i,j,k,l}$ 表示考虑了前 $i$ 个点，$T_1$ 上有 $j$ 个钦定为非叶子，其中还有 $k$ 个没有儿子，$T_2$ 形成 $l$ 个子树。转移即为： - 钦定在 $T_1$ 中为叶子，父亲已经有儿子，$f_{i-1,j,k,l}\cdot (j-k)\cdot \binom{l}{a}\to f_{i,j,k,l-a}(0\le a< l)$； - 钦定在 $T_1$ 中为叶子，父亲没有儿子，$f_{i-1,j,k,l}\cdot k \cdot \binom{l}{a}\to f_{i,j,k-1,l-a}(0\le a< l)$； - 钦定在 $T_1$ 中为非叶子，父亲已经有儿子，$f_{i-1,j,k,l}\cdot (j-k)\to f_{i,j+1,k+1,l+1}$； - 钦定在 $T_1$ 中为非叶子，父亲没有儿子，$f_{i-1,j,k,l}\cdot k\to f_{i,j+1,k,l+1}$；四维状态加一维卷积转移，时间复杂度 $O(n^5)$。对于第一棵树，要求为每个非叶子结点均有儿子，那么我们用一维状态表示还有多少非叶子结点还需要儿子，**当一个非叶子结点增加一个儿子时决策其是否结束增加儿子**，状态数减少一维。对于第二棵树，转移时选取儿子将不可避免地乘上组合数，难以优化。**不妨在形成子树时就决策其与哪些子树拥有相同的父亲**，这样转移时只需选取一类即可，转移减少一维。新状态设 $f_{i,j,k}$ 表示考虑了前 $i$ 个点，$T_1$ 还有 $j$ 个结点需要儿子，$T_2$ 已经形成 $k$ 个子树等价类。转移即为： - 钦定在 $T_1$ 中为叶子，$f_{i-1,j,k}\cdot j\cdot k(k-1)\to f_{i,j-op,k-1}$，$f_{i-1,j,k}\cdot j\cdot k\to f_{i,j-op,k}$； - 钦定在 $T_1$ 中为非叶子，$f_{i-1,j,k}\cdot j\to f_{i,j+1-op,k+1}$，$f_{i-1,j,k}\cdot j\cdot k\to f_{i,j+1-op,k}$；时间复杂度 $O(n^3)$，可以通过。 **** ### [Again Counting Arrays](https://www.luogu.com.cn/problem/CF1967E1) 给定三个整数 $n,m,b_0$，定义一个长为 $n$ 的序列 $b_{1\sim n}$ 是好的当且仅当 $\forall i\in[1,n],|b_i-b_{i-1}|=1,b_i\ne a_i$。求有多少值域在 $[1,m]$ 中的序列 $a_{1\sim n}$ 使得存在一个合法的 $b_{1\sim n}$。多组数据。 $n,m\le 2\times 10^5$，$\sum n\le 2\times 10^5$。 **** 判定型计数，考虑钦定单射，将 $a$ 序列对应至最优的合法 $b$ 序列。生成方式为当 $a_i\ne b_{i-1}+1$ 时令 $b_i=b_{i-1}+1$，否则令 $b_i=b_{i-1}-1$，不合法情况只有 $b_{i-1}=0$ 且 $a_i=1$。这种方式最有可能合法是因为若有一次 $a_i\ne b_{i-1}+1$ 且 $b_i'=b_{i-1}-1$，那么此后均有 $b_i'\le b_i$，即 $b_i=0\mapsto b_i'=0$。对一个 $b$ 序列计算对应至其的 $a$ 数列数量，那么每一次 $b_i=b_{i-1}+1$ 时 $a_i$ 均有 $m-1$ 种选择。注意当第一次 $b_i=m$ 之后需要特殊处理，方案数为 $(m-1)m^{n-i}$。令 $f_{i,j}$ 表示 $b_i=j$ 的贡献和，那么我们需要计算所有 $f_{i,m-1}$ 以及 $f_{n,j}$。直接暴力转移时间复杂度 $O(nm)$。旋转坐标系，转化为**格路计数**问题，向右走一步带有 $m-1$ 的系数，不允许跨过直线 $y=x$ 和 $y=x+m-1$。系数贡献在外计算，反射容斥求路径数量。时间复杂度 $O(n^2/m)$。平衡一下，时间复杂度 $O(n\sqrt n)$。 **** ### [阴阳阵](https://www.luogu.com.cn/problem/P9385) 有一个共有 $n+m$ 个结点的内向基环树森林，其中前 $n$ 个点为白点，后 $m$ 个点为黑点。其为好的当且仅当： - 所有黑点均指向白点。 - 所有环上黑点数量与白点数量的乘积均为偶数。求有多少满足题意的好的内向基环树森林。 $n,m\le 2000$。 **** **钦定图的生成顺序。每次从编号最小的还未出现出边的点开始不断钦定出边直到到达已经钦定完毕的点**。称其为一轮拓展。一轮拓展可能有两种形式： - 最终到达的点为已经确定的点，向图中加入了一条链。 - 最终到达的点为本轮拓展的点，向图中加入了一个 $ρ$ 型。同时我们需要钦定编号，**为了避免卷积，状态中不可区分已拓展点与本轮拓展点**。第一类拓展在结束时需要已拓展点的数量，这需要我们**在开启本轮拓展时就钦定本轮拓展终点颜色与终点指向的结点**。第二类拓展需要记录环上的颜色奇偶性以及进入环的点的颜色，我们**在拓展的过程中钦定一个点作为环的起点**即可。需要为两类拓展分别设计一个状态： - $f_{i,j}$ 表示已经确定了 $i$ 个白点 $j$ 个黑点的出边的方案数； - $g_{i,j,0/1,0/1}$ 表示已经确定了 $i$ 个白点 $j$ 个黑点的出边，正在进行第一类拓展，当前结点的颜色为白/黑，终止结点颜色钦定为白/黑的贡献和； - $h_{i,j,0/1/2,0/1,0/1,0/1}$ 表示已经确定了 $i$ 个白点 $j$ 个黑点的出边，正在进行第二类拓展，环起点的颜色为白/黑/未钦定起点，当前结点的颜色为白/黑，环上白/黑点数奇偶性。在三个状态之间互相转移。时间复杂度 $O(nm)$。 **** ### [[2024 联考 I Day7] 连通](http://192.168.102.138/JudgeOnline/problem.php?cid=2142&pid=1) 给定一棵 $n$ 个点的树，第 $i$ 个结点有权值 $a_i$。一个非空连通块合法当且仅当： - 连通块内点权值的最大公约数等于 $1$； - 连通块内点权值的最小公倍数等于 $y$。求合法非空连通块个数。 $n\leq 10^3$，$y\leq 10^{18}$，$a_i\mid y$，$\mu(y)\neq 0$ 且 $y$ 不存在大于 $50$ 的质因子。 **** 在题目的限制下每个结点的权值可看为一个集合，连通块合法需要其中权值的并集为全集且交集为空集。朴素容斥做法为枚举两个不交子集 $s,t$，要求所有选择的点均包含 $s$ 且与 $t$ 无交，容斥系数为 $(-1)^{|s|+|t|}$，时间复杂度 $O(3^{\omega(y)}n)$。 **考虑枚举 $s\cup t$，再将贡献乘上将其划分为 $s,t$ 的方案数**。当连通块内 $s\cup t$ 这些位均相同时有恰好一种划分方式，否则没有。直接 DP 即可，时间复杂度 $O(2^{\omega(y)}n)$。 **** ### [[2024 联考 IV Day7] 不连续子串 / subseq](http://192.168.102.138/JudgeOnline/problem.php?cid=2199&pid=2) 给你一个长为 $n$ 的序列 $a_{1\dots n}$，你需要求出其所有本质不同非空子序列的本质不同非空子序列数量之和。 $n\le 8000$。 **** 判定型计数问题，我们不妨**对每一种可能的子序列对钦定一个出现位置进行统计**。设外层、内层子序列分别为 $S=\{p_{1},p_2,\dots ,p_{l_1}\},T=\{q_{1},q_2,\dots ,q_{l_2}\}$。原先一层的情况下，我们可以要求 $\forall j\in(p_{i-1},p_{i}),a_j\ne a_{p_i}$，即钦定一种子序列在最左的出现位置处统计到。那么两层的情况下，我们考虑对内层进行 DP，设 $f_i$ 表示考虑到 $i$ 且钦定 $i$ 在 $T$ 内的答案，那么枚举 $T$ 中上一个位置 $j$，考虑 $(j,i)$ 中的数填入 $S$ 的方案数，有如下限制： - 对于 $j<p<i,a_p=a_i$，要求 $p$ 不能在 $S$ 中。 - 令 $l$ 为最大的 $j<l<i$ 使得 $a_l=a_i$，必须存在 $l<q<i$ 使得 $q$ 在 $S$ 中。 - 对 $S$ 中每相邻两个数 $p,q$，要求 $\forall k\in(p,q),a_k\ne a_q$。其中第一条限制是为了限制 $T$ 为 $S$ 中最左的，后两条限制是为了限制 $S$ 为最左的。时间复杂度 $O(n^2)$。 **** ### [青鱼和区间](https://pjudge.ac/contest/1114/problem/21741) 给定一个整数 $n$，你需要选出若干 $[1,n]$ 的不同子区间 $[l_1,r_1],[l_2,r_2],\dots ,[l_k,r_k]$。现有一个未知的整数 $x\in[1,n]$，你将会对于 $\forall i\in[1,k]$ 得知 $x$ 是否在 $[l_i,r_i]$ 中。求出有多少种选择区间的方案使得可以根据得到的信息确定出唯一的 $x$。 $n\le 300$。 **** 令 $S_p$ 为所有包含 $p$ 的区间编号的集合，那么能唯一确定 $x$ 就等价于 $S_p$ 的所有等价类大小均为 $1$。一个性质是不会存在两个等价类 $X,Y$ 使得存在 $i<a<j<b$ 且 $i,j\in X$，$a,b\in Y$，但仍难以寻找相似子结构。考虑以下过程： - 维护一个指针 $p$，初始 $p=1$。 - 重复： - 若 $p=n+1$，则停止重复。 - 令 $q$ 为 $p$ 所在等价类中最大的下标，令 $p\gets q+1$。那么我们实际上将 $[1,n]$ 划分为了若干段 $[p_1,q_1],[p_2,q_2],\dots,[p_k,q_k]$，满足 $p_i,q_i$ 分别为其对应等价类中下标的最小值与最大值。那么所有选取的区间 $[l,r]$ 要么是某个 $(p_i,q_i)$ 的子区间，要么是一段连续的段 $[p_i,q_j]$，并且此类区间要将这 $k$ 段划分到不同的等价类——相似子结构找到了！令 $f_i$ 表示答案，$g_{i,j}$ 表示将 $i$ 个位置划分为 $j$ 段的段内方案数乘积之和，可以容斥得到转移方程： $$g_{i,j}=\sum_{k=1}^i2^{(k-2)(k-1)/2}g_{i-k,j-1}$$ $$f_i=2^{i(i+1)/2}-\sum_{k=1}^{i-1}f_kg_{i,k}$$ 直接转移即可，时间复杂度 $O(n^3)$。 **本题的推导过程中，若关注了所有等价类的下标区间则难以求出区间选择方案数，但若只关注最外一层的等价类区间，那么就可以将内外分离来看，找到相似子结构了。** **** ### [重返现世](https://www.luogu.com.cn/problem/P4707) 给你一个长为 $n$ 的序列 $p_{1\sim n}$ 以及一个常数 $k$。有 $n$ 类物品，每一次以 $p_i$ 为权随机一个物品，当随出 $k$ 种不同的物品时停止，求随机的期望次数。 $n\le 1000$，$k\ge n-10$，$\sum p\le 10^4$。 **** 令 $m=\sum p$，$k\gets n-k+1$。根据拓展 $\min-\max$ 容斥，我们有： $$\text{kthmax}(S)=\sum_{T\sube S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)$$ 其中 $\min(T)$ 表示随出任意 $T$ 中物品的期望次数，显然其等于 $\dfrac{m}{\sum_{i\in T}p_i}$。设 $f_{i,j,l}$ 表示考虑到 $i$，$\sum p$ 为 $j$，$|T|$ 为 $l$ 时的方案数。状态复杂度太高，考虑优化，将最后一维纳入贡献中。由于有 $\binom{x}{k}=\binom{x-1}{k-1}+\binom{x-1}{k}$，我们将状态改写为 $f_{i,j,t}$ 表示考虑到 $i$，$\sum p$ 为 $j$ 时 $(-1)^{|T|}\binom{|T|-1}{t}$ 之和，可以转移。时间复杂度 $O(nmk)$。 **** ### [排列游戏](https://www.luogu.com.cn/problem/P10547) 给定整数 $n,m$，对满足下列条件的长为 $n$ 的排列 $p_{1\sim n}$ 计数： - 可以通过恰好操作 $n$ 次「选择 $1\le i<j\le n$，交换 $p_i,p_j$」操作使得 $p_i=i$。 - 可以操作若干次「选择 $1\le i<j\le n$，花费 $|i-j|$ 的代价交换 $p_i,p_j$」，在代价不超过 $m$ 的条件下使得 $p_i=i$。多组询问。 $T\le 1000$，$n\le 500$，$m\le 5\times 10^3$。 **** 先看第一个条件，由于每操作一次均会使得排列奇偶性改变，于是其等价于要求 $p_{1\sim n}$ 为偶排列。再看第二个条件，由经典结论，最小归位代价为 $\frac{1}{2}\sum|i-p_i|$，即要求 $\sum|i-p_i|\le 2m$。考虑 $\sum|i-p_i|$ 的形式，很容易让我们联想到**排列的连续段 DP**。但连续段 DP 通常用于解决 $\sum f(p_i,p_{i+1})$ 的问题，这是因为我们维护了已经填入排列中的位置，于是所有需要计算的 $f(p_i,p_{i+1})$ 均可被计入。而现在我们需要解决 $\sum f(i,p_i)$ 的问题，我们不妨对 $i\to p_i$ 形成的链做连续段 DP。设 $f_{i,j,k,0/1}$ 表示已经考虑了 $i$ 个点，目前形成 $j$ 条链，当前贡献和为 $k$，已经形成了偶数/奇数个环。由于此处贡献函数为绝对值，所以 $k$ 的范围为 $[-n^2,n^2]$，时间复杂度 $O(n^4)$。为了避免负值扩大定义域，我们将 $\sum|i-p_i|$ 看为对 $\forall v\in[1,n]$ 求有多少对 $i\to p_i$ 经过 $v$，那么在 $i$ 转移至 $i+1$ 时将 $k$ 加上 $2j$ 即可，时间复杂度 $O(n^2m)$。注意到转移一步 $j$ 至多加一，而每一步转移均会将 $j$ 计入 $k$ 中，所以只有前 $O(\sqrt m)$ 个 $j$ 是有用的，时间复杂度 $O(nm^{3/2})$，可以通过。还有另一个角度来理解这个 DP：记录左下角正方形 $1\le x,p_x\le i$ 的点数。 **** ### [Resurrection](https://www.luogu.com.cn/problem/P6383) 给你一棵 $n$ 个结点的大根树 $T$，边有编号。按照如下步骤生成一张包含 $n$ 个节点的无向图 $G$： - 选取一个 $1 \sim n-1$ 的排列 $p_{1\sim n-1}$。 - 依次进行 $n-1$ 次操作。 - 进行第 $i$ 次操作时，首先删除树 $T$ 中编号为 $p_i$ 的边 $(a,b)$，然后，记 $u$ 和 $v$ 分别为当前树 $T$ 中与 $a,b$ 连通的所有点中，编号最大的点，并在图 $G$ 的 $u$ 号点和 $v$ 号点之间连一条边。求对于给定的树 $T$，按上述方式一共可以生成多少种本质不同的图 $G$，对 $998244353$ 取模的值。 $n\le 3000$。 **** 有几个较为显然的性质。 - $G$ 中无环即 $G$ 也为树。 - 由于给出的树为大根树，一个连通块内的编号最大点即为其中深度最小的点。那么倒序加边，加入一条边时会在 $G$ 中将一个结点 $u$ 与其在 $T$ 中的某个祖先连边。考虑判定 $G$ 是否合法，一条 $G$ 中的边限制了一些 $T$ 中的边的加入的先后顺序，将限制描述为边，即要求不出现环。换成等价的描述形式为每个点 $u$ 与其某个祖先连边，且要求不存在四个同一条链上深度递减的点 $a,b,c,d$ 使得在 $G$ 中 $(a,c),(b,d)$ 间均有边。考虑树形 DP。经过尝试，在转移到一点 $x$ 时确定 $x$ 在 $G$ 上的儿子这条路行不通，那么就需要考虑转移到一点 $x$ 时确定 $x$ 在 $G$ 上的父亲。困难为 $x$ 可以连向的祖先个数与其祖先的连边方案相关，但我们只能自底向上求答案，解决方案为**将转移路径反向，对于每种可连边祖先数量均求出子树内的连边方案**。设 $f_{x,i}$ 表示**假如有 $\bm i$ 个祖先可以连边**，$x$ 子树的答案。转移考虑枚举 $x$ 连向的祖先，设其为可连边祖先的自底向上第 $j$ 个，那么其子树不能向前 $j-1$ 个连边；另外子树中也可向 $x$ 连边，于是转移为： $$f_{x,i}=\sum_{j=1}^i\prod_{t}f_{t,i-j+2}$$ 前缀和优化即可，时间复杂度 $O(n^2)$。 **** ### [Counting Haybales P](https://www.luogu.com.cn/problem/P8100) 给你一个长为 $n$ 的序列 $a_{1\sim n}$，你可以执行任意次如下操作： - 选择一个位置 $i$ 满足 $1\le i<n$ 且 $|a_i-a_{i+1}|=1$，交换 $a_i,a_{i+1}$。求可以得到多少种不同的序列，对 $10^9+7$ 取模。多组数据。 $\sum n\le 5000$。 **** 相差 $\ge 2$ 的两个数不可能交换相对位置，不妨钦定相等的两个数也不能交换位置。那么 $\forall 1\le i<j\le n$，如果 $|a_i-a_j|\ne 1$ 连边 $i\to j$，答案即为此图的拓扑序数量。考虑连边限制非常松，观察性质。相差恰好为一的一个性质为奇偶性不同，即**相同奇偶性的两个数一定连边**。不妨将所有奇数和所有偶数分开，形成两条链与若干两条链之间的附加边，设 $f_{i,j}$ 表示两条链已经分别加入了 $i,j$ 个点的方案数即可转移。时间复杂度 $O(n^2)$。 **** ### [Equal Sums](https://qoj.ac/contest/1522/problem/8049) 给出两个整数 $n$ 以及四个长为 $n$ 的序列 $l_{1\sim n}^{(x)},r_{1\sim n}^{(x)},l_{1\sim n}^{(y)},r_{1\sim n}^{(y)}$，对于 $\forall p,q\in[1,n]$，求有多少对长为 $n$ 的正整数序列 $a_{1\sim p},b_{1\sim q}$ 满足： - $l_i^{(x)}\le a_i\le r_i^{(x)}$； - $l_i^{(y)}\le b_i\le r_i^{(y)}$； - $\sum a_i=\sum b_i$。对 $10^9+7$ 取模。 $n,v\le 500$。 **** 对序列 $a,b$ 分开做复杂度过高，必须合并考虑。 **注意到限制无关顺序，考虑一个优秀的生成顺序**。设 $f_{i,j,v}$ 表示考虑了 $a_{1\sim i},b_{1\sim j}$，此时 $\sum a-\sum b$ 的值为 $v$ 的方案数。我们钦定当 $v\le 0$ 时确定 $a_{i+1}$，否则确定 $b_{j+1}$，这样我们就将第三维的范围限制为 $O(v)$。容易发现，每对合法的序列对应至恰好一种生成顺序，算法正确。使用前缀和优化，时间复杂度 $O(n^2v)$。 **** ### [[2023 NOI模拟 Day24] 数环](http://192.168.102.138/JudgeOnline/problem.php?cid=1986&pid=0) 有一张左右部均有 $n$ 个点的二分图，左侧第 $i$ 个点与右侧的第 $1\sim a_i$ 个点之间有连边，问该图有多少个不同的简单环，对 $998244353$ 取模。 $n\le 5000$。 **** 考虑如果确定了环上的左部点以及其顺序，其选择右部点的方案数。那么相邻两个左部点 $p_i,p_{i+1}$ 之间选择的右部点编号要不大于 $\min(a_{p_i},a_{p_{i+1}})$，这个形式让我们想起连续段 DP。将 $a_i$ 升序排序，设 $f_{i,j,k}$ 表示考虑到左部点 $i$，目前选出了 $j$ 条有向链，选择了 $k$ 个左部点的方案数。其中一条有向链包含若干左部点、其中间及两端的右部点，新加一左部点时需要此时已经选择的右部点数量 $j+k$。时间复杂度 $O(n^3)$，无法通过。当前考察的为环上的左部点，难以优化，不妨**转换视角，考察环上的右部点**。设 $f_{i,j}$ 为考虑到右部点 $a_i$ 以及左部点 $i$，目前选出了 $j$ 条有向链的方案数。由 $i-1$ 转移到 $i$ 时先枚举右部点 $(a_{i-1},a_i]$ 中选择了多少个，再考虑点 $i$ 是否选择，若选择则需要选择当前的两条链合并。时间复杂度 $O(n^2)$。值得注意的是，我们没有做出任何转化，仅仅是转换视角、将右部点的决策提前便降低了复杂度。 **** ### [All Pairs Similarity P](https://www.luogu.com.cn/problem/P11458) 给定 $n,k$ 以及 $n$ 个整数 $a_{1\sim n}$，保证 $a_i\in(0,2^k)$。定义两个整数 $x,y$ 的相似度为它们的按位与的结果中 $1$ 的数量除以它们的按位或的结果中 $1$ 的数量。对于 $\forall i\in[1,n]$，对于 $\forall j\in[1,n]$ 求出 $a_i$ 与 $a_j$ 的相似度之和，对 $10^9+7$ 取模。 $n\le 5\times 10^5$，$k\le 20$。 **** 所求为 $\displaystyle\sum_j\dfrac{|a_i\cap a_j|}{|a_i\cup a_j|}$，简单容斥得到 $\displaystyle\sum_j\dfrac{|a_i|+|a_j|}{|a_i\cup a_j|}-n$，考虑如何求 $f_s$ 表示 $\displaystyle\sum_j\dfrac{1}{|s\cup a_j|}$。集合的包含、并集等条件引出一类做法，考虑设计一辅助状态 $g_s$ 满足： $$f_s=\sum_{T⊇S} g_t$$ 仅考虑一个数 $a_p$，我们希望构造出 $g_t$ 满足其高维后缀和为 $f_s=\dfrac{1}{|s\cup a_p|}$。考虑一个关于集合大小的贡献系数 $w_i$，满足 $$\dfrac{1}{i}=\sum_{j=i}^k\binom{k-i}{j-i}w_j$$ 二项式反演可以轻松计算出 $w_{1\sim k}$。我们构造 $g_t=[a_p\sube T]w_{|t|}$，那么容易验证，对于一个 $S$，所有同时是 $S$ 和 $a_p$ 的超集的集合 $T$ 都会作出 $w_{|t|}$ 的贡献，它们的和正好是 $\dfrac{1}{|s\cup a_p|}$。时间复杂度 $O(2^kk+n)$。 **** ### [[2025 省选模拟 Day8] 神明的迷思](http://192.168.102.138/JudgeOnline/problem.php?cid=2223&pid=1) 给你一个长为 $n$ 的操作序列 $s_{1\sim n}$ 和一个长为 $m$ 的数轴，操作有 `LR` 两种，若现在的位置为 $p$，则： - 若当前操作为 `L`， - 如果 $p=1$，忽略本次操作； - 否则，令 $p\gets p-1$。 - 若当前操作为 `R`， - 如果 $p=m$，返回操作故障； - 否则，令 $p\gets p+1$。给出的 $s_{1\sim n}$ 中有 `LR?` 三种字符，你需要将 $s_{1\sim n}$ 中 `?` 替换为 `LR`。对于每个 $k\in[1,m]$，求出若初始处于位置 $k$，有多少种替换方式使得周期执行操作 $s_{1\sim n}$ 充分多次之后仍然不会返回操作故障。对 $10^9+7$ 取模。 $n,m\le 500$。 **** 如果一个方案在 $k$ 处合法，那么其在 $k-1$ 处也同样合法。故我们不妨枚举 $k$，考虑求出最大合法位置为 $k$ 的方案数量。类似判定型计数，我们需要限制其在 $k+1$ 处不合法，即在第一次忽略 `L` 操作之前存在一个 $p=m$ 的时刻，设 $f_{i,j,0/1}$ 表示执行到第 $i$ 次操作，当前位置为 $j$，是否到达过位置 $m$ 即可。时间复杂度 $O(nm^2)$。 **** ### [Graph](https://www.luogu.com.cn/problem/P11802) 给你一个长为 $n$ 的残缺排列 $p_{1\sim n}$ 以及一个常数 $c$，定义 $p^{(k)}_i=p_{p^{(k-1)}_i}$，你需要求出有多少种将排列 $p_{1\sim n}$ 补全为 $p'_{1\sim n}$ 的方案使得： - 存在一个排列 $q_{1\sim n}$ 满足 $q^{(c)}_i=p_i$。 - 分别连边 $i\to p_i(p_i\ne -1)$ 与 $i\to p_i'$ 形成两张图，在图一中不连通的两个非孤立点不能在图二中连通。 $n\le 1000$。 **** 题意其实是相当于给了若干条链，要求将他们拼成环且不能合并两条长度大于一的链。考虑第一个条件，$q_{1\sim n}$ 中一个长为 $l$ 的环会裂成 $\gcd(l,c)$ 个等长的环。那么 $p_{1\sim n}$ 中 $k$ 个长为 $l$ 的环能拼起来当且仅当 $\gcd(lk,c)=k$。不难发现，若令 $k_l$ 为最小的满足条件的数，那么要求最终长为 $l$ 的环的数量为 $k_l$ 的倍数。接下来考虑 DP。**为了低于指数级**，我们不能考察环由哪一条链构成，只能按照长度考虑由链构成环。设 $f_{i,j,k}$ 表示考虑了所有环长不超过 $i$ 的环，现有 $j$ 条长为 $i$ 的链，已经使用了 $k$ 个孤立点的方案数。转移时需要枚举 $c,t$ 分别表示使用 $c\times i$ 个孤立点形成 $i$ 个环、将 $t$ 条长为 $i$ 的链首尾相连形成环，分别需要乘上一些系数进行卷积，且要求 $r_i+c+t\equiv 0\pmod{k_i}$，其中 $r_i$ 为长为 $i$ 的环数。注意到 $j,c,t\le n/i$，时间复杂度为 $n\sum (n/i)^3=O(n^4)$，无法通过。 **两维卷积引导我们做分步卷积**，但是有一条额外的同余条件做阻碍。不妨枚举 $c\bmod k_i$，此时同样确定了 $t\bmod k_i$，只对满足余数要求的 $c,t$ 分别做卷积，最终将每个余数的答案加起来即可。任何一对 $(j,k,c),(j,k,t)$ 分别只进行一次卷积，时间复杂度为 $n\sum(n/i)^2=O(n^3)$，可以通过。 **** ### [[LNOI2022] 盒](https://www.luogu.com.cn/problem/P8367) 有 $n$ 个盒子排成一排，在初始状态下，第 $i$ 个盒子放有 $a_i$ 个货物，总货物数量为 $m= \sum_{i = 1}^{n} a_i$。对于所有非负整数序列 $b_{1\sim n}$ 满足 $\sum_{i = 1}^{n} b_i = m$，求以下问题的答案之和： - 你可以做如下操作若干次：花费 $w_i$ 的代价将一个货物在盒子 $i$ 与 $i+1$ 之间移动。求出使得第 $i$ 个盒子中需要拥有恰好 $b_i$ 个货物的最小代价。答案对 $998244353$ 取模。多组数据。 $T\le 5$，$n\le 5\times 10^5$，$m\le 2\times 10^6$。 **** 将贡献拆到每个间隔，令 $A_i$ 为 $a_i$ 的前缀和数组，答案即为 $$\sum_{i=1}^{n-1}w_i\sum_{s=0}^m|s-A_i|\cdot \binom{s+i-1}{i-1}\cdot \binom{m-s+n-i-1}{n-i-1}$$ 拆开绝对值，需要求解以下子问题： $$f(n,m,i,k)=\sum_{s=0}^k\binom{s+i-1}{s}\binom{m-s+n-i-1}{m-s}$$ $$g(n,m,i,k)=\sum_{s=0}^ks\binom{s+i-1}{s}\binom{m-s+n-i-1}{m-s}$$ 通过 $s\binom{s+i-1}{s}=i\binom{s+i-1}{i}$ 可得到 $g(n,m,i,k)=i\cdot f(n+1,m-1,i+1,k-1)$，故我们只需要解决 $f(n,m,i,k)$ 的部分。注意到 $i,A_i$ 是分别递增的，且由 $f(n,m,i,k)$ 递推至 $f(n,m,i,k+1)$ 是简单的，不妨考虑**递推求解 $\bm n$ 处点值**，难点为如何由 $f(n,m,i,k)$ 递推至 $f(n,m,i+1,k)$。 **考察 $\bm{f(n,m,i,k)}$ 的定义式的组合意义**，不难想到用格路计数代表组合数，原式组合意义即为枚举一个位置 $0\le p\le k$，求出 $(0,0)\to(i-1,p)\to(i,p)\to(n-1,m)$ 的方案数之和。不难发现。将 $i$ 增加 $1$，只有原先经过 $(i,k)\to(i,k+1)$ 的路径将不再满足条件。时间复杂度 $O(T(n+m))$。 **** ### [[GDKOI2023] 错排](https://www.luogu.com.cn/problem/P10103) 有 $q$ 组询问，每组询问给出两个整数 $n,m$，求有多少长为 $n$ 的排列 $p_{1\sim n}$ 使得： - $\forall i\in[1,m]$，$p_i>m$； - $\forall i\in[1,n]$，$p_i\ne i$。 $n,m,q\le 2\times 10^5$，$m\le n$。 **** 先考虑从 $(m,n]$ 中取出 $m$ 个数填入前半部分，记 $f(n,m)$ 表示计数有多少长为 $n+m$ 的排列，其中有 $m$ 个位置需要满足错排限制，另外 $n$ 个不需要满足。则有原问题的答案为 $\dfrac{(n-m)!}{(n-2m)!}f(m,n-2m)$，这是因为被选中的那 $m$ 个数对应的位置不可能不满足错排限制。不妨**考虑递推求解 $\bm{f(n,m)}$**。按照传统错排问题的思路，考虑数 $n$ 填入的位置，分类讨论 $n$ 是否被限制： - 若 $n$ 不被限制，则： - 可以将 $n$ 直接填入 $p_n$：方案数为 $f(n-1,m)$； - 否则 $n$ 不填入 $p_n$，即增加了对 $n$ 的限制：方案数为 $f(n-1,m+1)$； - 若 $n$ 被限制，则： - 将 $n$ 填入一个受限位置 $p_k$： - 若 $k$ 填入了 $p_n$：方案数为 $mf(n-1,m-1)$； - 否则 $k$ 不填入 $p_n$，可看作限制的传递：方案数为 $mf(n-1,m)$； - 将 $n$ 填入一个不受限位置 $p_k$，可看作限制的传递：方案数为 $nf(n-1,m)$；故我们得到了两条递推式： $$f(n,m)=f(n-1,m)+f(n-1,m+1)$$ $$f(n,m)=(n+m)f(n-1,m)+mf(n-1,m-1)$$ 将它们整合之后还可得到： $$f(n,m)=(n+m-1)f(n,m-1)+(m-1)f(n,m-2)$$ 于是我们可以维护 $(n,m,f(n,m),f(n,m+1))$ 四元组，可通过上述三条式子实现 $O(1)$ 将 $n,m$ 增减一。 **使用莫队算法解决 $\bm q$ 组询问**，时间复杂度 $O(n\sqrt q)$。 **** ### [[2025 NOI模拟 Day9] 旋舞](http://192.168.102.138/JudgeOnline/problem.php?cid=2241&pid=1) 有一个左右分别 $n$ 个点的二分图，其中左部点 $i$ 与右部点 $j$ 之间有边的概率为 $p_{i,j}$。求出该二分图有完美匹配的概率，对 $10^9+7$ 取模。 $n\le 9$。 **** 考虑 Hall 定理，对于任意左部点集合 $S$，若存在 $|S|>|N(S)|$ 则不合法。**对于一个不合法的方案，我们选取一个代表元 $\bm S$ 以防止记重**，我们可以选取 $|S|-|N(S)|$ 最大的集合 $S$ 作为代表元，若存在多个满足条件的 $S$，选取其中 $|S|$ 最小的一个。可以使用[反证法](http://192.168.102.138/JudgeOnline/upload/attachment/file/20250223/20250223070733_13110.pdf)证明此时代表元唯一。考虑设状态 $G(S,T)$ 表示考虑左部点集 $S$ 和右部点集 $T$ 之间的所有边，满足 $N(S)=T$ 且 $S$ 为该非法子图的代表元的概率。类似地，设 $F(S,T)$ 表示考虑 $S,T$ 之间的边，满足 $N(S)=T$ 且存在左部点的完美匹配的概率。容斥转移如下： $$F(S,T)=P(S,T)-\sum_{\substack{S'\sube S,T'\sube T\\|S'|>|T'|}}G(S',T')\cdot F(S-S',T-T')\cdot E(S',T-T')$$ $$G(S,T)=P(S,T)-\sum_{\substack{S'\sube S,T'\sube T\\|S'|-|T'|\ge |S|-|T|\\(S,T)\ne (S',T')}}G(S',T')\cdot F(S-S',T-T')\cdot E(S',T-T')$$ 其中 $P(S,T)$ 表示考虑 $S,T$ 的导出子图，$N(S)=T$ 的概率，$E(S,T)$ 表示 $S,T$ 间无边的概率。式子中乘上 $F(S-S',T-T')$ 的原因是，若该部分不合法，选取其中的代表元可以得到一个更优的代表元，反之则不可能得到更优的代表元。时间复杂度 $O(9^n)$。 **** ### [[广东省队集训 2025] 白](http://8.138.223.198/p/6) 给你一个长为 $n$ 的排列 $p_{1\sim n}$，你可以对其执行一次如下操作： - 选取 $k$ 个不交区间 $[l_1,r_1],\dots,[l_k,r_k]$，分别将 $p_{l_1\sim r_1},\dots,p_{l_k\sim r_k}$ 升序排序。求经过一次操作能得到多少种不同的排列 $p_{1\sim n}$。 $n\le 2\times 10^5$。 **** 钦定单射，将一种结果排列对应至唯一一种操作方案。不妨钦定选取所有极短的可操作区间进行操作，此时要求没有任何一个选取的区间可以划分为两个区间，使得前一个区间的最大值小于后一个区间的最小值。不合法区间必定存在一个 $v$ 使得 $\le v$ 的数构成一个前缀，于是可以按值域从小到大扫描，将 $\le v$ 的数记为 $1$，每形成一个 $1$ 的连续段将其与其后的 $0$ 连续段做矩形加。线段树优化 DP 即可。时间复杂度 $O(n\log n)$。 **** ### [咏叹调调律](https://www.luogu.com.cn/problem/P12264) 对于一个字符集为 $\{\tt A,B,C\}$ 的字符串，若其可通过不断删去其中的 $\tt AB,CA,AAA,CCB$ 子序列将其删空，则称该串是好的。给定常数 $p,q,r$，对于一个好的串，若其中分别有 $a,b,c$ 个 $\tt A,B,C$，那么定义其权值为 $p^aq^br^c$。给定正整数 $n$，对于所有的 $1\le k\le n$，求出所有长为 $k$ 的好的串的权值和，对 $998244353$ 取模。 $n\le 500$。 **** 首先观察字符 $\tt A$，可以知道必定有一个前缀的 $\tt A$ 匹配 $\tt AB$、一个后缀的 $\tt A$ 匹配 $\tt CA$。如果我们可将 $\tt AAA$ 划分为两部分，那么就可以变为一个前缀的 $\tt A$ 匹配 $\tt AB$ 或 $\tt AAA$ 的前半部分，而剩余后缀中的 $\tt A$ 匹配 $\tt CA$ 或 $\tt AAA$ 的后半部分，接下来将前缀 $\tt A$ 与后缀 $\tt A$ 分别记作 $\tt A_L,A_R$。接下来是一个核心观察：**将 $\tt{{ A_L,C,A_R,B}}$ 分别看作两个左括号、一个左括号、一个右括号、两个右括号，则一次操作可删去的串为合法括号串**。注意这只是必要条件，因为我们不能将两个左括号或右括号匹配不同类型的字符，如 $\tt A_LA_RCB$ 是不合法的，我们只能通过括号匹配的思想进行性质推导。由于替换后的括号串，其合法首先是一个必要条件，这也告诉我们如果一个字符串合法，其必定唯一对应一种替换 $\tt A$ 为 $\tt A_L,A_R$ 的方式。由于单括号的匹配自由度高于双括号的匹配自由度，故四种删除方式的优先级为 $\tt A_LB>A_LA_RA_R/CCB>CA_R$。接下来开始考虑 DP。首先必须要记录当前的总长与字符 $\tt A_L$ 与 $\tt C$ 分别剩余的个数 $i,j,k$ 三维，故接下来只能增加一些常数维度： - 需要增加一维 $0/1$ 表示当前的字符 $\tt A$ 对应字符 $\tt A_L$ 还是字符 $\tt A_R$； - 当出现字符 $\tt A_R$ 时，我们优先考虑匹配 $\tt A_LA_R$ 并等待下一个 $\tt A_R$，但由于 $\tt A_LB$ 的优先级高于 $\tt A_LA_RA_R$，故如果当前可匹配 $\tt CA_R$，需要预留一次反悔机会，增加一维 $0/1/2$ 分别表示不存在 $\tt A_LA_R$/存在不可反悔的 $\tt A_LA_R$/存在可反悔的 $\tt A_LA_R$ 即可。当出现 $\tt B$ 时，优先考虑与当前未配对的 $\tt A_L$ 匹配，再考虑与当前可反悔的 $\tt A_LA_R$ 进行匹配，最后尝试匹配 $\tt CCB$；若存在已配对的 $\tt A_LA_R$ 时再出现 $\tt A_R$，那么必定将其匹配为 $\tt A_LA_RA_R$，如果不这么做则此时必定存在两个 $\tt C$，下次出现 $\tt B$ 必定可匹配一组 $\tt CCB$。直接枚举添加的字符类型做 DP 即可，时间复杂度 $O(n^3)$。 **** ### [Harsh Comments](https://vjudge.net/contest/713031#problem/C) 给定 $n,m$，有 $n$ 个一类物品以及 $m$ 个二类物品，重量分别为 $a_{1\sim n}$ 和 $b_{1\sim m}$。每一次操作均会在还未取出的物品中按照重量均匀随机地取出一件物品，问取出所有一类物品的期望操作次数。答案对 $998244353$ 取模。 $n,m\le 500$，$a_i\le 500$。 **** **由期望的线性性，我们将答案拆到每一个二类物品上**，即对每一个二类物品求它在所有一类物品均被取出前被取出的概率。对于一类物品子集 $S$，定义 $\max(S)$ 为取出所有 $S$ 中一类物品前二类物品被取出的概率，$\min(S)$ 为取出任意 $S$ 中一类物品前二类物品被取出的概率。容易发现 $\min(S)$ 就等于 $\dfrac{b_j}{b_j+\sum_{i\in S}a_i}$，使用 Min-Max 容斥，只需算出所有子集和的容斥系数和即可。注意要求 $O(nmv)$ 个分数之和，可以先分数求和再求逆。时间复杂度 $O(nmv+n^2v)$。 **** ### [催眠术](https://www.luogu.com.cn/problem/P12152) 给定 $n,m,v$ 以及一个长为 $m$ 的值域在 $[1,v]$ 中的整数序列 $a$，再给定一个大小为 $n \times (m+1)$ 的矩阵 $c_{1\sim n,0\sim m}$。定义一个整数序列是好的，当且仅当它的值域在 $[1,v]$ 中且所有值域在 $[1,v]$ 的长为 $m$ 的整数序列都是它的子序列。定义一个好的整数序列 $b$ 的价值为 $\prod\limits_{i=1}^n c_{i,p_i}$，其中 $p_i$ 为 $a$ 的最长前缀长度使得 $a_{1 \sim p_i}$ 是 $b_{1\sim i}$ 的一个子序列，若不存在则 $p_i = 0$。求所有长度为 $n$ 的好序列的价值和，答案对 $10^9+7$ 取模。 $n,m,v\le 400$。 **** 题目强制我们一个个地向后填数，且要求所有长为 $m$ 的序列都出现过，即可以划分出 $m$ 段且每一段内所有 $[1,v]$ 的数均出。显然 $m\cdot v\le n$，否则无解。设 $f_{i,j,k,p,q}$ 表示填了 $i$ 个数，目前匹配到位置 $j$，已经填完了 $k$ 段，当前段中已经填入了 $p$ 种匹配过的数，$q$ 种未匹配的数。由于 $j,k\le m$ 且 $p,q\le v$，状态数是可接受的。但是我们需要要求相邻两个匹配的位置间不能出现于右侧匹配位置相同的数，这需要得知上一次匹配时有多少种未匹配的数，但我们不能在状态上再填一维。考虑一段转移的形式： - 在一段中相邻两个匹配位置之间进行转移； - 在一段中最后一个匹配位置至段末之间进行转移。 **其特点为转移不相交且转移的终止位置需要起始位置的信息，不妨新开状态表示当前处于一段转移，并在开启一段转移的时候提前将贡献乘入**。时间复杂度 $O(n^3)$，可以通过。 # 最优化 ### [双向奔赴](https://pjudge.ac/contest/951/problem/21655) 给你一张 $n$ 个点的无向图，你需要给每条边定向。对于每条边 $(u,v)$，将其定向为 $u\to v$ 和 $v\to u$ 分别有一个代价，求使得图强连通的最小代价。 $n\le 18$。 **** 对于一个强连通分量 $S$，找 $i,j\in S$，若存在一条 $i\to j$ 且经过的结点集合为 $T$ 的路径，则可拓展到强连通分量 $S\cup T$。设 $f_{s,i,j}$ 表示路径结点集合为 $s$，路径起点为 $i$，目前路径终点为 $j$ 的最小代价，$g_s$ 表示集合 $s$ 构成强连通分量的最小代价，可以做到 $O(3^n+2^nn^3)$。路径单独分开算是不优秀的，我们不妨直接以当前点集（一个强连通分量加上一条从其中向外连的路径）为状态尝试转移。注意到我们并不知道哪些点属于强连通分量，但从一个强连通分量开始拓展时我们可以事先预设路径终点。于是我们沿用 $g_s$，重新设 $f_{s,i,j}$ 表示当前点集为 $s$，当前路径终点为 $i$，我们设定的路径终点为 $j$，可以转移，时间复杂度 $O(2^nn^3)$。启示**将多个状态合并考虑**。 **** ### [[2024 联考 II Day3] 换换](http://192.168.102.138/JudgeOnline/problem.php?cid=2176&pid=0) 有一个长为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$ 和两个参数 $l,r$。每次操作可以交换 $a$ 中某两个数。当序列满足 $\exists k\in[1,n],l\le\left(\displaystyle\sum_{i=1}^k a_i\right)\le r$ 时操作结束。请求出最小的操作次数。 $\sum n\le 10^4$，$n,r,a_i\le 5\times 10^3$。 **** 先转化为 $\sum_{i\in S}a_i\in[l,r],\min\sum_{i\in S}[i>|S|]$，考虑分前后两段来看。设前面 $a$ 个，后面 $b$ 个，则前 $a+b$ 个选 $a$ 个，要最小化 $b$。固定前缀长度必然要使 $a$ 尽量大，则设 $f_{i,v}$ 前缀 $i$ 选出来和为 $v$ 的最大选择个数，$g_{i,v}$ 后缀 $i$ 需要前缀 $i-1$ 选出来和为 $v$ 时后缀 $i$ 的最小选择个数。答案所有满足 $f_{i,v}+g_{i+1,v}=i$ 的最小 $g_{i+1,v}$。发现**每种合法方案必然有一种不劣于它的方案被统计到**，算法正确。时间复杂度 $O(nv)$。 **** ### [[2024 联考 IV Day1] 最优划积树法则 / tree](http://192.168.102.138/JudgeOnline/problem.php?cid=2193&pid=0) 给你一颗 $n$ 个结点的树，其中点 $i$ 带有点权 $v_i\in\{0,1,2\}$。再给定一个常数 $k$，你要选出尽量多互不相交的连通块使得每个连通块的点权和均为 $k$。 $n\le 10^6$。 **** 考虑对于一个点权和 $s(s\ge 3)$ 的连通块，先将其所有点权为 $0$ 的叶子删去，则： - 若存在点权为 $2$ 的叶子，将其删去可得到点权和为 $s-2$ 的连通块； - 否则所有叶子点权为 $1$，删去两个叶子可得到点权和为 $s-2$ 的连通块。所以设 $f_{i,0/1}$ 表示 $i$ 子树内包含 $i$ 的连通块为奇数/偶数的最大点权和。从下至上贪心，若 $f_{i,k\bmod 2}\ge k$ 则直接截取该连通块，之后就不考虑 $i$ 子树了。时间复杂度 $O(n)$。类似最优化问题可以考虑**奇偶性**。 **** ### [[省选联考 2024] 迷宫守卫](https://www.luogu.com.cn/problem/P10220) 有一颗深度为 $n+1$ 的完全二叉树，其叶子上依次标有一个长为 $2^n$ 排列 $a$，非叶结点有选择代价 $b_i$。Alice、Bob 两人进行游戏。Alice 可以选择一些选择代价和不超过 $m$ 的非叶结点，此后 Bob 会从根开始深度优先搜索，有一初始为空的序列 $p$，设当前 Bob 在 $x$ 结点， - 若 $x$ 结点为叶子，则将 $a_x$ 加入序列 $p$ 末尾； - 若 $x$ 结点非叶子且被 Alice 选择，则 Bob 将先搜索左子树再搜索右子树； - 若 $x$ 结点非叶子且未被 Alice 选择，则 Bob 可以选择先搜索左子树还是先搜索右子树。 Alice 希望 $p$ 字典序尽量大，而 Bob 希望其尽量小。两人均采用最优策略，求最终的序列 $a$。多组数据。 $n\le 16$，$\sum 2^n\le 10^5$。 **** 设 $f_{i,x}$ 表示使得 Bob 进入 $i$ 子树后加入 $p$ 的第一个数为 $x$ 的最小代价，状态数总和为 $O(2^nn)$，容易转移（做后缀 $\min$、归并）： $$f_{i,x}=\begin{cases}f_{ls,x}+\min(\min_{y>x}f_{rs,y},b_i)&x\in\text{subtree}(ls)\\f_{rs,x}+\min_{y>x}f_{ls,y}&x\in\text{subtree}(rs)\end{cases}$$ 那么 $p_1$ 的值就确定为满足 $f_{1,x}\le m$ 的最大的 $x$。此后的选择都要满足 $p_1$ 固定，于是我们设计 $g_i$ 表示使得 $i$ 子树内已经填入 $p$ 内的数确定下来的最小代价，令 $h_i$ 表示子树内已经确定填入 $p$ 的第一个数，如果没有则为 $-1$。 $$g_{i}=\begin{cases}g_{ls}+g_{rs}&h_i=h_{ls}\land h_{rs}\ne -1\land h_{ls}<h_{rs}\\g_{ls}+g_{rs}+b_i&h_i=h_{ls}\land h_{rs}\ne -1\land h_{ls}>h_{rs}\\g_{ls}+\min(\min_{y>h_{i}}f_{rs,y},b_i)&h_i=h_{ls}\land h_{rs}= -1\\+\infty&h_i=h_{rs}\land h_{ls}\ne -1\land h_{ls}<h_{rs}\\g_{ls}+g_{rs}&h_i=h_{rs}\land h_{ls}\ne -1\land h_{ls}>h_{rs}\\g_{rs}+\min_{y>h_{i}}f_{ls,y}&h_i=h_{rs}\land h_{ls}= -1\end{cases}$$ 选择完 $p_1$ 后，更新 $p_1$ 对应节点至根的 $g,h$，再从下至上依次调用另一颗子树的递归问题。根为 $i$ 的递归问题可考虑枚举子树内第一个数 $x$，将 $g_i,h_i$ 分别设为 $f_{i,x},x$ 再依次更新至根，检查 $g_1\le m$ 是否成立，再撤回更新。子树内第一个选取的数即为使得 $g_1\le m$ 成立的最大的 $x$，更新并递归即可。每次计算 $g$ 如果都在所需的儿子的 $f$ 中二分，时间复杂度为 $O(2^nn^3)$，无法通过。注意到 $\min_{y>h_{i}}f_{*,y}$ 在 $h_i$ 确定后是不变的，可以在确定 $h_i$ 时就处理出，则每次更新一个点到根的复杂度降至 $O(n)$，总时间复杂度 $O(2^nn^2)$，可以通过。注意到 $g$ 的转移方式仅与 $h$ 相关，可以在 $h_i$ 从 $-1$ 变为非 $-1$ 时算一下 $g_i$ 对 $g_1$ 的贡献。设定 $g_i,h_i$ 后可直接 $O(1)$ 求出对 $g_1$ 的贡献，时间复杂度降至 $O(2^nn)$。 **** ### [Favorite Game](https://www.luogu.com.cn/problem/CF1523F) 有一个平面，其上有 $n$ 个传送门 $(p_i,q_i)$ 以及 $m$ 个任务 $(x_i,y_i,t_i)$。传送门初始均为关闭状态，第 $i$ 个任务要求玩家在 $t_i$ 时刻位于点 $(x_i,y_i)$。玩家选择一个整点并在 $0$ 时刻到达，接下来每秒玩家可以不动或向上下左右走一步。当玩家到达一个未激活传送门时此传送门被激活，之后玩家在任意时刻任意位置都可以立刻瞬移到这个传送门。求玩家最多可以完成几个任务。 $n\le 14$，$m\le 100$。 **** 设 $f_{s,i,j}$ 表示已经开启了 $s$ 的传送门，现在在点 $i$，已经完成了 $j$ 个任务的最小时间。预处理 $d_{s,i}$ 表示从 $s$ 的传送门到点 $i$ 的最小时间，可以做到 $O(2^nm^3)$。传送门和任务点之间有四种转移，发现从传送门的转移不需要知道现在在哪个点，从任务点的转移的时间是确定的，所以分离状态设 $f_{s,j}$ 表示已经开启了 $s$ 的传送门，现在在某个传送门，已经完成了 $j$ 个任务的最小时间，$g_{s,i}$ 表示已经开启了 $s$ 的传送门，时刻 $t_i$ 在任务点 $i$，最多完成几个任务，可以做到 $O(2^nm^2)$。启示**将多个状态分离考虑，某些状态不需要某些信息**。 **** ### [Juggler's Trick](https://qoj.ac/contest/819/problem/2548) 有 $n$ 个球排成一排，有红蓝白三色，给定 $a,b$，你可以选择连续的 $a+b$ 个球满足其中红球数为 $a$ 且蓝球数为 $b$ 并将这些球删去。你需要将白球确定为红蓝某色，然后进行若干次操作，求出最多删去多少个球。 $n\le 2\times 10^5$。 **** 令 $c=a+b$，则若有连续的 $kc$ 个球满足其中红蓝球数分别为 $ka,kb$，则这 $kc$ 个球能全部删去。考虑归纳证明。由于抽屉原理，必然存在连续的 $c$ 个球满足其中红球数 $\le a$ 及连续的 $c$ 个球满足其中红球数 $\ge a$。**考虑将区间移动一位，红球数最多变化 $1$，则将一个 $\le a$ 的区间一位一位移动到 $\ge a$ 的区间的过程中必然存在 $=a$ 的区间**。接下来 DP 就简单了，令 $p_i,q_i$ 分别为红球蓝球数的前缀和，要从 $i$ 转移到 $j$ 的条件就是： - $i\equiv j\pmod c$； - $p_j-p_i\le \dfrac{(j-i)a}{c}$； - $q_j-q_i\le \dfrac{(j-i)b}{c}$。三维偏序，直接 CDQ 即可，时间复杂度 $O(n\log^2n)$。 **** ### [ランプ / Lamps](https://www.luogu.com.cn/problem/AT_joisc2019_h) 给你一个 01 序列 $a_{1\sim n}$。有 $n$ 盏灯，初始全为关闭状态，你需要对其进行若干次操作使得其状态变为 $a_{1\sim n}$。有三种可以执行的操作，每种操作中你可以选择一个区间 $[l,r]$： - 关闭 $[l,r]$ 内所有灯； - 开启 $[l,r]$ 内所有灯； - 转换 $[l,r]$ 内所有灯的开关状态。求出最少的操作次数。 $n\le 10^6$。 **** 我们不难**将所有翻转操作挪到赋值操作后面**。于是现在就是先进行若干赋值操作再进行若干翻转操作。注意到**赋值操作和翻转操作均互不相交**，于是设 $f_{i,0/1/2,0/1}$ 表示 $i$「不赋值 / 赋值为 $0$ / 赋值为 $1$」「不翻转 / 翻转」即可。时间复杂度 $O(n)$。 **** ### [Minimum Sum of Maximums P](https://www.luogu.com.cn/problem/P10197) 有一个长为 $n$ 的序列 $a_{1\dots n}$，初始有 $k$ 个位置 $a_{p_1}\dots a_{p_k}$ 已经有值，其余位置均无值。此外还有 $n-k$ 个数 $b_{1\dots n-k}$，你需要将它们放入初始无值的位置并最小化 $\sum_{i=1}^{n-1}\max(a_i,a_{i+1})$。 $n\le 300$，$k\le \min(n,6)$。 **** 最小化 $\sum\max(a_i,a_{i+1})$ 等价于最小化 $\sum|a_i-a_{i+1}|$。固定的点将序列划分为若干段，要将剩余的数填进去。注意到一个区间内填的数必然是有序的，所以只需要考虑给这个区间填的最小值和最大值，不妨设为 $l_i,r_i$，若这个区间固定的两端点的值分别为 $a_i,b_i$，则这个区间的代价为 $r_i-l_i+|a_i-l_i|+|b_i-r_i|$。使用**调整法**可以说明一定有某种最优方案使得所有的 $[l_i,r_i]$ 不交，使用区间 DP 即可。详细题解可见 [详细揭秘：区间 DP 小计](https://www.luogu.com.cn/article/6o5kdrh3)。 **** ### [[2024 联考 III ACM] Si](https://codeforces.com/gym/542554/problem/K) 给你一个长为 $n$ 的单调递增的序列 $a_{1\dots n}$，你需要猜出一个数 $x\in[1,n]$。每次可以询问一个整数 $y$，你将会得到 $y\le a_x$ 是否成立，该次询问会造成 $|a_x-y|$ 的代价且你并不知道该代价。求出确定 $x$ 所需要的最小代价和。 $n\le 1000$。 **** 将代价中的绝对值拆掉，设 $f_{l,r,c}$ 表示已经确定 $x\in[l,r]$，且询问的所有 $y$ 中小于 $a_x$ 的个数减去大于 $a_x$ 的个数为 $c$。则 $f_{i,i,c}=ca_i$，转移为： $$f_{l,r,c}=\min_{k=l}^{r-1}\min_{y=a_k+1}^{a_{k+1}}\max(f_{l,k,c-1}+y,f_{k+1,r,c+1}-y)$$ 其中对于单个 $k$ 其对应的最小 $y$ 显然可以 $O(1)$ 计算。而经过尝试，$c$ 的绝对值不会超过 $O(\log v)$，于是我们得到了一个 $O(n^3\log v)$ 的算法。考虑优化，**优化最优化区间 DP 常用决策单调性**，归纳易证 $f_{l+1,r,c}\le f_{l,r,c}\le f_{l,r+1,c}$，于是我们可以证明 $f_{l,r,c}$ 的决策点 $\text{opt}_c(l,r)$ 满足 $\text{opt}_c(l,r-1)\le\text{opt}_c(l,r)\le \text{opt}_c(l+1,r)$。直接使用决策单调性优化便可做到 $O(n^2\log v)$。 **** ### [Nawiasowe podziały](https://www.luogu.com.cn/problem/P9266) 给出一个长为 $n$ 的括号串以及一个整数 $k$。请将其分为 $k$ 个非空段，使得每段中的合法子串个数之和最小。 $n\le 10^5$。 **** 令左括号为 $1$，右括号为 $-1$，前缀和为 $s_i$，则 $[l,r]$ 是合法括号串当且仅当 $s_{l-1}=s_r=\min_{i=l-1}^rs_i$。由于**同时有相等关系和 $\bm{\min}$ 的限制**，我们选择抛弃笛卡尔树的二叉树性质，建出**广义笛卡尔树**。具体地，将当前区间中所有的最小值作为分界点划分为若干个子区间。称一个区间对应的点为方点，一个分界点为圆点。广义笛卡尔树也可使用单调栈线性建出。考虑 $[l,r]$ 有多少个子区间为合法括号串，答案即为 $(l,r]$ 中有多少点对 $(i,j)$ 使得 $i<j$ 且圆点 $i,j$ 的父亲相同，将贡献拆到每一个方点上。易证 $w(l,r)$ 满足四边形不等式，将划分为 $k$ 段视作设置 $k-1$ 个分界点，考虑 **wqs 二分**。设 $f_x$ 表示 $x$ 子树内至少设置了一个划分点的最小代价，由于有多个子节点所以在转移时还需要辅助数组 $g_{i}$ 表示考虑了 $x$ 的前 $i$ 个子树，钦定在第 $i$ 个子树内设置了分界点的最小代价。转移可以轻松写出，转移方程的形式可以**斜率优化**，注意状态为双关键字，有许多细节。时间复杂度 $O(n\log n)$。 **** ### [[NOIP2018] 赛道修建](https://www.luogu.com.cn/problem/P5021) 给出一颗 $n$ 个点的树，其有边权。你需要从中选出 $m$ 条不相交的链，最大化这些链的边权和的最小值。 $n\le 10^5$。 **** 先二分，然后就是求最多取出多少长度 $\ge k$ 的不相交链。一个平凡的想法是一个子树内最多只有一条链向外连，于是令 $f_{u,i}$ 表示 $u$ 子树内选出了 $i$ 条链时挂在 $u$ 上向外连的链的最长长度。每个子树一定都取到链数的最大值，其正确性是因为假如我们加长挂在子树 $u$ 的链，那么也最多在 $u$ 子树外多形成一条合法链，不会优于子树内取到最大链数的方案。时间复杂度 $O(n\log n\log v)$。 **利用贪心与调整法，寻找最优答案的性质，降低状态数**。 **** ### [Bear and Rectangle Strips](https://www.luogu.com.cn/problem/CF771E) 给你一个 $2\times n$ 的矩阵 $t_{1\sim 2,1\sim n}$，求最多能切出多少个互不相交的权值和为 $0$ 的子矩阵。 $n\le 3\times 10^5$。 **** 可以线性求出 $s_{0/1/2,i}$ 表示在 $i$ 后位于第一行/第二行/同时包含两行的零权矩形的最小右端点。令 $f_{i,j}$ 表示两行分别考虑到第 $i,j$ 列时的答案，则有平凡的 $O(n^2)$ 做法。 **我们尝试规定转移的顺序以减少状态数量**。我们规定，按照矩形的左端点从小到大转移，则有： - 对于一状态 $(i,j)$，其中 $i<j$，如果第二行有超过一个右端点大于 $i$ 的子矩形，那么该状态是无用的。 - 令 $t$ 表示第二行第二个右端点大于 $i$ 的子矩形的左端点，则第一行不可能有左端点在 $t$ 之前的子矩形，那么可以直接用 $f_{t,j}$ 取代此状态。换句话说，我们只需要维护 $f_{i,j}=f_{i,i}+1$ 的最小 $j$ 即可。时间复杂度 $O(n)$。 **DP 只要使得任何最优合法解都能被生成即可，从而不必要记录所有可能的状态。** **** ### [[2023 NOI模拟 Day28] 光](http://192.168.102.138/JudgeOnline/problem.php?cid=2039&pid=2) 数轴上有 $n$ 个点 $(p_1,0),\dots ,(p_n,0)$，以这些点作为圆心，作出 $n$ 个圆，使得没有两个圆相交，求最大总面积和。 $n\le 5\times 10^6$。 **** 设圆 $i$ 的半径为 $r_i$，要求 $r_i+r_{i+1}\le p_{i+1}-p_i$。 **最优化问题可考虑对一个合法状态进行不断的调整，使得限制仍然满足并使得答案不劣，并依此得到最优答案的特殊性质来优化求解**。考虑一段不断极长的相切的圆，考虑对其调整。考虑让某个 $r_i$ 加一，那么相应地 $r_{i-1},r_{i+1}$ 就要减一。经过一些尝试，我们可以得到调整的基础形式为将奇数编号半径加一、偶数编号半径减一或者相反，而可以列式得到总有一种调整的方向使得答案增加。这就得到了最终构造的一个性质，可以依此进行多项式复杂度的 DP。另一个更强的性质是对于 $r_i\ge \max(r_{i-1},r_{i+1})$，必定有 $r_i=\min(p_i-p_{i-1},p_{i+1}-p_i)$，可以列式计算得出该结论。剩余的部分较为平凡，详细见[原题解](http://192.168.102.138/JudgeOnline/upload/attachment/file/20220505/20220505092709_46381.pdf)。 **** ### [Paired Up P](https://www.luogu.com.cn/problem/P7985) 数轴上有 $n$ 个点，每个点有位置 $x_i$、颜色 $c_i\in\{0,1\}$、权值 $v_i$。给你一个常数 $k$，你需要选出一个极大匹配使得每对匹配的点 $i,j$ 均满足 $c_i\ne c_j$ 且 $|x_i-x_j|\le k$。输入一个参数 $t\in\{1,2\}$，当 $t=1$ 时求出不在匹配内的点的权值和的最小值；当 $t=2$ 时求出该值的最大值。 $n\le 5000$。 **** 显然通过调整可以使得匹配中两种牛的编号均递增。先解决 $t=1$ 的子任务。设 $f_{i,j}$ 表示 H 牛、G 牛分别考虑到 $i,j$，不计入 $i,j$ 时的答案，只考虑不匹配 $i$、不匹配 $j$、匹配 $i,j$ 三种转移。**考虑一组匹配，如果其不是极大匹配，那么其定然取不到最小答案，即最小答案必定为极大匹配**，直接 DP 即可。但是 $t=2$ 时并没有这种性质，于是还需要升维记录上一个未匹配的牛。设 $f_{i,j,a,b}$ 表示 H 牛、G 牛分别考虑到 $i,j$，上一个不匹配的 H 牛、G 牛分别为 $a,b$ 的答案。四维状态过大，**尝试降维，寻找重复或无需同时记录的信息**。讨论一下，不妨设 $x_{\text H,a}<x_{\text G,b}-k$，那么由于接下来 G 牛的 $x$ 均大于 $x_b$，所以 $a$ 不会对后续造成限制，反之同理，可以少记录一维。时间复杂度 $O(n^3)$，无法通过。多记录的一维状态 $a/b$ 描述了当前允许所有 H/G 牛和限制 G/H 牛，尝试只记录允许的种类。设 $f_{i,j,0/1}$ 表示 H 牛、G 牛分别考虑到 $i,j$，当前允许所有的 H/G 牛的答案。需要思考更改允许类别的转移，不妨**钦定此时的状态 $(i,j,0)$ 中 $i$ 为最后一头不匹配的 H 牛**，找到最小的 $l\ge j$ 使得 $x_{\text G,l}>x_{\text H,i}+k$，转移至 $(i+l-j+1,l,1)$ 即可。注意此种转移需要 $(x_{\text H,i+1},x_{\text G,j}),(x_{\text H,i+2},x_{\text G,j+1})\dots (x_{\text H,i+l-j},x_{\text G,l-1})$ 均可匹配，可预处理。时间复杂度 $O(n^2)$，可以通过。 **** ### [[JSOI2007] 建筑抢修](https://www.luogu.com.cn/problem/P4053) 有 $n$ 个任务 $(t_i,l_i)$ 表示完成此任务需要 $t_i$ 的时间且该任务的截止时间为时刻 $l_i$。求出最多能完成多少个任务。 $n\le 1.5\times 10^5$。 **** **如果已经确定了完成的任务，那么一定是按截止时间从小到大完成这些任务，于是我们可预先按照 $l_i$ 排序并依次决策**。令只考虑前 $i$ 个任务的最优方案为 $S_{i}$，其中最优方案为在完成任务数量最多的情况下所用时间最小的方案。考虑**在 $S_{i-1}$ 的基础上增量求出 $S_i$**。 - 如果可以在 $S_{i-1}$ 不变的基础上完成任务 $i$，那么直接有 $S_{i}=S_{i-1}\cup\{i\}$； - 否则要完成任务 $i$ 必须从 $S_{i-1}$ 中删去一个任务，那么如果 $S_{i-1}$ 中所需时间的最大值大于 $t_i$，将该值替换为 $t_i$ 即可。可以使用调整法证明该做法的正确性。时间复杂度 $O(n\log n)$。 **** ### [[2023 NOI模拟 Day8] 菜粥鱼](http://192.168.102.138/JudgeOnline/problem.php?cid=2000&pid=0) 给你一颗 $n$ 个结点的树以及两个序列 $a_{1\sim n},b_{0\sim n}$。你需要选出若干关键点，选定 $i$ 为关键点会造成 $a_i$ 的花费。设 $c_i$ 表示结点 $i$ 与最近的关键点之间的距离，你将得到 $\sum b_{c_i}$ 的收益。求出收益减花费的最大值。 $n\le 3000$。 **** 我们只需知道序列 $c$ 就能求出利润，类似于判定型计数，于是不妨考虑判定一个序列 $c$ 是否合法，只需满足对于所有的 $c_u\ne 0$ 均有 $c_u=\min_{v} c_v+1$ 即可。于是设计状态 $f_{i,j,0/1}$ 表示考虑了子树 $i$，$c_i$ 为 $j$，是否存在一个子节点 $v$ 使得 $c_i=c_v+1$，可以转移。时间复杂度 $O(n^2)$。 **** ### [水杯降温](https://www.luogu.com.cn/problem/P11189) 给你一颗 $n$ 个点的树，根为结点 $1$，点有点权 $v_i$，你可以执行任意次如下操作： - 选择任意结点 $x$，将点 $x$ 的子树内的点权全部减一； - 选定任意叶子结点 $x$，将 $x$ 到根的路径上的点的点权全部加一。问能否通过任意次操作使得所有点的点权均为 $0$。 $\sum n\le 10^6$。 **** **先做操作二再做操作一**。考虑一个局面是否能只进行操作一清零，那么条件即为： - 所有点点权非负； - 父亲的点权小于等于儿子的点权。第一个条件可改为根的点权非负，那么设 $f_i$ 表示子树 $i$ 最多做几次操作二，转移可以二分。时间复杂度 $O(\sum n\log v)$。 **** ### [合并序列](https://www.luogu.com.cn/problem/P9746) 给定一个长度为 $n$ 的序列 $a_{1\sim n}$。你可以对这个序列进行若干次操作，每次操作： * 选择三个正整数 $i<j<k$，满足 $a_i\oplus a_j\oplus a_k=0$ 且 $k$ 的值不超过此时序列的长度。记 $s=a_i\oplus a_{i+1}\oplus \cdots\oplus a_k$。 * 然后，删除 $a_i\sim a_k$，并在原来这 $k-i+1$ 个数所在的位置插入 $s$。判断是否能够使得序列 $a$ 仅剩一个数，也就是说，在所有操作结束后 $a$ 的长度为 $1$。若可以，你还需要给出一种操作方案。多组数据。 $T\le 20$，$n\le 500$，$a_i\le 511$。 **** 设 $s(l,r)$ 表示区间 $[l,r]$ 的异或和。任意时刻，序列中的每一个元素都是由初始的一个区间合并而来。设 $f_{l,r}$ 表示 $[l,r]$ 是否能缩成一个点，如果区间中存在四个下标 $l\le a<b\le c<d\le r$ 满足 $f_{l,a}=f_{b,c}=f_{d,r}=1$ 且 $s(l,a)\text{ xor }s(b,c)\text{ xor }s(d,r)=0$，那么 $f_{l,r}$ 就等于 $1$。暴力转移时间复杂度 $O(n^6)$，无法通过。 **考虑到我们同时枚举了三个区间，不妨进行分步转移，逐个添加区间**。设 $g_{l,v}$ 表示满足 $l\le b\le c$，$f_{b,c}=1$ 且 $s(b,c)=v$ 的情况下最小的 $c$；设 $h_{l,v}$ 表示满足 $l\le a<b\le c$，$f_{l,a}=f_{b,c}=1$ 且 $s(l,a)\text{ xor }s(b,c)=v$ 的情况下最小的 $c$。三个状态分别维护了第二个区间、第一二个区间和全部三个区间的信息，分别枚举一个可进行转移。时间复杂度 $O(n^3+n^2v)$，可以通过。 **** ### [夏天 / summer](https://www.luogu.com.cn/problem/P11218) 给你一个 $2\times n$ 的网格，每个格子有黑白之一的颜色。再给你一个常数 $m$。有两人进行博弈，先手在网格上选择一个可空的连通块，后手选择不超过 $m$ 列并交换选出的列中两个格子的颜色。两人进行完操作后，定义分数为此时先手选出的连通块内的黑色格子数量减白色格子数量。先手希望最大化分数，而后手希望最小化分数。求出两人都采用最优策略的情况下的分数。 $n\le 2\times 10^6$。 **** 后手只会操作「两行颜色不同且只有黑格被选入连通块」的列，记连通块内除了这些列的分数为 $s$，这种列的数量为 $c$，那么该局面的分数即为 $s+|c-m|-m$。记录一维 $c$ 是无法接受的，但是由绝对值的性质 $|c-m|=\max(c-m,m-c)$，**取 $\bm{\max}$ 与我们的 DP 取值方向是相同的**，那么可以分别将这种列的分数设为 $1$ 以及 $-1$，进行两次 DP 并取较大值。时间复杂度 $O(n)$。 **** ### [青鱼和怪兽](https://pjudge.ac/contest/1114/problem/21743) 给定常数 $n,m,p$，其中 $p\in(0,1)$。有一点对 $(a,b)$，初始等于 $(n,m)$，有一整数 $x=0$，接下来： - 当 $a=0$ 时，将 $(a,b)$ 重置为 $(n,m)$； - 当 $b=0$ 时，结束整个过程； - 否则，你可以选择： - 将 $(a,b)$ 重置为 $(n,m)$； - 令 $x\gets x+1$，并以 $p$ 的概率执行 $b\gets b-1$ 以及 $1-p$ 的概率执行 $a\gets a-1$。你希望最小化结束时 $x$ 的值，求出最优策略下结束时 $x$ 的值的期望。 $n,m\le 1000$。 **** 依题意可以列出转移： $$f_{i,j}=\min(p\cdot f_{i,j-1}+(1-p)\cdot f_{i-1,j}+1,f_{n,m})$$ 边界为 $f_{0,*}=f_{n,m},f_{*,0}=0$。 **转移成环，无法直接转移，不妨钦定环中特殊点的值**。设 $f_{n,m}=x$，那么可归纳证明 $f_{i,j}$ 是关于 $x$ 的一次分段函数且每一段的斜率均 $\le 1$。那么我们可以二分 $x$ 的值，找到 $f_{n,m}(x)=x$ 即为答案。时间复杂度 $O(nm\log v)$。 **** ### [[NOIP2017] 宝藏](https://www.luogu.com.cn/problem/P3959) 给你一个 $n$ 个点的图，初始无边，再给出 $m$ 条带权无向边表示可以建立的边集。你需要选择一个点 $s$ 作为源点，初始你仅可到达源点 $s$，此后你可以选择一条边 $(u,v,w)$ 满足当前 $u$ 可到达且 $v$ 不可到达，花费 $w\cdot d$ 的代价加入边 $(u,v)$，其中 $d$ 表示当前图中 $s$ 到 $u$ 的最短路径长度，路径长度定义为其上的结点数量。 $n\le 12$，$m\le 1000$。 **** 直接思路是模拟 BFS，设 $f_{i,s,t}$ 表示目前可以到达点集 $s$，其中距离源点最远的点的距离为 $i$ 且这些点的集合为 $t$ 的最小代价，每一次转移拓展一层，预处理 $c_{s,t}$ 表示最外层从 $s$ 拓展至 $t$ 的最小代价。时间复杂度 $O(4^nn)$，可以通过。 **由于题目只需最优化，我们无需在状态中记录 $t$，只需用 $s$ 进行转移。若此时有非法转移，那么将此类转移提前进行一定不劣。** 时间复杂度 $O(3^nn)$。 **** ### [Minimum Cost Paths P](https://www.luogu.com.cn/paste/tp8hw0m1) 有一个 $n\times m$ 的网格图以及一个长为 $m$ 的序列 $c_{1\sim m}$。该网格图的边集为： - $\forall 1\le i\le n,1\le j<m$，$(i,j)$ 向 $(i,j+1)$ 有一条权值为 $i^2$ 的有向边； - $\forall 1\le i<n,1\le j\le m$，$(i,j)$ 向 $(i+1,j)$ 有一条权值为 $c_j$ 的有向边。接下来 $q$ 次询问从 $(1,1)$ 到 $(x,y)$ 的最短路径长度。 $m,q\le 2\times 10^5$，$n\le 10^9$。 **** **两种边中行内边的形式较简单，故对每一列处理较为方便**。设 $f_{i,j}$ 为到达结点 $(j,i)$ 的最短路径长度，转移显然为 $f_{i,j}=\min(f_{i-1,j}+j^2,f_{i,j-1}+c_i)$，**不难归纳证明 $f_{i,*}$ 是下凸的，于是存在一个 $p_i$ 满足 $j\le p_i$ 时进行第一种转移，否则进行第二种转移**。考虑进行完一次转移的结果，一段后缀的值为一个一次函数，不难发现对于 $f_{i,j}$，我们可以划分出若干段 $(l,r,v_0,k,t)$，满足 $\forall j\in[l,r],f_{i,j}=v_0+(j-l)\cdot k+(i-t)\cdot j^2$。使用栈维护之，进行一列的转移时弹出末尾若干段，进行一次二分即可求出新的断点。时间复杂度 $O((m+q)\log n)$。 **** ### [Fruits](https://www.luogu.com.cn/problem/P11331) 给你两个长为 $n$ 的序列 $a_{1\sim n},w_{1\sim n}$，其中 $a_{1\sim n}$ 为一个残缺的排列，$w_{1\sim n}$ 为单调不降序列。对于序列 $b_{1\sim k}$ 定义 $f(b_{1\sim k})$ 为 $b_{1\sim k}$ 中每个前缀最大值 $c$ 的 $w_c$ 之和。对于 $\forall k\in[1,n]$，求出将 $a_{1\sim n}$ 补为完整排列后 $f(a_{1\sim k})$ 的最大值。 $n\le 4\times 10^5$。 **** 朴素想法是设 $f_{i,j}$ 表示前缀 $i$ 的最大值为 $j$ 的答案，但其中有一些状态非法，难以进一步优化。合法状态有两种，一种为前缀 $i$ 已确定部分的最大值，另一种为未确定的数，其有一个下界。 **将两类合法状态分离以研究性质**。设 $f_{i,j}$ 表示前缀 $i$，当前最大值为未确定位置的数中第 $j$ 小的数时的答案，$g_i$ 表示前缀 $i$，当前最大值为前缀 $i$ 已确定部分的最大值时的答案。注意到 $f_{i,*}$ 的合法部分是单调不降的，可以导出一个 $O(n^2)$ 的做法。一次转移为 $f_{i,j}\gets \max(g_{i-1},f_{i-1,j-1})+w_{j}$，又因 $f_{i,*}-w_{*}$ 同样单调不降，故维护 $f_{i,j}'=f_{i,j}-w_j$，一次转移为 $f_{i,j}'\gets f_{i-1,j-1}'+w_{j-1}$，再将一个前缀推平为 $g_{i-1}$。需要查询前后端当前值，使用双端队列维护颜色段，打上时间戳标记。推平前缀需要在一段内二分出推平位置，时间复杂度 $O(n\log n)$。 **** ### [Emiya 家明天的饭](https://www.luogu.com.cn/problem/P10242) 有 $n$ 位顾客与 $m$ 道菜品，其中第 $i$ 位顾客对第 $j$ 道菜的满意程度为 $a_{i,j}$，保证 $a_{i,j}\ge -1$。如果上菜集合为 $S$，则对于一个顾客 $i$： - 若 $\exist j\in S$ 且 $a_{i,j}=-1$，则顾客 $i$ 将会离场； - 否则会对 $\forall j\in S$ 产生 $a_{i,j}$ 的满意值。现在你需要选择若干道菜，使得获得的满意值之和最大。 $n\le 20$，$m\le 10^6$。 **** 由于顾客数量远小于菜品数量，我们对顾客集合进行考察。由于满意值非负，若我们固定剩余的顾客集合 $S$，那么一定选中所有不会让 $S$ 内顾客离场的菜品。令 $T_j$ 表示不排斥第 $j$ 道菜品的顾客集合，那么此时的答案 $f_s$ 为： $$\sum_{T_j⊇S}\sum_{i\in S}a_{i,j}$$ 直接枚举每个顾客 $i$，做高维后缀和达到 $O(2^nn^2)$ 的复杂度，不够优秀。集合的包含、并集等条件引出一类做法，考虑设计一辅助状态 $g_s$ 满足： $$f_s=\sum_{T⊇S} g_t$$ 仅考虑一道菜品 $j$，我们希望构造出 $g_t$ 满足其高维后缀和为 $f_s=[S\sube T_j]\sum_{i\in S}a_{i,j}$，那么我们对希望得到的 $f_s$ 数组进行高维后缀差分即可得到需要构造的 $g_t$。对于任意一位顾客 $\forall i\in T_j$： - 将 $g_{t_j}$ 加上 $a_{i,j}$； - 将 $g_{t_j-\{i\}}$ 减去 $a_{i,j}$。最后只需做一次高维后缀和，时间复杂度 $O(2^nn+nm)$。 **** ### [[2023 NOI模拟 Day22] cut](http://192.168.102.138/JudgeOnline/problem.php?cid=1984&pid=2) 数轴上有 $n$ 个点，点 $i$ 与点 $i+1$ 之间的距离为 $a_i$，初始位于点 $k$。每个点上有一株草，每个时刻草会长高一单位，当你走到点 $p$ 时可以令点 $p$ 的草停止生长。你一个时刻可以走一单位长度，求出最优策略下让所有草停止生长后，它们的高度之和的最小值。 $n\le 10^6$。 **** 状态不可记录时间，故需要**贡献提前计算**。设 $f_{l,r,0/1}$ 表示已经处理完区间 $[l,r]$，现在在 $l$ 或 $r$ 的最小代价，则转移时加上路径长度乘以剩余点数。 **由于贡献提前计算需要知道两侧的剩余点数，必然需要记录两维的信息，考虑只用当前一侧的剩余点数计算贡献**。考虑一株草 $p$ 的最终高度，除了必须经过的 $\text{dis}(p,k)$ 外，在走到点 $p$ 之前每一次向右走长度 $d$ 都会将草 $p$ 的高度加上 $2d$，令 $f_i(i\le k),g_i(i\ge k)$ 分别表示已经处理完了点 $i$ 与点 $k$ 之间的点与另一侧的一部分点的最小额外贡献，得到转移： $$g_i\gets \min_{j\le k}f_j+2(s_i-s_j)\cdot(j-1)$$ $$f_i\gets \min_{j\ge k}g_j+2(s_j-s_i)\cdot(n-j)$$ 其正确性不难归纳证明，并且 $f_i,g_i$ 分别单调，故可以使用双端队列维护凸包求解。由于转移成环，我们考虑模拟最短路，每次取出值最小的状态进行转移，不难发现由于单调性，已取出部分形成一个包含 $k$ 的区间 $[l,r]$，每次判断 $f_{l-1},g_{r+1}$ 的大小关系移动端点即可。时间复杂度 $O(n)$。 **** ### [[2023 NOI模拟 Day28] 零一串](http://192.168.102.138/JudgeOnline/problem.php?cid=1990&pid=1) 给你两个长为 $n$ 的 `01` 串 $s_{1\sim n},t_{1\sim n}$ 以及三个常数 $w_{0,1,2}$。你需要将 $s$ 变成 $t$，为此你可执行任意次下列操作： - 选择 $s_p=0$，花费 $w_{0}$ 的代价令 $s_p\gets 1$。 - 选择 $s_p=1$，花费 $w_{1}$ 的代价令 $s_p\gets 0$。 - 选择 $1\le p<n$，花费 $w_{2}$ 的代价交换 $s_p,s_{p+1}$。求代价的最小值。 $n\le 4\times 10^6$。 **** 若先执行操作 $0,1$，那么此后的花费由经典结论即为 $$\sum_{p=1}^n\left|\sum_{i=1}^p(s_i'-t_i)\right|$$ 直接维护时间复杂度 $O(n\log n)$。考虑**研究最优方案的性质**，首先显然我们不会交换两个相等的数，由此可以导出不会依次对同一个位置进行修改操作与交换操作，反之亦然。那么我们设 $f_i$ 表示前缀 $i$ 修改完毕的最小代价，那么有三种转移，分别为不操作 $i$；修改 $i$；交换 $i$。我们只需解决第三种转移，那么只需要找到最近的 $j$ 使得 $\sum_{p=j+1}^i(s_p-t_p)=0$，从 $f_j$ 转移至 $f_i$。而由于 $j$ 为最近的满足要求的位置，那么区间中 $s_p-t_p$ 的前缀和均同号，可以直接前缀和解决这段区间的贡献。时间复杂度 $O(n)$。 **** ### [[2025 省选模拟 Day2] 异或](http://192.168.102.138/JudgeOnline/problem.php?cid=2217&pid=2) 给你一颗 $n$ 个点的带边权的树，你需要进行若干次操作，每次操作你可以任意指定两个不同的点 $u,v$，添加一条连接 $u,v$ 的，边权为原来 $u,v$ 之间路径上边权的异或和的边，再断开此时图中任意一条边使得其保持为树。对于 $k\in[0,n]$ 求出进行恰好 $k$ 次操作得到的所有树中，边权之和的最小值。 $n\le 10^5$。 **** 不难发现无论如何操作，对于一对点对 $u,v$，它们之间树上路径的边权异或和始终保持不变。于是我们指定一个根，求出初始的树中所有点与根之间的边权异或和 $a_i$，连出完全图 $(i,j,a_i\oplus a_j)$，使用 Brouvka 算法求出其最小生成树，那么操作中添加的边只可能是这颗最小生成树内的边。将原树记作 $T_1$，完全图最小生成树记作 $T_2$。现在的问题为对所有 $k$ 求出使用 $T_1$ 中的边和至多 $k$ 条 $T_2$ 中的边能得到的最小生成树边权和。如果只需要求单个 $k$ 的答案，我们可以使用 wqs 二分，那么要求出 $k\in[0,n]$ 的答案不妨考虑**整体 wqs 二分**。考虑函数 $\text{solve}(l,r,L,R)$ 表示切到 $k\in[l,r]$ 的斜率在区间 $[L,R]$ 中，我们求出斜率为 $[L,R]$ 中点时切到的点 $x$，考虑此时求出的最小生成树，其中的 $T_1$ 中的边在左半区间一定同样被加入。类似的，其中 $T_2$ 中的边在右半区间一定也被加入。那么我们依此将边划分至左右区间，使用可撤销并查集处理一定被加入的边。注意处理共线情况。每条边只会单侧递归，故时间复杂度 $O(n\log n\log v)$。 **** ### [Just Long Neckties 2](https://www.luogu.com.cn/problem/P11665) 给你一个长为 $n$ 的序列 $a_{1\sim n}$，称 $a_{1\sim n}$ 的一个合法子序列为满足「不存在相邻两个位置都不属于该子序列」的子序列。请找到最小的正整数 $k$ 满足存在一个 $a_{1\sim n}$ 的合法子序列 $b_{1\sim m}$ 使得可以将 $b_{1\sim m}$ 划分为不超过 $k$ 个不下降子序列。 $n\le 5\times 10^6$，$a_i\le 21$。 **** 由于是不下降子序列，故我们可以状压是否存在一个子序列结尾为 $x$。有一个朴素的 DP 即设 $f_{i,s}$ 为是否可能选择 $i$，状态为 $s$。注意到**这是一个可行性 DP，考虑交换值域与定义域**。设 $f_s$ 表示状态为 $s$ 时最长的可行前缀长度，我们向后找到第一对数 $a_p,a_{p+1}$ 均不在 $s$ 中，此时状态必须发生变化，分别转移至加入 $a_p$ 和加入 $a_{p+1}$ 的状态即可。现在的问题为如何求出最近的位置 $p$。注意如果能按 $f_s$ 升序的顺序枚举 $s$ 就能直接维护指针进行线性的扫描了，不妨考虑建出转移图，进行类似拓扑排序的过程。转移边数很多，不可直接建图，不妨考虑前缀和优化建图，只需要将每个 $s$ 连向将 $s$ 中某一个 $1$ 后移一维得到的状态即可。时间复杂度 $O(n+2^vv^2)$。 **** ### [Lasers 2](https://www.luogu.com.cn/problem/P12196) 有一个长为 $n$ 的木板，其上有 $m$ 块固定的小木块，其中第 $i$ 块小木块初始覆盖了位置 $[l_i,r_i]$。每块小木块有权值 $w_i$，你可以选择一些权值和不超过 $k$ 的小木块使其不再固定，不再固定的小木块可在木板上任意滑动。一个位置可被多块小木块覆盖。求出最优方案下木板不被任何木块覆盖的长度的最大值。 $n,m\le 2000$。 **** 由于选择的木块可以放在最长的木块上，所以只需要最小化不被选择的木块的并集大小。注意如果最长的木块被选择，仍需要考虑其位置。 **对区间并集进行 DP 只需考虑并集中每一段连续区间**，设最终的并集为区间 $[l_1,r_1],\dots,[l_c,r_c]$，则需要满足： - 不被任意一个区间包含的木块必须被选择，也就是说每一段的内部木块权值和之和不小于 $\sum w_i-k$。 - 最长区间要不短于 $x=\max r_i-l_i+1$，否则最长木块无法放置。设计状态 $f_{i,j,0/1}$ 表示考虑了前 $i$ 个位置，当前并集大小为 $j$，是否有一段连续区间达到最长木块长度。转移为： - 不选择 $i+1$，$f_{i,j,c}\to f_{i+1,j,c}$； - 选择 $i+1$，枚举右端点 $p$，$f_{i,j,c}+w(i+1,p)\to f_{p,j+p-i,c\text{ or }(p-i\ge x)}$。 **考虑优化，注意到两维转移复杂性不同，考虑交换枚举顺序与旋转状态矩阵**。将状态改写为 $f_{i-j,i,0/1}$，此时转移变为： - $f_{i-j,i,c}\to f_{i-j+1,i+1,c}$； - $f_{i-j,i,c}+w(i+1,p)\to f_{i-j,p,c\text{ or }(p-i\ge x)}$。按照第一维顺序转移，线段树优化 DP 即可。时间复杂度 $O(n^2\log n)$。 **** ### [[广东省队集训 2025] 石堆分裂 ](http://8.138.223.198/p/5) 有一堆石子共 $n$ 个，你希望将其变为 $n$ 堆石子各一个。给定常数 $m$，你可以执行若干次操作，每次操作形如： - 记当前有 $k$ 堆大小分别为 $a_{1\sim k}$ 的石子，你可以指定序列 $b_{1\sim k}$ 满足 $\sum_{i=1}^kb_i\le m$，从第 $i$ 堆中取出 $b_i$ 个作为新的一堆石子。求出最少的操作次数。多组数据。 $T\le 10^3$，$m\le n\le 10^9$。 **** 考虑二分答案 $x$。**时光倒流**，建出石子的合并树。该树为一颗二叉树，每个叶子对应一颗石子，且要求每个深度的点的右子树中叶子数量之和 $\le m$。将叶子编码为 $x$ 位二进制数，即要求选出 $n$ 个不同的 $x$ 位二进制数使得每一位上为 $1$ 的数的个数不超过 $m$。 **弱化条件**为所有位上为 $1$ 的数的个数和不超过 $x\cdot m$，可以直接按照 `popcount` 从小向大选。**由于每一位的对称性，任何方案均可调整为满足原限制的方案**。时间复杂度 $O(T\log^2 n)$。 **** ### [[集训队互测 2025] 火花](https://www.luogu.com.cn/problem/P14471) 给定一颗 $n$ 个点的树，给定常数 $k,t$ 与序列 $c_{1\sim n},v_{1\sim n}$，结点 $i$ 上有 $c_i$ 个价值为 $v_i$ 的物品。接下来 A 与 B 先后取物品： - A 可以总共选择不超过 $t$ 个互不相同的结点，对于每个选择的结点，从该结点到根路径上所有结点取走一个物品。 - B 可以总共取走不超过 $k$ 个物品，要求 B 取过物品的结点形成包含根的连通块。最大化 A 与 B 取到的物品的价值总和。 $n,k\le 10^4$，$nk(t+1)\le 10^7$，保证 ${t<\min c_i}$。 **** 先看 $t=0$ 的部分分，这是简单的树形依赖背包模板，使用 DFS 序的解法，在 DFS 序上进行 DP，处理到点 $p$ 时决定取走点 $p$ 中至少一个物品或者跳过 $p$ 的子树，使用单调队列优化即可。记 $s_x$ 表示 $x$ 到根路径上的结点的单价和，表示 A 选择结点 $x$ 的收益。本题主要的难点为 A 在当前处理的结点 $p$ 处取走的物品依赖于子树中选择了多少结点，而我们对 B 进行树形依赖背包时会从浅至深决策。为了解决这个问题，我们**对欧拉序进行 DP**。在进入 $p$ 子树和离开 $p$ 子树时分别进行一部分决策。注意到我们需要两次处理到 $p$ 之间中有多少结点被 A 选择，这**启示我们记录前缀和/后缀和，差分得到所需信息**。不妨使用前缀和，定义状态 $f_{i,j,l}$ 表示处理到欧拉序的第 $i$ 项，前面 B 选择了 $j$ 件物品，A 选择了 $l$ 个结点。具体转移如下，设当前结点为 $p$： - 如果这是 $p$ 初次出现，即进入 $p$ 子树： - 决策 B 是否取走 $p$ 上物品： - 如果取走了，那么限制取走 $[1,l+1]$ 个物品，转移至 $i+1$； - 如果不取走，那么决策子树中 A 取走了多少个结点，显然会取走 $s_x$ 最大的若干个结点，转移至 $i+2\cdot siz_p$； - 如果这是 $p$ 第二次出现，即离开 $p$ 子树： - 决策 A 是否选择结点 $p$： - 如果选择了，那么再允许 B 取走 $[0,c_p-l-1)$ 个物品； - 如果不选择，那么再允许 B 取走 $[0,c_p-l-1]$ 个物品；可以发现，两次允许 B 取走的物品之和为 $c_p$ 减去在 $p$ 子树中 $l$ 的增加量，且由于 $t<c_p$，两次决策都是良定义的。对于跳过子树的部分，记 $g_{p,i}$ 表示 $p$ 子树中 $s_x$ 的前 $i$ 大之和，因为 $g_{p,i}$ 明显是凸的，所以 $f_{i,j,*}$ 与 $g_{p,*}$ 的 $(\max,+)$ 卷积可以通过决策单调性做到 $O(t\log t)\sim O(t)$。总时间复杂度 $O(nkt\log t)\sim O(nkt)$。 **** ### [大鱼吃小鱼](https://www.luogu.com.cn/problem/P14475) 有 $n$ 条体型依次为 $a_{1\sim n}$ 的鱼排成一排，给定非负整数 $k$，对于每个 $i$，要操控鱼 $i$ 吃掉其它所有鱼： - 每次可以选择一条与 $i$ 相邻的鱼，如果鱼 $i$ 此时的体型比这条鱼大了至少 $k$，那么可以直接吃掉这条鱼；否则可以使用一次道具直接吃掉这条鱼； - 鱼 $i$ 的体型会加上被吃掉的鱼的体型； - 求出最少需要使用多少次道具才能吃掉其它所有鱼。 $n\le 5\times 10^6$。 **** 令 $a_0=a_{n+1}=+\infty$。每个时刻鱼 $i$ 的体型都是原先一段包含 $i$ 的区间 $[l,r]$ 的体型之和。以下是一些定义： - 如果区间 $[l,r]$ 之和 $<k$，则区间 $[l,r]$ 为小鱼区间； - 如果区间 $[l,r]$ 之和 $\ge k$，则区间 $[l,r]$ 为大鱼区间； - 如果区间 $[l,r]$ 是大鱼区间，且区间 $[l,r),(l,r]$ 存在小鱼区间，则区间 $[l,r]$ 是极短大鱼区间； - 如果区间 $[l,r]$ 之和小于 $\min(a_{l-1},a_{r+1})+k$，即不使用道具无法拓展，则区间 $[l,r]$ 为自闭大鱼区间。在操作一条鱼 $i$ 时，分为两步： - 不断使用道具拓展区间直到成为一个极短大鱼区间； - 拓展区间直到成为自闭大鱼区间，此时使用道具吃掉两侧较大的一条鱼，重复直到吃掉所有鱼。首先我们说明自闭大鱼区间只有 $\le 2n$ 个。我们称一个自闭大鱼区间关联 $a_{l-1},a_{r+1}$ 中较小的一个点，那么一个点 $p$ 在一个方向上最多只能关联一个自闭大鱼区间： - 若 $[p,r_1],[p,r_2](r_1<r_2)$ 均为自闭大鱼区间，显然有 $a_{r_1+1}+\text{sum}(p,r_1)\ge a_{p-1}+k$，矛盾。接下来考虑自闭大鱼区间之间的关系。 - 如果存在两个自闭大鱼区间 $[l_1,r_1],[l_2,r_2](l_1<l_2<r_1<r_2)$，那么 $[l_2,r_1]$ 一定是小鱼区间，否则讨论 $a_{r_1+1},a_{l_2-1}$ 的大小关系即可导出矛盾。 - 于是对于一个大鱼区间，包含其的自闭大鱼区间必定是层层嵌套的，所以接下来的策略是唯一的。考虑求出所有向右关联的自闭大鱼区间，共有三个条件： - 大鱼区间，即要求 $s_r-s_{l-1}\ge k$； - 向右关联至 $r+1$，即要求 $a_{l-1}\ge a_{r+1}$； - 自闭，即要求 $s_r-s_{l-1}<a_{r+1}+k$。在满足大鱼区间的条件下，找到其中最后一个 $l$ 使得 $a_{l-1}>a_{r+1}$，只需要检查 $[l,r]$ 是否自闭，否则区间和就会超过 $a_{r+1}+k$，不再自闭。所以可以在双指针满足大鱼区间的过程中维护一个后缀最大值单调栈，考虑找到 $l$： - 直接弹出栈中所有 $\le a_{r+1}$ 的元素即可，假设这些元素之后依旧有用，那么一定有 $a_{r'+1}\le a_{r+1}$，此时拼上以 $r$ 为右端点的极短大鱼区间即可吃掉 $a_{r'+1}$，矛盾。接下来要对每个自闭大鱼区间求出答案，这需要求出覆盖其的最短自闭大鱼区间。按 $l$ 为第一关键词正序排序，$r$ 为第二关键词倒序排序后，可以直接维护 $r$ 的后缀最大值单调栈，实际效果为维护嵌套树的极右链。再根据 $a_{l-1},a_{r+1}$ 的大小关系，求出其祖先中第一个左端点 $<l$ 的或第一个右端点 $>r$ 的即可。接下来要对每个极短大鱼区间求出覆盖其的最短自闭大鱼区间，同样做双指针，移动左端点时加入该左端点的自闭大鱼区间，移动右端点时移除该右端点的自闭大鱼区间，由于区间时刻为大鱼区间，故移除的区间均在栈顶，可以简单维护。这样就得到了所有极短大鱼区间的答案，由于极短大鱼区间左右端点均单调，可以直接使用单调队列求出每个 $i$ 的答案。时间复杂度 $O(n)$。 # 图论 ### [Canvas](https://www.luogu.com.cn/problem/P9697) 有一个长度为 $n$ 的序列 $a_{1\sim n}$，初始 $a_i$ 全为 $0$。另外还有 $m$ 个操作，其中第 $i$ 个操作 $(l_i,r_i,x_i,y_i)$ 为 $a_{l_i}\gets x_i,a_{r_i}\gets y_i$，其中 $x_i,y_i\in\{1,2\}$。每个操作必须恰好执行一次。求执行操作的最优顺序，使得所有操作执行完成后，$\sum a_i$ 最大。 $n,m\le 5\times 10^5$。 **** 染色问题，**时光倒流**可以使覆盖、不覆盖互换。将覆盖转为不覆盖。**考虑贪心：一定最先做** $(2,2)$，**最后做** $(1,1)$。对于一个 $(x_i,2,y_i,1)$ 我们连一条 $y_i\to x_i$ 的边，可以发现对于一条链我们可以从左至右操作使得只有链首为 $1$。建完图缩点，只有入度为 $0$ 的强连通分量会出现一个 $1$。需要注意如果该连通块内有点属于某个 $(2,2)$ 的操作可以从该点开始使得不需要出现 $1$。时间复杂度 $O(n+m)$。 **** ### [Balance](https://www.luogu.com.cn/problem/P9731) 给你一个 $n\times m$ 的值域为 $[1,v]$ 的矩阵 $c_{1\sim n,1\sim m}$，保证 $m$ 是 $2$ 的次幂。你可以任意重排每一行。求一种重排方案，使得 $\forall i,j\in[1,n],k\in[1,v]$ 均有 $k$ 在 $c_{*,i}$ 中的出现次数与在 $c_{*,j}$ 中的出现次数之差不超过 $1$。 $n,m,v\le 10^5$，$nm\le 10^5$。 **** 不妨先考虑两列的问题，要求每个数在两列中出现次数差不超过 $1$。考虑刻画成入度出度差小于等于 $1$，同一行两个数连无向边，给图定向使得每个点入度出度差小于等于 $1$。度数为奇数的点向虚拟源点连边，跑**欧拉回路**。列数是 $2$ 的幂，可以考虑**分治**。注意到我们只关注点连的每条边的入度出度，所以左右部分怎样连边都不重要，只需要每个点都连一条边即可。时间复杂度 $O(nm\log m)$。 **** ### [Żarówki](https://www.luogu.com.cn/problem/P10367) 有 $n$ 个灯泡，给定初始状态。有 $m$ 个开关，每个开关控制两个灯泡，按下开关可以使这两个灯泡变为与目前状态相反的状态，只有在两个灯泡有相同状态时才起作用，否则不起作用。你可以随意安排开关的使用顺序和使用次数，问利用这些开关可以到达多少种不同的状态。 $n\le 2\times 10^5$，$m\le 4\times 10^5$。 **** 考虑一个连通块： - **如果它是二分图**，则**将右部点颜色反转**，操作变为选择一个白点一个黑点并交换它们的颜色，容易发现若最开始有 $c$ 个黑点，连通块点数为 $p$，那么这个连通块共有 $\displaystyle\binom{p}{c}$ 种方案； - **如果它不是二分图**，那么考虑**求出一颗生成树**，依旧对偶数深度的点颜色反转。考虑一个奇环的非树边连接了深度奇偶性相同的两个结点，可以任意地增加/减少两个黑点，所以只要求最后连通块内黑点数量奇偶性与初始相同，方案数为 $2^{p-1}$。把所有连通块答案乘起来即可，时间复杂度 $O(n+m)$。 **** ### [地地铁铁](https://www.luogu.com.cn/problem/P8456) 给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 $0$ 或 $1$。定义无序点对 $(x, y)$ 是好的，当且仅当 $x \neq y$ 且 $x, y$ 之间存在同时出现 $0$ 和 $1$ 的简单路径。求出好的点对数量。 $n\le 4\times 10^5$，$m\le 10^6$。 **** 正难则反，求有多少点对之间不存在同时包含 $0,1$ 的路径。显然先建圆方树，点双有如下的性质（默认该点双大小 $\ge 3$）： - 任选两点 $x,y$，有过 $x,y$ 的简单环； - 任选一点 $x$ 与一边 $e$，有过 $x,e$ 的简单环； - 任选两点 $x,y$ 与一边 $e$，有 $x\to y$ 且经过 $e$ 的简单路径。由第三条性质，如果两点间只有全 $0$ 路径（或只有全 $1$ 路径），则必然是这两点在圆方树上经过的所有方点代表的点双内部的边权全为 $0$（或全为 $1$）。这部分贡献可以用并查集简单计算。若两点间同时有全 $0$ 路径和全 $1$ 路径但没有同时包含 $0,1$ 的路径，则它们必然同属于一个点双，且一个点双内最多有一个这种点对，存在这种点对当且仅当点双内恰好有两个点的邻边同时拥有两种颜色。证明较为复杂暂略。时间复杂度 $O(n+m)$。 **** ### [[2023 NOI模拟 Day12] 尼伯龙根的思维题](http://192.168.102.138/JudgeOnline/problem.php?cid=2004&pid=1) 给你一个 $n$ 个点 $m$ 条边带边权的无向图和一个正整数 $t$，问是否有一条从 $1$ 到 $n$ 的路径上的边权和恰好为 $t$。不要求为简单路径。 $n,m\le 10^5$，$w\le 5\times 10^5$，$10^{15}\le t<2^{64}$。 **** 令 $x$ 为所有边权的 $\gcd$，则若 $t\bmod x\ne 0$ 显然无解。否则将所有边权与 $t$ 均除以 $x$，答案不变。考虑从点 $1$ 开始经过每条边至少一次再回到点 $1$，过程中可以在某条边上往返任意次。由于所有边权的 $\gcd$ 为 $1$，则任意足够大的偶数均可由这些边往返走得到。其中偶数是因为每条边每次往返都会增加两倍边权，而足够大只需要达到 $w^2$ 则必然能表示出。这个下界可以考虑建出**同余最短路**的图，由于只有 $w$ 个点，所以到每个点的最短路必然不超过 $w^2$。由于此处 $t$ 足够大，所以只需要判断从 $1$ 到 $n$ 有没有与路径的边权和与 $t$ 奇偶性相同即可。时间复杂度 $O(n+m)$。 **** ### [[2024 省选模拟 Day22] 魔法](http://192.168.102.138/JudgeOnline/problem.php?cid=2151&pid=1) 有一张 $n\times m$ 的空画布，初始所有格子都是白色的。有黑白两种颜料，你可以对它进行若干次操作，要求绘制出给定的画。你可以执行的操作操作为： - 选取画布中一块 $1\times x$ 或 $x\times 1$ 的矩形区域，将其染为黑色或白色，代价为 $Ax+B$； - 选取画布中一块 $1\times 1$ 的区域，将其染为黑色或白色，代价为 $C$。其中 $A,B,C$ 为给定的常数。对一个格子进行多次染色会将该格染为最后一次染的颜色。此外还有两条限制： - 不允许对一个被染过白色的格子染黑色； - 不允许对一个格子进行超过 $2$ 次染色。请求出最小代价。 $n,m\le 40$，$C\le A+B$，$T\le 6$。 **** 第一种操作中行列染色的区域分别是不交的，考虑到限制条件一则染色顺序可以划为三步：先用操作一染若干黑色区域、再染若干白色区域、再使用操作二进行调整不劣。考虑最小割。**最小割可以用于解决给定若干 0/1 变量 $\bm{x_i}$，求 $\bm{\min\sum_i[x_{a_i}=1][x_{b_i}=0]w_i}$ 的问题**，其中要求 $w_i\ge 0$，将布尔变量为 $1$ 视作割给 $S$，为 $0$ 为割给 $T$，连边 $a_i\to b_i$，流量为 $w_i$ 即可。本题中，设 $a_{i,j},b_{i,j},c_{i,j},d_{i,j}$ 分别表示 $(i,j)$ 这个格子在「第一步被行操作染黑」/「第二步被行操作染白」/「第一步被列操作染黑」/「第二步被列操作染白」。拆一下代价： - 前两步的代价：对于 $a$ 有 $[a_{i,j}=1]A+[a_{i,j}=1][a_{i,j+1}=0]B$，$b,c,d$ 同理； - 第三步的代价： - 如果 $(i,j)$ 要求为黑色，则不能被染过白色：$[b_{i,j}=1]\infty+[d_{i,j}=1]\infty$；如果没有被染过色还需要在第三步染一下：$[a_{i,j}=0][c_{i,j}=0]C$。 - 如果 $(i,j)$ 要求为白色，则不能被染两次黑色：$[a_{i,j}=1][c_{i,j}=1]\infty$；如果被染过一次黑色且没染过白色还需要在第三步染一下：$[a_{i,j}=1][d_{i,j}=0]C+[b_{i,j}=0][c_{i,j}=1]C$。将 $b,c$ 取反即可化为上述形式，可以最小割。 **** ### [[2023 NOI模拟 Day13] 激光塔](http://192.168.102.138/JudgeOnline/problem.php?cid=2005&pid=1) 有 $n$ 个激光塔，每个塔有一个面对的方向（上下左右之一），给定常数 $w_1,w_2$，以某种方式给出 $m$ 条边，每个激光塔初始会贡献 $w_1$，让某一个塔向任意方向旋转 $90°$ 会花费 $w_1$ 的代价。对于某条边，如果这条边连接的两个塔方向相同则会有 $w_2$ 的贡献，如果它们方向相反则会有 $w_2$ 的代价。求出贡献和减代价和的最大值。 $n\le 50$。 **** 上左下右相邻两个方向间旋转均需要恰好一次，将它们分别编号为 $0,1,3,2$ 后可以用异或刻画旋转次数。同时注意到边给的贡献与旋转的代价是高度对称的，也可以用异或来刻画。于是我们拆变量 $a_i,b_i$ 表示塔 $i$ 状态的两位分别是什么即可。 **** ### [[2023 NOI模拟 Day13] 地理微米](http://192.168.102.138/JudgeOnline/problem.php?cid=2005&pid=0) 有一个 $n\times m$ 的网格，有若干位置有标记，你需要用若干 L 字型的纸片覆盖网格，使得每个有标记的位置恰好被一个 L 字型的纸片的中心覆盖，每一个标记与一个纸片一一对应。纸片不允许重叠，可能存在不被任意纸片覆盖的位置。求放纸片的方案数，对 $998244353$ 取模。 $\sum nm\le 3\times 10^6$。 **** 每一个标记的上下两个位置必定覆盖一个，左右两个位置必定覆盖一个。在这些点之间连一条边，问题变为**给形成的图定向使得每个点入度不超过 $\bm 1$**。如果左右两个位置有一个不能选则直接在另一个位置连一个自环，若两个都不能选则无解。对于每个连通块，若边数大于点数则必然无解，否则 - 如果是树，可以以任意位置为根定为外向树，方案数为点数； - 如果是树带一个自环，只能以自环的点为根定为外向树，方案数为 $1$； - 如果是基环树，环上有 $2$ 种方案，每颗树只能从环上的点为根定为外向树，方案数为 $2$。并查集即可，时间复杂度 $O(nm)$。 **** ### [[2024 联考 III Day1] 水管工](http://192.168.102.138/JudgeOnline/problem.php?cid=2191&pid=1) 有一个 $n\times m$ 的网格图，每一个格子可以放下一个水管。水管共有六种，形态分别为「与周围 $0$ 个格子相连」/「与周围 $1$ 个格子相连」/「与周围相对的 $2$ 个格子相连」/「与周围相邻的 $2$ 个格子相连」/「与周围 $3$ 个格子相连」/「与周围 $4$ 个格子相连」。称其中「与周围相邻的 $2$ 个格子相连」的水管为高级水管。称一个局面是合法的当且仅当所有水管间连接均为双向连接。现在网格图内已经放置了一些高级水管，你需要在其中再放置若干高级水管使得可以再向局面中添加若干任意水管使得局面合法。此外，网格图上还有两种特殊格子，分别要求你「必须在此放置一个高级水管」/「不能在此放置高级水管」。注意这些特殊格子只限制你的放置过程，放完后添加水管使局面合法的过程允许在第二种特殊格子放置高级水管。求出你放置的高级水管数量的最大值或报告无解。 $n,m\le 100$。 **** 注意到只要你放完后不是已经不合法（有水管指向墙或者此方向无接口的水管）就能补为合法状态，所以只关注我们放的过程即可。不妨关注网格每条边的状态，其中边指的是所有相邻两个网格的公共边，边的状态指的是与该边相邻的两个网格之间是否相连。一个格子是高级水管当且仅当该格子相对的两组边均恰有一边为 $1$。称这种格子为好格子。给定的初始局面即强制要求了若干边的状态。只考虑一行中相邻两个确定状态的边之间的格子，强制好格子要求相邻两边不同，强制坏格子要求相邻两边相同。如果除开强制坏格子外所有格子不能均为好格子则必须选出一个为坏格子。那么称「一段中除开限制格需要有一个坏格子」为一个行限制，同理有列限制。如果一个行限制和一个列限制相交且交点格非限制格，那么选交点格可以同时满足两个限制。将它们连边，零度点向虚拟源汇连边，则需要求二分图最小边覆盖，网络流即可。 **** ### [Tuple+](https://www.luogu.com.cn/problem/P10998) 给出 $m$ 个互不相同的无序三元组 $(u,v,w)$，求有多少无序四元组 $(a,b,c,d)$ 使得三元组 $(a,b,c),(a,b,d),(a,c,d),(b,c,d)$ 均存在。 $m\le 2\times 10^6$。 **** 限制为三元组，相对难以处理，我们考虑**强制满足一维的限制以化为二维的问题**。假如枚举 $a$，则对于所有的三元组 $(a,x,y)$，我们在 $x,y$ 间连边，枚举建出的图上的所有三元环并检查这三点是否包含在同一三元组内即可。时间复杂度 $O(m^{3/2})$。考虑类似三元环计数的优化：我们令 $\text{deg}(i)$ 表示包含 $i$ 的三元组数量，则我们将每个三元组内部重排使得其 $\text{deg}(u)\le \text{deg}(v)\le \text{deg}(w)$，其中度数相同的比较编号。根据[分析](https://www.luogu.com.cn/article/flblcgsu)，将三元组重排后使用上述算法时间复杂度降为 $O(m^{4/3})$。 **** ### [Game King](https://www.luogu.com.cn/problem/P11073) 给你一张有向图，求有多少个点 $x$ 满足对于 $\forall y\in[1,n]$ 均有 $x$ 可到达 $y$ 或 $y$ 可到达 $x$。 $n\le 10^6$，$m\le 3\times 10^6$。 **** 先缩点，DAG 问题不妨使用拓扑序，则只需求哪些点可以到达所有拓扑序大于它的点且能被所有拓扑序小于它的点到达，两个限制是对称的，只需要考虑一边。判断一个点 $x$ 能否到达所有拓扑序大于它的点，判定性问题的思路为**先列出必要条件**：不能有除了 $x$ 的入度为 $0$ 的点；**再证明其为充分条件**：每个点不断跳入边必定走到入度为 $0$ 的点即 $x$ 本身。 Tarjan 的过程中已经求出了拓扑序，直接维护即可。时间复杂度 $O(n+m)$。 **** ### [Travelling Merchant](https://www.luogu.com.cn/problem/P7831) 给你一张 $n$ 个点 $m$ 条边的有向图，其中每条边上有两个参数 $r,p$，分别表示只有当你的资产不少于 $r$ 元才可以通过这条边、通过这条边后你的资产会增加 $p$ 元。对每个点 $x$ 求出最小的初始资产数量使得可以从 $x$ 开始无限游走。 $n,m\le 2\times 10^5$。 **** 一个朴素算法为，从点 $i$ 开始不断增加初始预算以到达一个新点。由于图并没有较好的性质，该做法难以优化。考虑拓扑排序，每次队列为空时从每个点开始必定能走到环中，**考虑此时全局限制最严即 $r$ 最大的边**，如果经过了该边则必定能无限走下去，于是可将该边的入点的答案对该边的 $r$ 取 $\min$ 并删去该边继续求解。 **路径问题中，可将路径按照是否经过了某点或某边分类讨论**。时间复杂度 $O(m\log m)$。 **** ### [[2023 NOI模拟 Day32] 有向图](http://192.168.102.138/JudgeOnline/problem.php?cid=2047&pid=2) 有一个 $n\times m$ 的 01 矩阵 $A_{i,j}$，初始全为 $0$，有 $q$ 次操作，每次操作将一个矩形取反。所有操作后，将根据矩阵 $A$ 生成一张左右部点数分别为 $n,m$ 的有向二分图。当 $A_{i,j}=1$ 时有边 $i\to j$，反之则有边 $i\gets j$。对每个点求出其能到达的点数。 $n,m\le 2\times 10^5$，$q\le 5\times 10^4$。 **** 先考虑「二分完全图」的特殊性质。我们知道竞赛图缩点后形成一条链，考虑二分完全图缩点后形成的图。 **不妨从一些突破口出发描述性质，如拓扑序最小的强连通分量**。如果其不为单点，那么其必然同时包含两部的点。假设有一点 $p$ 无法从该强连通分类出发到达，那么 $p$ 必然指向该分量中所有与 $p$ 异侧的所有点，即 $p$ 所在强连通分量拓扑序更小，不符合假设，故此种情况下此强连通分量必然可到达所有点。否则该强连通分量为单点，令该点为 $q$，找到接下来第一个包含与 $q$ 异侧的点的强连通分量，同上可证 $q$ 可到达所有拓扑序不小于该强连通分量的点。接下来要解决的就是对原图进行优化建图了。对矩形做扫描线，扫到一行 $i$ 时，需要对每个 $A_{i,j}=0$ 要连边 $i\gets j$，对 $A_{i,j}=1$ 要连边 $i\to j$。使用线段树，每个区间维护区间内所有 $0/1$ 位置的入/出树即可。令 $n,m$ 同阶，时间复杂度 $O(n+q\log n)$，有着 $32$ 倍的逆天常数。 **** ### [Strange Train Game](https://www.luogu.com.cn/problem/P11146) 给你两个长为 $n$ 的 01 序列 $a_{1\sim n},b_{1\sim n}$ 以及 $m$ 个区间 $[l_i,r_i]$，你可以对每个区间选择是否操作，若选择操作 $[l_i,r_i]$，那么将执行 $\forall p\in[l_i,r_i]$，交换 $a_p,b_p$。最大化最终序列 $a$ 的字典序。 $n,m\le 2\times 10^5$。 **** 先将 $a_p=b_p$ 的位置删去。形如区间异或问题，考虑图论建模：**在 $\bm{l_i}$ 与 $\bm{r_i+1}$ 之间连边，那么可取反一个区间 $\bm{[l,r]}$ 当且仅当 $\bm l$ 与 $\bm{r+1}$ 连通**。从左至右确定每一位，如果这一位再操作一次更优，那么找到最大的 $r$ 使得 $[i,r]$ 可操作，操作 $[i,r]$ 即可。不难证明其正确性。时间复杂度 $O(n+m)$。 **** ### [[省选联考 2021] 图函数](https://www.luogu.com.cn/problem/P7516) 给你一张 $n$ 个点 $m$ 条边的有向图 $G$，定义函数 $f(u, G)$： 1. 初始化返回值 $cnt = 0$，图 $G' = G$。 2. 从 $1$ 至 $n$ 按顺序枚举结点 $v$，如果当前的图 $G'$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径均存在，则令 $cnt\gets cnt + 1$，并在图 $G'$ 中删去结点 $v$。 3. 第 $2$ 步结束后，返回值 $cnt$ 即为函数值。现在给定一张有向图 $G$，请你求出 $h(G) = f(1, G) + f(2, G) + \cdots + f(n, G)$ 的值。更进一步地，记删除编号不超过 $i$ 的边后的图为 $G_i$，请你对 $\forall 1\le i\le m$ 求出 $h(G_i)$ 的值。 $n\le 10^3$，$m\le 2\times 10^5$。 **** 首先拆开贡献，对于 $1\le i\le j\le n,1\le k\le m$，点 $i$ 在 $f(j,G_k)$ 中做出贡献当且仅当由 $i$ 至 $j$、由 $j$ 至 $i$ 均存在只经过编号在 $[i,n]$ 内的点、编号在 $[k,m]$ 中的边。 **点的限制提示使用 Floyed**，设 $f_{i,j}$ 表示由 $i$ 至 $j$ 的路径中，只经过编号在 $[\min(i,j),n]$ 中的点，所有路径编号最小值的最大值。从大到小枚举中转点进行转移即可，时间复杂度 $O(n^3+m)$，难以通过。动态加边，维护 $f_{i,j}$ 表示此时是否存在 $i$ 至 $j$ 的只经过编号在 $[i,n]$ 中的点的路径，$g_{i,j}$ 表示此时的反图上是否存在这种路径。那么此时的答案就是 $\sum_{i}\sum_{j\ge i}[f_{i,j}=g_{i,j}=1]$，这个形式不妨考虑 bitset 优化。加入一条边 $(u,v)$ 时，当 $f_{i,u}=1$ 且 $f_{i,v}=0$ 时 $f_{i,*}$ 会发生变化。从结点 $v$ 开始 DFS，只搜索 $f_{i,x}=0$ 且 $x\ge i$ 的结点，令 $f_{i,x}\gets 1$，反图同理。只需要求**在搜索过程中要求搜到的点 $x$ 均满足 $f_{i,x}=0$**，那么每一次搜索均会将一个 $0$ 标为 $1$，时间复杂度便有了保证。维护每行每列的 biset 即可。统计答案只需在修改时增量。时间复杂度 $O(\dfrac{n^3+nm}{\omega})$，可以通过。 **** ### [[2023 NOI模拟 Day22] lis](http://192.168.102.138/JudgeOnline/problem.php?cid=1984&pid=1) 给你一个长为 $n$ 的序列 $a_{1\sim n}$，选出其最长的一个子序列 $b_{1\sim k}$ 使得 $a_{1\sim n}$ 的最长上升子序列长度大于 $b_{1\sim k}$ 的，求出最大的 $k$。 $n\le 10^6$。 **** 求出 $f_i$ 表示以 $i$ 结尾的最长上升子序列，那么如果 $f_i$ 可以转移至 $f_j$，连边 $i\to j$，则我们要选择最少的点使得所有最长路径上均存在选择的点，可以建图跑最小割。时间复杂度 $O(n^2)$，无法通过。考虑图的特殊形态，发现图本身即为分层图，即只会增广一次，且并不需要考虑退流，考虑**模拟最大流 DFS 的过程**，可以使用线段树隐式优化建图。时间复杂度 $O(n\log^2n)$，无法通过。注意到一层内的点的点权不递增，考虑把相邻两层的点分别拉出来，层 $d$ 的每个点 $p$ 向层 $d+1$ 的一个区间 $[l_p,r_p]$ 内的点连边，且 $l_p,r_p$ 分别递增，增广时直接从区间内最小的未遍历过的点开始即可。每个点只会遍历一次，复杂度正确。时间复杂度 $O(n\log n)$。 **** ### [[2023 NOI模拟 Day44] B](http://192.168.102.138/JudgeOnline/problem.php?cid=2028&pid=1) 给你两个整数 $n,m$，平面上有 $n$ 个点 $(x_{1\sim n},y_{1\sim n})$，求出最小的 $d$ 使得存在 $m$ 个点满足其中任意两个点的距离都不超过 $d$。 $n,m\le 200$。 **** 确认一个 $d$ 是否合法是最大团问题，故难以直接解决。**此类一般图上的 NPC 问题考虑加强限制转化为二分图问题求解。** 枚举选出的点的直径 $(x_p,y_p),(x_q,y_q)$，那么其余选择的点都需要在以它们为圆心，$d=\text{dis}(p,q)$ 为半径的圆内，两个圆会交出一个区域，连接 $PQ$ 将这一区域划分为上下两部分，同一部分内的点距离均 $\le d$，故排斥关系只会在两部分之间。将排斥关系连边，求二分图最大独立集即可。时间复杂度 $O(n^5)$，常数极小，可以通过。 **** ### [Wide Swap](https://www.luogu.com.cn/problem/AT_agc001_f) 给你一个排列 $p_{1\sim n}$，你可以进行任意次以下操作： - 选择 $i,j$ 使得 $|i-j|\ge k$ 且 $|p_i-p_j|=1$，交换 $p_i,p_j$。最小化得到的排列 $p_{1\sim n}'$ 的字典序。 $n\le 5\times 10^5$。 **** **对 $\bm{p_i}$ 的限制较松而对 $\bm i$ 的限制较严，考虑其逆排列 $\bm{q_{1\sim n}}$**，能交换 $q_i,q_j$ 当且仅当 $|i-j|=1$ 且 $|q_i-q_j|\ge k$，我们要依次最小化 $1,2,\dots,n$ 的位置。若 $|q_i-q_j|<k$，那么 $q_i,q_j$ 的相对位置不会改变，可以依此连边构造出一张 DAG。由 [P3243 的结论](https://www.luogu.com.cn/article/tp38r8c9)，所求的答案 $q'$ 为所有可以到达的排列 $q''$ 中反串的字典序最大的。建反图进行拓扑排序，使用数据结构优化之。一个值 $v$ 可以取当且仅当不存在 $p_v<p_x$ 且 $|v-x|\le k$，使用线段树维护 $[l,r]$ 中未取的位置的最大值。**取走一个值 $\bm x$ 后，新的零度点必定与其有直接连边**，只需要考虑 $(x-k,x)$ 以及 $(x,x+k)$ 区间内的最大值即可。时间复杂度 $O(n\log n)$。 **** ### [[2023 NOI模拟 Day38] 求和](http://192.168.102.138/JudgeOnline/problem.php?cid=2022&pid=1) 给你两个长为 $n$ 的序列 $a_{1\sim n},b_{1\sim n}$，你可以选择若干位置 $i$ 并交换 $a_i,b_i$，最大化 $\sum_{i,j}\min(a_i,b_j)$，构造一组方案。 $n\le 2\times 10^5$。 **** 考虑每个数被算入贡献的次数，相当于将从大到小每个数放入两个集合，要求 $a_i,b_i$ 在不同集合。一个数被算入的次数即为加入它时另一个集合内数的数量。将 $a_{1\sim n},b_{1\sim n}$ 拼起来从大到小排序得到序列 $c_{1\sim 2n}$，模拟出一个上界为 $$\sum_{i=1}^{2n}c_i\cdot \left\lfloor\dfrac i 2\right\rfloor$$ 总计算次数和是确定的，而该式中每个前缀的计算次数和均取到最大值，故答案不可能比该式大。考虑取到该上界的条件：$c_{2i-1}$ 要与 $c_{2i}$ 在不同的集合中。将 $a_{1\sim n},b_{1\sim n}$ 离散化为 $2n$ 的排列 $p_{1\sim n},q_{1\sim n}$。**放入不同的集合看作连边，有 $\bm{(p_i,q_i)}$ 以及 $\bm{(2i-1,2i)}$ 两类边，每个点各与两条边相连，将两类边分别称为白边、黑边，那么该图不可能存在奇环，否则必定存在一点拥有两条同颜色邻边。** 故该图为二分图，直接进行二分图染色即可。时间复杂度 $O(n\log n)$。 **** ### [[2025 NOI模拟 Day3] moon](http://192.168.102.138/JudgeOnline/problem.php?cid=2235&pid=0) 给你 $m$ 个 $\{1,2,\dots,n\}$ 的子集 $A_{1\sim m}$，你需要选出两组不交且非空的子集使得它们的并集相同。 $m\le 500$，$n\le m-1$。 **** 建立二分图，$m$ 个左部点分别表示每个集合，$n$ 个右部点分别表示每个元素，按照包含关系连边并求出一组最大匹配。由于 $m>n$，必定存在一个未匹配的左部点 $x$，由该点开始执行增广路算法并染色，若 $x$ 存在一个未访问过的右部点邻居 $t$，则将 $t$ 匹配的左部点 $y$ 标记为与 $x$ 相反的颜色并继续搜索 $y$。由于求出了一组最大匹配，故访问到的右部点 $t$ 一定已匹配，且由于每个左部点只匹配一个右部点故不会重复染色。算法结束后，每个被访问到的右部点均与至少一个黑白二色的左部点相邻，故我们求出了一组合法解。时间复杂度视匹配算法为 $O(n^3)$ 或 $O(n^{2.5})$ 等。 **** # 数据结构 ### [Dinosaur Bones Digging](https://qoj.ac/contest/1475/problem/8006) 给你一个长为 $n$ 的序列 $a$，给出 $q$ 次询问 $[l_i,r_i]$，求 $\displaystyle\max_{i=1}^q\max_{j=l_i}^{r_i}a_j\cdot\left(\sum_{k=l_i}^{r_i}[a_k>a_j]\right)$。 $n,q\le 10^6$。 **** 对所有询问答案求最大值，那么**被包含的询问不可能贡献答案**，去除掉被包含的询问后把询问按左端点排序，此时 $l,r$ 均递增，即一个 $i$ 只会被一段连续的询问包含。为了处理大于关系，考虑**按值域从大到小扫描线**，区间加区间求 $\max$ 即可。时间复杂度 $O((n+q)\log n)$。 **** ### [山路长环 / ring](https://www.luogu.com.cn/problem/P9546) 两人在玩一个游戏。在他们面前有一个棋盘，棋盘是一个由 $n$ 个节点和 $n$ 条边构成的环，边有边权。初始时，一枚棋子被放置在某个节点上。两人轮流移动棋子，无法移动者败。每次移动时，必须选择棋子当前所在节点的某个相邻点（即有边相连的点），沿着边将棋子移动到这个相邻点去，并将边权减少任意正整数。需要注意的是，边权不允许被减小到负数。定义一个长为 $k$ 的序列 $v_{1\sim k}$ 的权值为，如果棋盘上共 $k$ 个节点，且边权以顺时针方向分别为 $v_1,v_2,\dots,v_k$，那么这样一盘游戏共有多少个不同的初始棋子位置可以让先手有必胜策略。现在给你一个长为 $m$ 的序列 $a_{1\sim m}$，接下来 $q$ 次操作。每次操作形式为如下之一： - `1 x y` 表示将 $a_x$ 赋值为 $y$； - `2 l r` 表示查询 $a_{l\sim r}$ 的权值。 $m,q\le 3\times 10^5$。 **** 环上有边权值为 $0$ 时： - 如果现在在 $0$ 权边旁，那么只有一个方向可走，并且必须将这条边权也变为 $0$，否则对手会走回来卡死你； - 那么设一个点到左右的最近的 $0$ 的距离分别是 $p,q$，那么如果 $p,q$ 有一个奇数，直接向那个方向走并把边权变成 $0$ 即可胜利。所以对于一个极长的非 $0$ 段，若其长为奇数则全可胜利，否则有一半的点可以胜利。如果不存在 $0$ 且环长为奇数，则先手直接将一条边变成 $0$，所有点都可以胜利。否则先后手都要避免自己将某条边走成 $0$，我们注意到与 $1$ 权边相邻时也不能向这个方向走了，上述分析仍然适用。所以线段树维护最小值相关信息即可。时间复杂度 $O(q\log m)$。启示是**遇见特殊的 $0$ 考虑拓展到最小值**。 **** ### [验题](https://loj.ac/p/511) 给你一颗大小为 $n$ 的树和它的一个独立集 $I$，你需要求出字典序比 $I$ 恰好大 $k$ 的独立集。 $n\le 10^6$，$k\le 10^{18}$。 **** **字典序问题考虑逐位确定**。可以按照与给定独立集的最长公共前缀分类。限制排序后的一个前缀即要求必须包含这些前缀内的数，不能包含小于等于这个前缀最大值且没在这个前缀中出现过的数。要求某些点一定选中，某些点一定不选中，这是平凡的 DDP 问题。使用 LCT 或树剖维护，时间复杂度 $O(n\log n)$ 或 $O(n\log^2n)$。 **** ### [[广东省队集训 2024] 写作]() 给你一颗满足每个点儿子个数不超过 $d$ 的树和一个排列 $p$，定义一个排列是合法的当且仅当每个子树内的点在 $p$ 中的出现位置都是连续的一个区间。你可以任意次交换 $p$ 的相邻两项，求最少的操作次数 $k$ 使得 $p$ 合法并求出操作 $k$ 次后能得到多少种不同的合法排列，对 $998244353$ 取模。 $n\le 5\times 10^4$，$d\le 10$。 **** **最小邻项交换次数，考虑逆序对**。从深往浅合并，注意到一个子树内的点在最终排列中的顺序与子树外无关，所以 $k$ 即为把每个点自身和它的每个子树合并起来的最小代价加起来，而方案数则为把所有对应方案数乘起来。把一个子树放在另一个子树前面的代价是一个类似逆序对数的东西，任意两个子树的代价可以 DSU 求，用迭代分块可以比 BIT 优一点，然后给子树排序直接状压。总复杂度 $O(n\log^2n+nd\log n+n^{4/3}\log n+n2^{d+1})$。 **** ### [[2024 联考 II Day4] C](http://192.168.102.138/JudgeOnline/problem.php?cid=2178&pid=2) 区间加，求区间笛卡尔树最浅的一层满足该层不满。 $n,q\le 10^5$。 **** 笛卡尔树可以看作是以 $a_i$ 为随机权的 Treap。线段树每个结点维护对应区间的笛卡尔树，答案不超过 $\log n$，深度大于 $\log n$ 的子树可以直接砍掉，容易发现此时合并可均摊。区间加使用标记永久化。区间笛卡尔树可以将区间加极大值求全局此时的笛卡尔树，注意一些 corner case。时间复杂度 $O(n\log^2n)$。 **** ### [[2024 联考 II Day6] 合并书籍](http://192.168.102.138/JudgeOnline/problem.php?cid=2185&pid=0) 有 $n$ 堆石子排成一列，个数分别为 $a_{1\dots n}$。在最初选定一堆石子，每次可以将这堆石子与左右某一堆合并，代价为合并后的大小。对于每堆石子求出，如果选择以这堆石子作为初始选择，那么合并完所有石子的最小代价是什么。 $n\le 2\times 10^5$。 **** 发现是个类似 $\max\sum a_ip_i$ 的东西，考虑经典操作**每次取最小值合并**，发现可行。然后移动前缀后缀维护单调栈，一个结点在一段区间内出现，扫描线即可。时间复杂度 $O(n\log n)$。 **** ### [[2024 联考 II Day8] word](http://192.168.102.138/JudgeOnline/problem.php?cid=2184&pid=0) 给定一个长为 $n$ 的字符串，其中只包含前 $k$ 个小写英文字母。同时，再给一个 $k\times k$ 的 01 矩阵 $A$。你可以对字符串进行若干次操作，每次操作选择一对相邻的字符 $u, v$，并且 $u$ 在前 $v$ 在后，$A_{u,v}=1$，删去 $v$。求出经过任意次删字符后，所能得到的字典序最小的串。 $n\le 5\times 10^5$，$k\le 26$。 **** 求最小字典序，尝试**维护哈希**。为了支持删字符，需要考虑倍增。设 $f_{i,j}$ 与 $g_{i,j}$ 表示后缀 $i$ 的答案中第 $2^j+1$ 位的位置与前 $2^j$ 位的哈希值，转移维护单调栈。时间复杂度 $O(n\log n)$。 **** ### [[2024 联考 II Day8] partition](http://192.168.102.138/JudgeOnline/problem.php?cid=2184&pid=1) 给你一个长为 $n$ 的排列，将其分为两个子序列 $a,b$，求出 $a$ 中前缀最大值数量与 $b$ 中前缀最小值数量的和的最大值。 $n\le 2\times 10^5$。 **** 考虑**枚举分界点** $i$，则满足对于任何的 $k<j\le i$，若 $p_j>p_k$，则 $p_k$ 在序列 $a$，否则在序列 $b$。令 $pr_i$ 和 $sf_i$ 分别表示 $[1,i)$ 中 $p_i$ 的前驱、后继，则我们发现 $i$ 之前的部分的答案就为有多少个 $[pr_j,sf_j]$ 包含 $p_i$。后面部分的答案是一个类似 LIS 或者 LDS 的东西，分类讨论一下即可。时间复杂度 $O(n\log n)$。 **** ### [[2023 NOI模拟 Day6] 色彩](http://192.168.102.138/JudgeOnline/problem.php?cid=1998&pid=1) 给你一颗 $n$ 个点的树，点带颜色，$q$ 次询问求树链最长同色颜色段。强制在线。 $n\le 2\times10^5$，$q\le 5\times10^6$。 **** 链的情况考虑猫树即二区间合并，而**树上二区间合并即为点分树**。时间复杂度 $O(n\log n+q)$。 **** ### [[2023 NOI模拟 Day12] 公司](http://192.168.102.138/JudgeOnline/problem.php?cid=2004&pid=2) 给你一颗 $n$ 个点的树，每个点有点权 $v_i$ 表示这个结点的员工数。初始老板在点 $1$，现在召集所有人到点 $k\in[1,n]$ 开会，老板的速度为 $1$，员工的速度为 $2$，求有多少员工到达的时间不晚于老板到达的时间。对每个 $k$ 求出该答案。 $n\le 2\times 10^6$。 **** 题意就是对每个 $i$ 求所有满足 $\text{dis}(i,j)\le 2dep_i$ 的 $j$ 的 $v_j$ 之和。直接点分治能做到 $O(n\log n)$。 **与距离和深度有很大关系，不妨考虑长链剖分**。$i,j$ 有祖先后代关系的情况可以用树上差分搞定，接下来需要算 $i,j$ 没有祖先后代关系的贡献。考虑合并若干短链和一条长链，长链对短链的贡献为一段前缀的和，改成全局减后缀。短链对长链的贡献为一段后缀加，在对应位置打标记。注意到此处的“链”并非真正的一条链，而是若干链合并而来，此处打标记后缀加会将所有合并到该节点的点全部都加上该值。于是建出合并树，最后再做一遍树上前缀和。短链与短链之间的贡献已经在上述讨论过程中算入了，注意减去自己到自己的贡献。另外需要注意将一个点 $i$ 合并到点 $j$ 时 $j$ 可能已经含有标记，需要在 $i$ 处减去，需要将长链前「次长链长度」个点的后缀标记加的标记先传下去。精细实现一下，时空复杂度均为 $O(n)$。 **** ### [[2024 联考 III Day1] 交换余生](http://192.168.102.138/JudgeOnline/problem.php?cid=2191&pid=0) 给你一个长为 $n$ 的序列 $a_{1\dots n}$ 和一个常数 $k$，求所有长度 $\ge k$ 的「区间和减去区间内前 $k$ 大之和」的最大值。 $n\le 10^5$，$k\le 100$。 **** 设 $p_{i,j},q_{i,j}$ 分别表示 $i$ 前后第 $j$ 个比 $a_i$ 大的数，可以用链表求出。具体地，类似单调栈，将「存在 $j>i$ 且 $a_j\ge a_i$ 时出栈」改为「存在 $k$ 个 $j>i$ 且 $a_j\ge a_i$ 时从链表中删去」即可。 **枚举区间第 $\bm{k+1}$ 大**，则枚举该数左边有 $i$ 个比它大，区间的左右端点均位于某个区间内，ST 表求出区间中前缀和的最小值或最大值即可。时间复杂度 $O(n\log n+nk)$。 **** ### [[2024 联考 III ACM] Dou](https://codeforces.com/gym/542554/problem/G) 有一棵 $n$ 个点的树，以 $1$ 为根，边分为虚边与实边，初始全为虚边。给出 $q$ 次操作，每次操作给定一个点 $x$，进行 $\text{access}(x)$。在每次操作后，求出有多少排列 $p_{1\dots n}$ 使得依次进行 $\text{access}(p_1),\dots,\text{access}(p_n)$ 后得到当前给定的树，对 $998244353$ 取模。 $n,q\le 2\times 10^5$。 **** 实链剖分中 $\text{access}(x)$ 的效果为将 $x$ 至根路径上所有虚边变为实边并断掉该边父亲原有的与儿子连的实边，同时断掉 $x$ 与儿子的实边。于是一颗给定实链剖分的树中，对于每条实链，其链底必须最后操作；每条实链上的所有点必须比其链顶的父亲所在实链的所有点后操作。我们**将「点 $\bm x$ 必须在点 $\bm y$ 前操作」的限制描述成一条边 $\bm{x\to y}$**，则实链上每个点都向其链底连边，一条实链的链底向该链链顶的父亲所在实链的链底连边。注意到连出的边形成一颗树，答案为它的拓扑序数量。树的拓扑序计数公式为 $\dfrac{n!}{\prod sz_i}$，此处只有每条实链链底的子树大小大于 $1$，且其子树大小等于原树中链顶的子树大小。所以我们只需要求出每条实链的链顶的子树大小之积即可。注意到 $\text{access}$ 操作中只要能快速找到路径上每条虚边即可，分析如下：定义势能函数为「对该树进行轻重链剖分，有多少条重边此时为虚边」。考虑一次 $\text{access}(x)$ 操作前 $x$ 到根路径上的所有虚边，对于一条虚边，如果它是轻边，则此类虚边数量不超过 $O(\log n)$；如果它是重边，则修改后势能函数会减小 $1$。所以一次操作中势能增加不会超过 $O(\log n)$ 且每一条第二类虚边都会减小势能函数，所以总共跳过的虚边数量是 $O(n+q\log n)$ 的。这同时也是 LCT 的时间复杂度证明。使用轻重链剖分或者 LCT 直接维护即可，复杂度为 $O(n\log n+q\log ^2n)$ 或 $O(n+q\log n)$。 **** ### [[2024 联考 IV Day7] 钢琴教室 / anoko](http://192.168.102.138/JudgeOnline/problem.php?cid=2199&pid=0) 给你一个长为 $n$ 的序列 $a_{1\dots n}$，根据序列 $a_{1\dots n}$ 生成一张有 $n$ 个点的有向图，其边集为： - $\forall i\in[1,n),i\to i+1$； - $\forall i\in[1,n],i\to a_i$。接下来有 $q$ 次操作，操作的类型如下： - `1 x v`，表示令 $a_x\gets v$。 - `2 x`，表示查询由当前的 $a_{1\dots n}$ 生成的图中，点 $x$ 能到达的编号最小的结点。 $n,q\le 10^6$。 **** **考虑一个点 $\bm i$ 能否成为答案**，即能否走到编号更小的点。如果可以，那么必然存在一个 $j\ge i>a_j$ 使得你可以走到点 $a_j$。那么我们对于每个 $i$，将区间 $(a_i,i]$ 加一，从 $x$ 开始能走到的编号最小的点也就是 $x$ 左侧最近的 $0$ 的位置。带修问题可以直接用线段树维护，查询的时候使用线段树二分。时间复杂度 $O((n+q)\log n)$。 **** ### [[2024 联考 IV Day7] 丰雪千里祥音颂 / cristmas](http://192.168.102.138/JudgeOnline/problem.php?cid=2199&pid=1) 有一个 $n$ 个结点的环，环上还有 $m$ 个棋子，其中第 $i$ 个棋子初始在结点 $s_i$，需要到达结点 $t_i$。每个棋子有两条不同的简单路径使得其从 $s_i$ 移动到 $t_i$，你需要为每个棋子选择其中一条路径，使得所有棋子均经过的边的数量最大。 $m\le 5\times 10^5$。 **** 由于一个棋子的两条路径无交且包含所有的边，所以对于每条边，每个棋子恰有其中一条路径包含它。那么我们**枚举其中一条边，要求所有棋子均经过它**，那么所有棋子的路径选择方案就确定下来了。多条边能同时在答案中当且仅当它们确定的方案一致，即每条边对应一个选择方案，需要选出最大的等价类。判断等价关系直接使用**随机异或哈希**即可。时间复杂度 $O(m\log m)$。 **** ### [[2024 联考 IV Day7] 复读机 / repeat](http://192.168.102.138/JudgeOnline/problem.php?cid=2199&pid=3) 给你一个长度为 $n$ 的序列 $a_{1\dots n}$。接下来有 $q$ 次查询，每次给出一个区间 $[l,r]$ 和 $k$，你需要在区间中选择一个长为 $k$ 的子序列，最小化相邻两项的和的最大值。 $n\le 10^5$，$q\le2\times 10^5$。 **** 对于一个数 $v$，取出最长的相邻两项和 $\le v$ 的子序列，如果其长度 $\ge k$ 那么答案就 $\le v$。我们把 $2a_i\le v$ 的数称为「小数」，反之称之为「大数」。小数必定可连选，大数必定不可连选。最优情况必定为小数全选，对于每相邻两个小数，如果它们之间最小的大数可选就选上。那么我们**按值域从小到大做扫描线**，每次会将一些大数切换为小数。注意到相邻的小数之间显然均为大数，所以求出若干四元组 $(i,j,l,r)$ 表示在 $v\in [l,r]$ 时 $i,j$ 为相邻小数且对答案有 $1$ 的贡献。差分为对 $v\ge l$ 的单点加矩形求和，还需注意 $[i,j]$ 跨过端点时的贡献。对这些四元组以及询问进行整体二分即可。时间复杂度 $O((n+q)\log^2n)$，可以通过。 **对于一个时刻 $v$，仍有贡献的四元组 $(i,j,l,r),l\le v\le r$ 的区间 $[i,j]$ 除端点外互不相交，那么数点可以降一维：只要求 $i$ 在区间内，此时只会算多包含右端点的一个贡献区间**。前驱后继可以类似地在整体二分中双指针维护。时间复杂度 $O((n+q)\log n)$。 **** ### [[SNOI2017] 炸弹](https://www.luogu.com.cn/problem/P5025) 在一条数轴上有 $n$ 个炸弹，坐标分别为 $x_{1\sim n}$，每个炸弹分别有一个爆炸半径 $r_{1\sim n}$。当炸弹 $i$ 爆炸时，所有满足 $|x_i-x_j|\le r_i$ 的炸弹 $j$ 也会被引爆。对 $\forall i\in[1,n]$ 求出，如果引爆炸弹 $i$，最终会引爆几个炸弹。 $n\le 5\times 10^5$。 **** 我们遇到的困难是炸弹可能左右反复地激活，考虑以下做法。设 $[l_i,r_i]$ 为 $i$ 最终可激活的炸弹区间。先求出 $l_i'$ 表示只考虑 $[1,i]$ 的炸弹，激活 $i$ 最终可激活的最小炸弹编号，这可以一次单调栈求出。我们设 $d_i'$ 为 $\displaystyle\max_{j=l_i'}^i(d_j+x_j)$，这可以在单调栈过程中求出。此处 $d_i'$ 的意义为考虑引爆 $i$ 可引爆的其左侧的炸弹，这些炸弹中最右可炸到的位置。我们再用 $d_i'$ 类似地求出 $r_i$，并更新 $l_i$ 为 $\displaystyle\min_{j=i}^{r_i}l_j'$ 便可得到答案。考虑它的正确性，我们通过 $d_i'$ **将向左炸一次和向右炸一次压缩为一次操作**，只需要不断使用这种操作便可考虑到炸弹左右反复的情况。时间复杂度 $O(n)$。 **** ### [磁力块](https://www.luogu.com.cn/problem/P10590) 有 $n+1$ 块磁铁 $0\sim n$，每个磁铁都有四个属性 $(d_i,m_i,p_i,r_i)$，如果你拥有了磁铁 $i$，那么你就能吸引并拥有所有满足 $d_j\le r_i,m_j\le p_i$ 的磁铁 $j$，初始你只拥有磁铁 $0$，求最后你能得到多少的磁铁。 $n\le 2.5\times 10^5$。 **** 考虑广搜，过程中需要求出满足两维偏序限制的还未拥有过的磁铁，则预先对一维排序，另一维使用数据结构维护。线段树加 `vector` 即可，时间复杂度 $O(n\log n)$。 **** ### [WD 与地图](https://www.luogu.com.cn/problem/P5163) 给你一个 $n$ 个点 $m$ 条边的有向图，点 $i$ 有点权 $x_i$。接下来有 $q$ 次操作： - `1 u v` 表示删除边 $u\to v$。 - `2 i v` 表示令 $x_i\gets x_i+v$。 - `3 x k` 表示询问 $x$ 所在强连通分量的点权前 $k$ 大之和。 $n\le 10^5$，$m,q\le 2\times 10^5$。 **** 时光倒流变为加边。需要维护强连通分量，对于每条边求出这条边第一次加入强连通分量的时间。使用**整体二分**，先将所有加入时间 $\le mid$ 的边加入并进行缩点，便可将边划分至两侧。递归完左侧后需要保留缩点状态。令 $n,m,q$ 同阶，时间复杂度 $O(n\log n)$。 **** ### [A Graph Problem P](https://www.luogu.com.cn/problem/P9984) 给你一张 $n$ 个点 $m$ 条边的连通无向图，边有编号，对每个 $v\in [1,n]$ 求出： 1. 初始有一集合 $S=\{v\}$，变量 $r=0$。 2. 当 $|S|<n$，重复执行： 1. 找到编号最小的，仅有一个顶点在集合 $S$ 中的边，令其编号为 $t$。 2. 将 $t$ 不在 $S$ 中的那个顶点加入集合 $S$。 3. 将 $r$ 修改为 $10r+t$。 3. 返回 $r$。对每个 $v\in [1,n]$ 求出最终的 $r$，对 $10^9+7$ 取模。 $n\le 2\times 10^5$，$m\le 4\times 10^5$。 **** 以编号为权建出 **Kruscal 重构树**，考虑求一个点的答案。由于 **Kruscal 重构树上父亲权值一定大于儿子权值**，一个点的加边顺序必然为从它开始不断跳祖先，跳到一个点时立即将其另一子树从「该边连接的另一个结点」开始全部遍历一遍。可以用线段树维护，时间复杂度 $O(n\log n)$。 **** ### [Infinite Adventure P](https://www.luogu.com.cn/problem/P10198) 给定 $n$ 个数组 $c_{i,0\dots t_i-1}$，其中 $t_i$ 为 $2$ 的幂。有 $q$ 次询问，每次询问给出三个参数 $x,T,\Delta$，接下来会执行 $\Delta$ 次 $x\gets c_{x,T\bmod t_x},T\gets T+1$，求出最终的 $x$。 $n,\sum t\le 10^5$，$q\le 5\times 10^4$。 **** 令 $n=\sum t$，$v=\max\Delta$。 **从一点开始走若干步到达的点提示使用倍增**。我们的状态数不能太多，于是一个想法是设 $f_{i,j,k}$ 表示现在在点 $i$，当前时间 $\bmod\ t_i$ 等于 $j$，走 $2^k$ 步到达的点。此时一个问题是如果跳到一个 $t_u>t_i$ 的点 $u$，维护的信息不足以得知当前时间 $\bmod\ t_u$ 的值。**注意到 $t_i$ 只有 $\log n$ 种，即我们在一条路径上最多遇到 $\log n$ 次这种情况**。于是我们将此种情况下的 $f_{i,j,k}$ 定义为在这 $2^k$ 步中遇到的第一个 $t_u>t_i$ 的点 $u$，还需再维护 $g_{i,j,k}$ 表示在这个 $u$ 之前已经走了几步了。预处理与单次询问均可模拟：从高至低枚举每一位，不断跳直到该位为 $0$，每一位至多只会跳 $\log n$ 次。时间复杂度为 $O(n\log n\log^2v+q\log n\log v)$，无法通过。考虑复杂度瓶颈为预处理部分，我们在特殊情况中经过了形如 $i\to u\to v$ 且 $t_u<t_v<t_i$ 这样的路径，这造成了很大的复杂度开销，**我们希望每一次跳到的点 $u$ 对应的 $t_u$ 均为路径上的前缀最大值**，这样一条任意长的路径也只需要跳 $\log n+\log v$ 次即可跳完。考虑令 $f_{i,j,k}$ 为在时间为 $j\pmod{t_i}$ 时从点 $i$ 开始不断走直到经过了 $2^k$ 个使得 $t_u=t_i$ 的点 $u$ 或到达一个使得 $t_u>t_i$ 的点 $u$，此时到达的点。相应地有 $g_{i,j,k}$ 表示这条路径的长度。预处理时先从小到大枚举 $v$，对所有 $t_i=2^v$ 的 $i$ 求出所有 $f_{i,j,k}$。重点为求出 $f_{i,j,0}$，从 $c_{i,j}$ 开始不断向其后第一个 $t$ 比自身大的跳即可。询问时先不断向大跳直到达到路径上 $t$ 的最大值，此后跳过所有 $t$ 值为最大值的点即可减小最大值，显然我们只能减少 $\log n$ 次。总时间复杂度 $O(n\log v+q\log n\log v)$，可以通过。 **** ### [[2023 NOI模拟 Day22] 好串](http://192.168.102.138/JudgeOnline/problem.php?cid=2021&pid=1) 给你一个长为 $n$ 的 `01` 串 $s$，定义一个长度为 $k$ 的 `01` 串 $t$ 是好的当且仅当对于 $\forall i\in[1,k]$ 均有 $t_{1\dots i}$ 和 $t_{i\dots k}$ 中 `1` 的数量不小于 `0` 的数量。定义一个 01 串的权值为在其中的任意位置插入 `1` 使得其变为好的，最少需要插入多少个 `1`。有 $q$ 次询问，每次询问给出 $l,r$，求出 $s_{l\dots r}$ 的权值。 $n,q\le 10^6$。 **** 考虑求单串权值，经典地，`0/1` 视作 $-1,1$，要求所有前缀和和后缀和均非负。那么令 $c_i$ 为在 $i-1$ 与 $i$ 之间插入的 $1$ 的数量，则有若干个形如 $\sum_{j=1}^ic_j\ge p_i$ 和 $\sum_{j=i}^nc_j\ge q_i$ 的限制。 **考虑先满足前缀和的限制，注意到限制是同向的，于是只需要贪心地尽量后地插入 `1`**。经过一些处理可以得到答案为最大子段和减区间和，有一些边界情况。线段树维护，时间复杂度 $O(n\log n)$。 **** ### [Numbers on the blackboard](https://www.luogu.com.cn/problem/CF878E) 对于一个序列 $b_{1\sim k}$，执行 $k-1$ 次操作，每一次选择两个相邻的位置 $b_p,b_{p+1}$ 并将它们替换为一个数 $b_{p}+2b_{p+1}$。定义该序列的权值为最终剩余的数的最大值。给你一个长为 $n$ 的序列 $a_{1\sim n}$，接下来 $q$ 次询问 $[l,r]$，求出 $a_{l\sim r}$ 的权值，对 $10^9+7$ 取模。 $n,q\le 10^5$。 **** 考虑求全局的答案，从左往右扫，如果 $a_i\ge 0$ 则在合并 $a_{i-1}$ 之前一定会先将 $a_i$ 合并至 $a_{i-1}$，这种优先合并关系形成了若干段，使用栈维护这些段。加入一个数时先在栈顶单加一段，不断执行「当栈顶段的值为正时，将栈顶段向前合并」即可。容易发现栈中最多只有栈底一段为正，于是最终从左向右合并即可。 **对于求一个区间的答案，我们考虑其与前缀答案的差异**。注意到只有最左边一段是受影响的，并且操作顺序不改变，单独处理即可。时间复杂度 $O(n\log n)$。 **** ### [[2023 NOI模拟 Day35] 前缀和](http://192.168.102.138/JudgeOnline/problem.php?cid=2052&pid=2) 给你一个长为 $n$ 的数组 $a_{1\sim n}$，接下来 $q$ 次询问给出 $[l,r]$，求 $[l,r]$ 的所有子区间的最大前缀和之和。 $n\le 10^6$，$q\le 10^7$。 **** 最大前缀和即为 $\max_{i=l}^r s_i-s_{l-1}$，后面那一项容易前缀和计算，考虑求一个区间的所有子区间的最大值之和。记 $f(l_1,r_1,l_2,r_2)$ 为所有左端点在 $[l_1,r_1]$ 中，右端点在 $[l_2,r_2]$ 中的区间的最大值之和，将 $f(l,r,l,r)$ 简写为 $f([l,r])$。那么我们要求的就是 $f([l,r])$，将其差分，转化为求 $f([l,n])$，$f([r+1,n])$，$f(l,r,r+1,n)$ 三项。尝试求 $f(i,i,i,n)$，**考虑 $s_i$ 在哪些区间作出贡献**。要使得 $s_i$ 作出贡献，那么区间中一定不能有大于 $s_i$ 的值。找到 $r_i$ 表示 $i$ 右侧最近的大于 $s_i$ 的位置，那么右端点在 $r_i$ 及以后的部分与 $i$ 无关，在其之前的部分则固定贡献为 $s_i$，即 $f(i,i,i,n)=f(r_i,r_i,r_i,n)+a_i\cdot(r_i-i)$。贡献式中 $f(l,r,r+1,n)$ 仍然难以计算。考虑类比上述部分，使某些参数无关贡献计算。找出 $[l,r]$ 中的一个最大值 $p$，跨过 $p$ 的区间的贡献容易计算。考虑 $f([l,p-1])$，其中我们之前难以计算的部分为 $f(l,p-1,p,n)$，而此时我们发现由于有 $\forall i\in[l,p-1],s_i\le s_p$，那么 $[l,p-1]$ 必然不可能成为最大值，$f(l,p-1,p,n)$ 就等于 $(p-l)f(p,p,p,n)$！使用 ST 表即可通过，时间复杂度 $O(n\log n+q)$。 **其中蕴含的思想为钦定区间过某特殊点，类似图论问题中的钦定路径过特殊边、特殊点**。 **** ### [冒泡排序 2](https://www.luogu.com.cn/problem/P9596) 给你一个长为 $n$ 的序列 $a_{1\sim n}$，定义其权值为要使得其变为升序序列所需的最少冒泡排序轮数。接下来有 $q$ 次操作，每次操作为单点修改 $a_p\gets x$，在每次修改后求出 $a_{1\sim n}$ 的权值。 $n,q\le 5\times 10^5$。 **** 考虑一轮冒泡排序，对于每个非前缀最大值的位置 $p$，操作前 $p$ 前方最近的前缀最大值在这轮操作后会移动至 $p$ 后方。于是答案就是 $\displaystyle\max_i\left(\sum_{j<i}[a_j>a_i]\right)$。注意到答案只会在某个后缀最小值的位置处取到，但后缀最小值也不好维护。观察一个后缀最小值 $p$ 的答案 $\sum_{i<p}[a_i>a_p]$，由于 $\forall i>p,a_i>a_p$，所以有上式等于 $\sum_{i}[a_i>a_p]-(n-p)$。考虑一个非后缀最小值的位置 $q$，设 $q<p$ 且 $a_q\ge a_p$，那么显然有 $\sum_{i}[a_i>a_q]-(n-q)$ 小于 $\sum_{i}[a_i>a_p]-(n-p)$，即**该式的最大值必定在后缀最小值处取到，只需维护全局 $\bm{\max}$ 即可**！值域线段树维护即可。令 $n,q$ 同阶，时间复杂度 $O(n\log n)$。 **** ### [大师选徒](https://www.luogu.com.cn/problem/P7769) 给定一个长为 $n$ 的数组 $a_{1\sim n}$，有 $q$ 次询问，每次询问给出三个整数 $l,r,s$，求是否存在 $1\le p\le n-r+l,p\ne l$ 使得 $\forall k\in[0,r-l],a_{l+k}+a_{p+k}=s$。 $n,q\le 4\times 10^5$。 **** 和的限制是相当强的，不妨**考虑差分**，限制化为 $a_p=s-a_l$ 且 $\forall k\in[1,r-l],a_{l+k}-a_{l+k-1}=a_{b+k+1}-a_{b+k}$。那么将差分数组与其相反数的数组拼起来做一次后缀数组，询问时二分出满足与后缀 $l$ 的 LCP 大于等于 $r-l$ 的排名区间，再离线扫描线即可。时间复杂度 $O((n+q)\log n)$。 **** ### [[2024 联考 IV Day9] Tamaya](http://192.168.102.138/JudgeOnline/problem.php?cid=2201&pid=3) 给你一个长为 $n$ 的序列 $a_{1\sim n}$，长为 $m$ 的操作序列 $[l_{1\sim m},r_{1\sim m}]$，执行一次操作 $[l_i,r_i]$ 会对 $\forall j\in[l_i,r_i]$，将 $a_j$ 替换为它们的最大值。接下来有 $q$ 次操作，每次操作形如： - `1 x v`，令 $a_x\gets v$。 - `2 L R x`，如果进行操作序列中第 $L$ 到 $R$ 个操作，查询此时 $a_x$ 的值是什么。 $n,m,q\le 5\times 10^5$。 **** 归纳可以证明最终每个数都是原来一段数 $[p_i,q_i]$ 的 $\max$，并且 $p_i\le p_{i+1},q_i\le q_{i+1}$。 **因为最终要求单点值，我们的方向为尽量只维护 $\bm{[p_x,q_x]}$ 的变化。** 正序扫描操作序列会将 $[l_i,r_i]$ 中所有区间更新为它们的并，这涉及多个位置的 $[p_j,q_j]$，不符合我们设定的方向。尝试倒序扫描，遇到一个操作 $[l_i,r_i]$ 时，如果 $[l_i,r_i]\cap[p_x,q_x]\neq \varnothing$，将 $[p_x,q_x]$ 并上 $[l_i,r_i]$，这是好的。 **单独一点 $\bm x$ 信息太少，不妨先找到倒序处理过程中第一个包含 $x$ 的区间 $\bm{[l_p,r_p]}$，将询问的 $\bm R$ 移至 $\bm p$ 显然不改变答案**。 **任意时刻的 $\bm{p_x,q_x}$ 只可能是 $\bm{[x,x]}$ 或者某个 $\bm{[l_a,r_b]}$，这启示我们维护 $\bm{a_x,b_x}$**。那么遇到一个操作 $[l_i,r_i]$ 时就会将 $\forall l_i\le l_{a_x}\le r_i,a_x\gets i$，$b$ 同理。倍增可以维护，用 `set` 预处理出每个 $l_i,r_i$ 向前最早被哪个区间包含即可。令 $n,m,q$ 同阶，时间复杂度 $O(n\log n)$。 **** ### [[2023 NOI模拟 Day42] 计算几何](http://192.168.102.138/JudgeOnline/problem.php?cid=2026&pid=0) 给定平面上的 $n$ 个整点 $(x_i,y_i)$，你需要在平面上放置任意多个边长相同的正方形，需要满足： - 每个正方形至少覆盖三个给出的点。 - 正方形边界与坐标轴平行。 - 所有点都至少被一个正方形覆盖。求正方形边长的最小值。多组数据。 $n\le 2\times 10^5$，$\sum n\le 4\times 10^5$。 **** 二分边长 $x$。能放置正方形就一定放置，考虑这一正方形覆盖的三个点组成的三角形，可移动该正方形使得一个顶点为给定的点，进行数点即可。时间复杂度 $O(n\log n\log v)$，常数极大，无法通过。 **考虑我们所求的正方形均为定长 $x$ 的，定长区间考虑按长度分块**。将平面按 $x\times x$ 分块，需要对每个点判断是否存在另外两个点与其在同一个 $x\times x$ 的正方形中。如果一块内点数 $\ge 3$，那么其中所有点已经合法。否则对于本块内的一点 $(x_p,y_p)$，取出周围的块的所有点，尝试用一个端点为 $(x_p,y_p)$ 的正方形覆盖其中至少两个点，若仍旧失败，那么可选点数量为常数，直接枚举其中两个点判断即可。时间复杂度 $O(n\log v)$，可以通过。 **** ### [[2023 NOI模拟 Day41] 铺路](http://192.168.102.138/JudgeOnline/problem.php?cid=2025&pid=2) 有 $n$ 个点按顺序排成一行，初始所有点均为未激活状态。给定 $m$ 个区间 $[l_i,r_i]$，每一次操作选择一个区间 $p$ 使得： - 之前未选择过 $p$。 - 在所有未选择过的区间中，区间 $[l_p,r_p]$ 中未激活的点的数量最小。 - 区间内未激活的点的数量相同时优先选择编号小的区间。进行 $m$ 次操作，求出每次操作选择的区间。 $m\le 2.5\times 10^5$。 **** **若区间 $\bm{[l_j,r_j]}$ 包含区间 $\bm{[l_i,r_i]}$，那么区间 $\bm i$ 一定先于 $\bm j$ 被取出**。维护当前不包含任意未被取出的区间的区间序列，那么标记一个点会对其中一段区间产生影响。一棵 BIT 维护区间中未激活的点的权值和，一棵线段树维护这些互不包含的区间，一棵线段树维护未被选取过的区间，将区间放在左端点处维护。取出一个区间 $x$ 时需要拓展出一些新的区间，这些区间必然包含 $[l_x,r_x]$，又其不能包含其余区间，只需找到 $[l_x,r_x]$ 前后的两个区间即可解决问题。时间复杂度 $O(m\log m)$。 **** ### [进制与操作](https://www.luogu.com.cn/problem/P9376) 对于给定的长为 $n$ 的正整数序列 $a_{1\sim n}$ 与常数 $b$，有如下两种操作： - 选择 $p\in[1,n]$，令 $a_p\gets\left\lfloor\dfrac{a_p}{b}\right\rfloor$； - 选择 $p\in[1,n],v\in[0,b)$，令 $a_p\gets a_p\cdot b+v$。定义权值 $f(a_{1\sim n},b)$ 为要使 $a_{1\sim n}$ 两两相等所需的最少操作数量。给你一个长为 $n$ 的正整数序列 $a_{1\sim n}$，接下来 $q$ 次询问给出 $l,r,b$，查询 $f(a_{l\sim r},b)$。 $n,q\le 10^5$。 **** 最终的数一定为某个 $a_p$ 的前缀，考虑枚举 $p$，如何计算其所有前缀 $a_{p,1\sim i}$ 对应的答案。 **先将操作一进行至极端，即将每个数先清空，再逐步撤销多余的操作一**。如果 $a_{q,1\sim i}=a_{p,1\sim i}$，那么可减少一次操作一，否则需要增加一次操作二，我们只需查询 $\sum_{q=l}^r[a_{q,1\sim i}=a_{p,1\sim i}]$，可以枚举 $a_q$ 的位数，转为 $\log v$ 次询问区间中某值域区间内的数的数量，对单个 $p$ 计算其所有前缀答案的复杂度为 $O(\log^3v)$。只有区间中有超过一半的数和 $a_p$ 的最长公共前缀长度 $\ge i$ 时才可能选择 $a_{p,1\sim i}$，即随机任意区间内的 $a_x$，最终答案 $a_{p,1\sim i}$ 均有 $1/2$ 的概率为 $a_x$ 的前缀。故我们只需随机 $O(\log nq)$ 个位置，查询它们所有前缀的答案即可，时间复杂度 $O(q\log n\log^3v)$。但我们注意到每个长度的合法前缀均为唯一的，所以记录下已经找到的合法前缀，那么均摊下每个长度的前缀均只需判断一次。时间复杂度 $O(n\log v+q\log^3v)$。 **** ### [After god](https://www.luogu.com.cn/problem/P11368) 你需要维护两个长为 $n$ 的序列 $a_{1\sim n},b_{1\sim n}$，初值均为 $0$。接下来 $m$ 次操作，每次操作中给出 $x,y$，依次执行： - 令 $a_x\gets y$； - 令 $\forall i\in[1,n],b_i\gets b_i+\displaystyle\max_{j=1}^i a_j$； - 查询 $\displaystyle\sum_{i=1}^x b_i$。 $n,m\le 10^6$。 **** 直接维护前缀最大值需要单侧递归上传，复杂度过高不做考虑。令 $a_{i,t}$ 为时刻 $t$ 对应的 $a_i$，$c_{i,t}$ 为时刻 $t$ 中前缀 $a_{1\sim i,t}$ 的最大值。所求为 $\sum_{i=1}^x\sum_{j=1}^t c_{i,j}$。考虑**交换求和顺序，对序列维做扫描线**。设当前扫描到 $i$，则维护所有的 $c_{i,t}$ 以及其历史和 $\sum_{j=1}^ic_{j,t}$，对位置 $i$ 的若干次修改构成对 $c_{i,t}$ 的若干次区间取 $\max$ 操作，而一次查询即为前缀历史和查询。写一个维护历史和的吉司机线段树即可维护。时间复杂度 $O(n\log n)$。 **** ### [众数](https://www.luogu.com.cn/problem/P11398) 给你两个长为 $n$ 的序列 $a_{1\sim n},b_{1\sim n}$。定义下标 $i$ 的权值为将 $\forall 1\le j\le i$，$a_j$ 个 $b_j$ 拼接在一起后形成的序列的最大众数乘以 $a_i$。接下来有两种操作共 $m$ 次： - `1 x y`，将 $a_x$ 增加 $y$。保证 $y$ 非负。 - `2 x`，求最小的正整数 $k$ 使得下标 $n-k+1 \sim n$ 的权值异或和为 $x$。操作二保证有解，且所有答案之和 $\sum k$ 不超过 $5\times 10^7$。 $n,m\le 3\times 10^5$，$\sum k\le 5\times 10^7$。 **** 正向递推求解前缀 $i$ 权值是简单的，但逆向求解是困难的。为了控制枚举量，我们可以想到**设置一些关键前缀，每次从某个关键前缀处向后求解**。使用**倍增**，预处理所有前缀 $n-2^i$ 的信息，每次查询只需要 $O(k)$ 的枚举量，时间复杂度 $O((n+m)\log n+\sum k)$。 **** ### [[2025 联考 I Day4] 钓鱼](http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2209&pid=0) 给定 $n$ 个区间 $[l_i,r_i]$，构造一个字典序最小的排列 $p_{1\sim n}$ 使得 $p_{1\sim n}$ 中值 $v$ 的出现位置在 $l_v\sim r_v$ 中。无解输出 `-1`。 $n\le 2\times 10^5$。 **** 考虑如何判定无解。排列构造考虑二分图匹配，左部点 $i$ 向右部点 $l_i\sim r_i$ 连边。考虑 Hall 定理，枚举左部点集合 $S$，其邻点集合为 $\displaystyle\bigcup_{i\in S}[l_i,r_i]$，难以处理。考虑**枚举邻点集合** $T$，那么可选择的左部点必须要满足 $[l_i,r_i]\sube T$，分析可得只需要要求 $T$ 是一个区间时合法即可。设 $x_i$ 表示位置 $i$ 是否未填数，$y_i$ 表示值 $i$ 是否未填入，则要求对于任意的区间 $[l,r]$ 均有 $$\sum_{i=l}^rx_i\ge\sum_{j=1}^ny_j\big[[l_j,r_j]\sube[l,r]\big]$$ 现在需要判断在位置 $i$ 填数 $j$ 是否合法，由于判定复杂，必定不能模拟判定过程。**由于原状态合法，进行修改后只需要判定修改位置影响到的区间**。原先合法且修改后不合法状态需要存在一个满足 $l\le i\le r$ 且 $[l_j,r_j]$ 不包含于 $[l,r]$ 之中的区间使得不等式取等。由于已经填入了 $1\sim i-1$ 且 $l\le i$，直接取 $l=1$ 即可让限制最严格。维护 $q_i$ 表示有多少个未填入的值 $j$ 满足 $r_j\le i$，则合法需要满足 $\forall r\in[i,r_j),r-q_r\ge i$，线段树维护 $r-q_r$，找到 $i$ 右侧最近的 $p-r_p<i$，则位置 $i$ 可以填入最小的 $j$ 使得 $l_j\le i$ 且 $r_j\le p$。由于是升序枚举 $i$，只需要在 $l_j$ 处加入 $j$，线段树加 `set` 维护即可。时间复杂度 $O(n\log n)$。 **** ### [[SDOI2019] 世界地图](https://www.luogu.com.cn/problem/P5360) 给你一张 $n$ 行 $m$ 列的网格图，第 $i$ 行与第 $i+1$ 行有连边，第 $j$ 列与第 $j+1$ 列有连边，特别地，第 $1$ 列与第 $m$ 列有连边，边均有边权。接下来 $q$ 次询问，每次询问给出 $l,r$，表示询问假如删去第 $l\sim r$ 列的点，剩余的图的最小生成树的边权之和。 $n\le 100$，$m\le 10^4$，$q\le 3\times 10^4$。 **** 删除区间内的点的通常做法为维护前后缀信息并合并，于是我们需要将目光投向合并最小生成树上。注意到我们求整个图的最小生成树也需要 $O(nm\log n)$ 的时间复杂度且这是我们能接受的最高复杂度，我们需要**考虑在同样的时间复杂度内可以进行的操作与希望求出的信息**：我们要对 $m$ 个前后缀均求出其最小生成树的信息，且单次只允许 $O(n\log n)$ 的时间复杂度。合并的形式为两棵树中分别有 $n$ 个点对位相连一条边。维护加边最小生成树时，我们会找到加边两点间路径上的最长边，判断两条边之间的大小关系。经过讨论与模拟，对于一棵树，将这 $n$ 个新连边的点的虚树建出，断开的最长边只可能是虚树中相邻两点路径上的最长边，于是我们只需要对点数与边数均为 $O(n)$ 的图进行最小生成树算法即可。查询时无需求出新树的形态，于是只需要预处理排序数组即可。时间复杂度 $O(nm\log n+qn\alpha(n))$。 **** ### [学习轨迹](https://www.luogu.com.cn/problem/P10656) 给定四个正整数序列 $a_{1\sim n},x_{1\sim n},b_{1\sim m},y_{1\sim m}$，保证 $a_{1\sim n}$ 互不相同、$b_{1\sim m}$ 互不相同。你需要选择两个可空区间 $[l_1,r_1]\sube[1,n]$，$[l_2,r_2]\sube[1,m]$ 使得不存在 $i\in[l_1,r_1],j\in[l_2,r_2]$ 满足 $a_i=b_j$，在此情况下最大化 $\sum_{i=l_1}^{r_1} x_i+\sum_{i=l_2}^{r_2}y_i$。 $n,m\le 5\times 10^5$。 **** 此类最优化问题，**可以先找一组平凡解，在加强了限制要求得到的解优于平凡解的情况下可能导出新的性质**。对于本题，我们可以轻松得到只选择 $x_{1\sim n}$ 和只选择 $y_{1\sim m}$ 的两组平凡解。设平凡解答案为 $s$，则**求和的两部分必须有至少一部分不小于 $\bm s$ 的二分之一**。不妨设为 $x$ 部分，由于 $s$ 大于等于 $x_{1\sim n}$ 的和，我们找到最小的 $p$ 满足 $2\sum_{i=1}^px_i\ge s$，则任何强于平凡解的解均需要包含 $x_p$。那么对于序列 $y_{1\sim m}$，我们若想选择 $y_i$ 就不能选择 $a_j=b_i$，由于规定了必须包含 $x_p$，我们便可确定出区间 $[l_i,r_i]$ 要求选择的 $x_j$ 必须满足 $j\in [l_i,r_i]$。扫描线即可，使用单调栈与线段树，时间复杂度 $O(n\log n)$。 **** ### [2236 A.D.](https://www.luogu.com.cn/problem/P11648) 给你一颗 $n$ 个结点的树，结点 $1$ 为根，结点有 $[1,k]$ 的颜色 $c_i$。给定序列 $a_{1\sim k}$，定义两个结点 $x,y$ 之间的权值 $f(x,y)$ 为所有在 $x\to y$ 的简单路径上出现过的颜色 $c$ 的 $a_c$ 之积。对 $\forall i\in[1,n]$ 求出 $i$ 子树内的点两两之间的权值和，对 $998244353$ 取模。 $n\le 5\times 10^5$，$k\le 15$。 **** 直接对每个颜色集合预处理出其权值 $v_s$，考虑计算 $x$ 的不同子树 $i,j$ 间的答案。维护子树 $i$ 内每个点到 $i$ 的路径颜色集合 $S_i$，需要支持两种操作：将集合 $S_i$ 内所有元素并上 $c_x$；查询 $S_i,S_j$ 之间两两元素 $p,q$ 的 $v_{p\cup q}$ 之和，再合并这两个集合。一眼可以看出两个暴力，分别是直接枚举和 FWT 卷积，于是考虑根号分治。设置阈值 $b$，若 $S_i,S_j$ 均有 $\ge b$ 个元素便直接卷积；若 $S_i,S_j$ 均有 $\le b$ 个元素则直接枚举；否则对 $S_i$ 内每个元素 $p$ 计算 $\sum_{q\in S_j}cnt_qv_{p\cup q}$，这可以采用 [All Pairs Similarity P](https://www.luogu.com.cn/problem/P11458) 的做法，进行 $O(2^kk)$ 预处理 $O(1)$ 回答。注意每次计算完还需要合并，我们对每个集合分别维护一个 $\le b$ 个元素的零散部分和非零散部分的信息，合并后若零散部分大小 $\ge b$ 直接将其重构入非零散部分即可。将集合内的数取并可以直接暴力对零散部分做，维护非零散部分的取并标记。重构与卷积次数分别只有 $O(n/b)$ 次，零散部分的枚举量为 $\sum_{i,j}\min(siz_i,b)\min(siz_j,b)$ 即 $O(nb)$。取 $b=\sqrt{2^kk}$，时间复杂度 $O(n\sqrt{2^kk})$。 **** ### [[2025 NOI模拟 Day13] 括号序列](http://192.168.102.138/JudgeOnline/problem.php?cid=2245&pid=0) 给你一个长为 $n$ 的括号序列，其中每个左括号有权值 $a_i$。接下来 $q$ 次询问每次询问给出一个区间 $[l,r]$，求 $[l,r]$ 的一个子序列使得其为合法括号串且其中所有左括号权值之和最大。 $n,q\le 2\times 10^5$。 **** 考虑对于单次询问的简单贪心，只需从左往右扫，遇到一个右括号时将其与当前未匹配的权值最大左括号匹配即可。同时将枚举顺序反转同样可以得到一个从右往左扫的做法：遇到一个左括号时，若此时有未匹配右括号则直接匹配，否则比较其与当前匹配的权值最小的左括号，若当前括号权值更大则将权值最小的匹配括号替换掉。 **两个枚举方向分别可处理前缀查询与后缀查询，考虑序列分治**。二区间合并时会用右半区间未匹配的右括号匹配一些左半区间的未匹配左括号，以及用左半区间一些未匹配左括号替换右半区间已匹配左括号。可使用主席树双树二分解决。时间复杂度 $O(n\log^2 n)$。 **** ### [[广东省队集训 2025] 火力全开](http://8.138.223.198/p/9) 有 $n$ 个敌人以及 $m$ 种法术，每个敌人有属性 $(a_i,b_i)$，每种法术也有属性 $(c_i,d_i)$，为了击败敌人，你有两种攻击方法： - 花费 $1$ 的代价将某位敌人的 $a_i$ 减小 $1$。 - 花费 $c_i$ 的代价使用第 $i$ 种法术。所有敌人有统一的法术抗性 $k$，若使用了不少于 $k$ 种属性值 $d_j$ 不小于 $b_i$ 的法术，则敌人 $i$ 会被击败。另外，若敌人 $i$ 的属性 $a_i$ 降至零，其同样会被击败。接下来有 $q$ 次操作，每次操作会将某位敌人的属性 $(a_i,b_i)$ 或某种法术的属性 $(c_i,d_i)$ 进行修改。在每次操作后求出击败所有敌人所需的最小代价。 $n,m,q\le 2.5\times 10^5$，$k\le 10^4$，$k\cdot q\le 5\times 10^5$。 **** 显然我们只可能使用 $0$ 或 $k$ 种法术，不妨枚举使用的最小属性值 $x=\min d_i$，那么代价即为 $d_i\ge x$ 中 $c_i$ 的前 $k$ 小之和加上所有 $b_i>x$ 的 $\sum a_i$。考虑**弱化条件**，改为选取一个后缀，代价为其中的 $\sum a_i$，并在其中选取 $k$ 个 $c_i$ 加入代价。使用线段树维护，每个区间维护 $f_{0\sim k},g_{0\sim k}$ 分别表示区间中选取 $i$ 个 $c_i$ 的答案以及选取区间的一个后缀并已经在其中选取了 $i$ 个 $c_i$ 的答案。合并时会将左区间的 $g_{0\sim k}$ 与右区间的 $f_{0\sim k}$ 作 $(\min,+)$ 卷积，**由于 $\bm{f_{0\sim k}}$ 下凸，其关于选取的 $\bm{g_i}$ 有决策单调性**，可采用决策单调性分治。分析复杂度，由于区间长度不及 $k$ 时只保留区间长度位，故时间复杂度为 $O((n+qk)\log n\log k)$。 **** ### [[广东省队集训 2025] 修理](http://8.138.223.198/p/17) 给定一个长为 $n$ 的正整数序列 $a_{1\sim n}$。对于一个序列 $b_{1\sim m}$： - 初始有一常数 $x=0$； - 你可以进行若干次操作，操作共有两种： - 令 $x\gets x+1$； - 选择 $1\le i\le m$，令 $b_i\gets b_i\oplus x$。 - 定义序列 $b_{1\sim m}$ 的权值为要使 $b_{1\sim m}$ 均变为 $0$ 所需的最小操作次数。接下来有 $q$ 次询问，每次询问给出 $l,r$，求出 $a_{l\sim r}$ 的权值。强制在线。 $n,q\le 2\times 10^5$。 **** 由于 $x$ 必须达到区间中的数的最高位，可以发现每个数最多只需要操作两次。只考虑区间内含有最高位 $k$ 的数并统一减去 $2^k$，问题转化为求解 $\min(x+\sum [a_i>x])$。将上式写作 $\max(\sum[a_i\le x]-x)$，**逆用 Hall 定理，将问题转化为二分图匹配问题**，左部点 $i$ 向右部点 $j\le a_i$ 连边，上式即为左部点失配点数。由于所有左部点均向右部一个前缀连边，故可以以任意顺序贪心匹配，不妨按照 $r,r-1,\dots,l$ 的顺序进行匹配。按右端点进行扫描线，扫到 $r$ 时，由于我们从右至左贪心匹配，故一定匹配 $r$。**使用 Hall 定理维护并判断是否可成功加入 $r$**，只需要判断是否满足 $\min(x-\sum[a_i\le x])\ge 0$ 即可。若不能直接匹配，则需要我们找到最左侧的匹配点 $l$ 使得删去 $l$ 后存在完美匹配。这只需要找到最小的 $x$ 使得 $(x-\sum [a_i\le x])< 0$，那么 $l$ 即为最小的满足 $a_l\le x$ 的位置。上述操作均可使用线段树简单维护，而询问只需使用主席树维护矩形加单点求值。精细实现可做到时间复杂度 $O((n+q)\log n)$。 **** ### [[广东省队集训 2025] 平衡树](http://8.138.223.198/p/27) 给你一棵 $n$ 个点的树，带有点权 $a_{1\sim n}$。定义一条边的权值为其两侧点权和之差，定义一次操作为将一个点的点权加一。接下来有 $q$ 次询问，每次询问给出三个整数 $k,l,r$ 与 $k$ 条关键边，你需要执行至少 $l$ 次至多 $r$ 次操作，最小化所有关键边权值的最大值。 $n,q,\sum k\le 3\times 10^5$。 **** 对于每一次询问，可以将所有非关键边缩掉，剩余的树只包含关键边。注意到若三条关键边在同一条链上，那么中间那一条必定不会成为权值最大的边，于是只需要考虑所有叶子。令总点权和为 $s$，叶子权值分别为 $v_{1\sim c}$，那么一个叶子对应的权值即为 $|s-2v_i|$。注意到 $2v_i>s$ 的叶子只会有至多一个且一定不会成为权值最大的叶子，故不妨直接定义叶子对应的权值为 $s-2v_i$。执行一次操作必定为选取 $v_i$ 最小的叶子将其加一，执行完 $l$ 次操作后若 $v_i$ 最小的叶子仍然唯一便可继续执行。找叶子可以使用 BIT，时间复杂度 $O(n+\sum k\log n)$。 **** ### [呼吸之野](https://www.luogu.com.cn/problem/P14463) 给定一个长为 $n$ 的排列 $a_{1\sim n}$ 和常数 $k$，称区间 $[l,r]$ 对于 $x$ 合法当且仅当区间长度不小于 $k$ 且 $a_{l\sim r}$ 的中位数不小于 $x$。接下来 $q$ 次询问，每次询问给出 $l,r,x$，求出 $[l,r]$ 有多少对于 $x$ 合法的极短子区间。多组数据。 $n,q\le 10^5$，$T\le 6$。 **** 区间中位数 $\ge x$ 即将 $\ge x,<x$ 的数分别视作 $+1,-1$，要求和 $\ge 0$。 **考虑 $x$ 逐渐增大的过程**，每次会将一个 $+1$ 变为 $-1$，使得固定区间的和单调不增。维护以 $i$ 为右端点的极短合法区间 $[l_i,i]$，删去其中存在 $l_i\le l_j\le j< i$ 的 $i$，则 $l_i$ 递增。我们说明此时删去的 $i$ 在更大的 $x$ 时依旧被删去： - 由于 $[l_i,i]$ 包含 $[l_j,j]$，修改落在 $[l_j,j]$ 中时一定也落在 $[l_i,i]$ 之中，于是 $l_j$ 向左移动时 $l_i$ 也一定向左移动，此时一定有两区间和均为 $0$ 且 $[l_i,l_j)$ 之和 $\ge 0$，所以 $l_i\le l_j$ 依旧成立。记 $tl_i,tr_i$ 为 $i$ 作为左端点/右端点未被删去的最大 $x$，则在 $x\le tl_i$ 时，$i$ 是一个极短区间的左端点。**由于一个时刻存在的极短区间左右端点均递增，我们可以将左右端点一一对应起来**。询问时只需要求出右端点 $\le r$ 的区间数减去左端点 $<l$ 的区间数即可，这是二维数点。接下来考虑求出 $tr_i$，同理可求 $tl_i$。对于一个 $x$，判断此时 $i$ 是否不被删去，考察上一个未被删去的位置 $j$，分类讨论： - 如果 $(j,i]$ 之和 $>0$：那么 $i$ 一定不被删除，因为 $l_i$ 至少可以取到 $l_j+1$，长度与总和均合法。 - 如果 $(j,i]$ 之和 $\le 0$：若 $l_j<l_i\le j$，那么显然 $[l_i,j]$ 之和 $\ge 0$，故 $l_j$ 是因为长度限制不能取到 $l_i$，故必要条件为 $j-k+1<l_i\le i-k+1$，只需在这个区间内寻找合法的 $l_i$。 **在序列上从左到右做扫描线，维护时间维的信息**。记时间点 $x$ 的上一个未被删除的位置为 $j_x$，只需要满足以下两个条件之一： - $(j_x,i]$ 的区间和 $>0$； - 存在 $p\in(j_x-k+1,i-k+1]$ 满足 $[p,i]$ 之和 $\ge 0$。后者即为维护 $\min a_x\le b_x$，其中 $a_x$ 是 $p\in[j_x-k+1,i-k+1)$ 的前缀和的最小值，$b_x$ 是 $i$ 的前缀和。使用历史最小值的线段树可以维护。分别找到两者合法的最大 $x$，取较大值即可。时间复杂度 $O((n+q)\log n)$。 # 特殊技巧 ### [[2024 联考 II Day3] 串串](http://192.168.102.138/JudgeOnline/problem.php?cid=2176&pid=1) 给你 $n$ 个字符串 $s_{1\dots n}$，每次询问给出 $l,r,k$，求出 $s_k$ 在 $s_{l\sim r}$ 中的本质不同出现次数个数。 $n,q,\sum |s|\le 10^5$。 **** **字符串长度和可导出自然根号**。压缩重串，设给出的字符串构成若干等价类 $t_{1\dots k}$，则 $t_i$ 在 $s_j$ 中出现 $c$ 次（$c>0$）的三元组 $(i,j,c)$ 只有 $O(l\sqrt l)$ 对并可在对应时间复杂度内求出。对单个等价类做扫描线，用分块平衡一下即可做到 $O(l\sqrt l)$。 **** ### [[2024 联考 II Day4] A](http://192.168.102.138/JudgeOnline/problem.php?cid=2178&pid=0) 有一个长为 $n$ 的序列 $a$，初始 $a_i=i$，$m$ 次操作每次交换两个位置，有 $q$ 个询问串 $b_{1\dots m}$，问每个询问串最早在哪次操作后在 $a$ 中作为子串出现。保证交换操作随机。 $n,m,q,\sum|b_i|\le 3\times 10^5$。 **** 令 $\sum|b_i|=O(m)$，直接对询问串建 ACAM 可以做到 $O(nm)$。 $n$ 较大时涉及每个数的交换次数只有 $O(\dfrac m n)$，对于每次操作把涉及这 $|b_i|$ 个数的操作拉出来做可以做到 $O(\dfrac{m^2}{n})$，平衡到 $O(m\sqrt m)$。对大的部分进一步优化，对每个在任意时刻相邻过的二元组 $(p,q)$ 维护其所有相邻的时间，那么总区间数量是 $O(m)$ 的，即每对二元组的区间数是 $O(\dfrac{m}{n^2})$ 的，每次对 $k_i$ 个二元组暴力求交即 $O(\dfrac{m^2}{n^2})$，平衡到 $O(m^{4/3})$，可以通过。再进一步，对每个在任意时刻相邻过的长为 $k$ 的子串 $(p_1,p_2\dots p_k)$ 维护其所有相邻的时间，那么总区间数量是 $O(mk)$ 的，即每个长为 $k$ 的子串的区间数是 $O(\dfrac{mk}{n^k})$ 的，总复杂度 $O(mk+\dfrac{m^2k}{n^k})$，取 $k=\log_nm$，则达到复杂度 $O(m\log_nm)$。 **** ### [DZY Loves Chinese II](https://www.luogu.com.cn/problem/P10778) 给定 $n$ 个点 $m$ 条边的无向图，接下来 $q$ 次询问，每次给定一个边集 $e_{1\sim k}$，求删除该边集后图是否连通。强制在线。 $n\leq 10^5$，$m\leq 5\times 10^5$，$q\leq 5\times 10^4$，$k\leq 15$。 **** 考虑**随机异或哈希**。我们称一个边集为基础边集当且仅当删除这个边集后图不连通且删除这个边集的任意真子集都无法使得图不连通。我们尝试赋权使得所有基础边集的权值异或和都为 $0$，无法由基础边集组合出的边集的权值异或和为 $0$ 的概率较小。注意到基础边集删去后图一定变为两个连通块，则两连通块间边权异或和为 $0$。一个显然的必要条件是每个点的边权异或和为 $0$，玩一下发现这是充分的。直接提取一颗生成树，非树边随机赋权，树边满足儿子的条件即可。对于一次查询，我们需要判断给出的这些边是否包含一个基础边集，即是否包含边权异或和为 $0$ 的子集，线性基即可。时间复杂度 $O(n+m+qk\log w)$。 **** ### [[2023 NOI模拟 Day3] 数学题](http://192.168.102.138/JudgeOnline/problem.php?cid=1995&pid=1) 给你两个长度分别为 $n,m$ 的字符串 $A,B$ 以及一个长为 $n$ 的数组 $v_{1\sim n}$ 表示 $A$ 每个位置的权值，定义一个 $A$ 的子序列的权值为对应下标的权值之和，有 $q$ 次询问给出 $[l,r]$，求 $A_{l\sim r}$ 所有匹配 $B$ 的子序列的权值和，对 $10^9+7$ 取模。 $n\le 2\times 10^5$，$m\le 30$，$q\le 10^6$。 **** 显然权值不重要。不难写成矩阵形式，每次询问求区间矩阵乘积，用 [该题](https://www.luogu.com.cn/article/02pcppl3) 的方法可以做到 $O(nm^2\log n+qm)$，过不去。观察一下这个转移矩阵，发现它是满秩的，即它有逆矩阵，于是可以维护前缀乘积及其逆，把单个矩阵拆成几个初等矩阵手玩求逆即可，时间复杂度 $O(nm^2+qm)$。 **** ### [[省选联考 2024] 魔法手杖](https://www.luogu.com.cn/problem/P10218) 给你两个长为 $n$ 的序列 $a_{1\sim n},b_{1\sim n}$，满足 $a_i \in [0,2^k-1]$ 以及 $b_i\geq 0$，你需要给出 $S \subseteq \{1,2,\dots,n\}$ 以及 $x \in [0,2^k-1]$ 满足以下条件： - $\sum \limits_{i\in S} b_i\leq m$； - 满足以上条件的前提下，最大化 $val(S,x)=\min(\min \limits_{i \in S}(a_i+x),\min \limits_{i \in U \backslash S}(a_i \oplus x))$ 的值。你只需要求出最大的 $val(S,x)$ 的值即可。多组数据。 $n\le 10^5$，$\sum n\le 5\times 10^5$，$k\le 120$。 **** **从高往低贪心每一位能否是 $1$，只需要取低位限制最松的情况来判断**。从高到低贪心答案的每一位是否能是 $1$，考虑 $x$ 这一位取什么。如果 $x$ 这一位可能取 $0/1$ 就向那一边递归，如果无论怎么取都无法使答案这一位为 $1$ 就直接递归两边。以 $x$ 第 $i$ 位取 $0$ 时的判断为例，此时左子树全部归给 $S$ 中： - 左子树的 $\sum b$ 不能比剩余的 $m$ 大； - 当前归给 $S$ 的所有数的最小值加上 $x+2^i-1$ 要大于等于 $ans+2^i$，即最坏情况下 $x$ 后 $i-1$ 位全取 $1$，$ans$ 后 $i-1$ 位全取 $0$，此时满足条件即可。每个结点只会被搜到一次，时间复杂度 $O(\sum nk)$，可以通过。 **** ### [Trzy kule](https://www.luogu.com.cn/problem/P5982) 给你三个长为 $n$ 的 01 串 $A_{1\sim 3,1\sim n}$ 以及三个整数 $r_{1\sim 3}$。定义两个 01 串的距离为它们不同的位置数量，求有多少个 01 串 $S_{1\sim n}$ 满足至少有一个 $i\in [1,3]$ 满足 $S$ 与 $A_i$ 的距离不超过 $r_i$。 $n\le 10^4$。 **** 求三个限制都不满足的方案数，不妨令 $r_i\gets n-r_i-1$。我们只关注相对的关系，所以如果 $A_i=0$ 我们就同时取反 $A_i,B_i,C_i,S_i$，答案不变。 $(A_i,B_i,C_i)$ 共有 $(1,1,1),(1,1,0),(1,0,1),(1,0,0)$ 四种情况，设它们的数量分别为 $k_{1\sim4}$，设 $c_{1\sim4}$ 为这四种情况中分别有多少个 $S_i=1$，则有以下三个限制： $$\begin{aligned}c_1+c_2+c_3+c_4&\le r_1\\c_1+c_2+(k_3-c_3)+(k_4-c_4)&\le r_2\\c_1+(k_2-c_2)+c_3+(k_4-c_4)&\le r_3\end{aligned}$$ 直接枚举 $c_{1\sim4}$ 可以做到 $O(n^4)$。 **可以考虑折半以将时间复杂度开根**。设 $s_{i,j}=\displaystyle\sum_{c_1,c_2}\binom{k_1}{c_1}\binom{k_2}{c_2}[c_1+c_2\le i][c_1+k_2-c_2\le j]$，可以使用一次二维前缀和求出。计算答案时只需枚举 $c_3,c_4$ 即可。时间复杂度 $O(n^2)$。 **** ### [Wielki Zderzacz Termionów](https://www.luogu.com.cn/problem/P9252) 有红绿蓝三种颜色的棋子，定义一个棋子序列是好的当且仅当其能通过执行若干次如下操作使得最终剩余恰好一个棋子： - 将两个相邻的红色棋子替换为一个绿色棋子。 - 将两个相邻的绿色棋子替换为一个红色棋子。定义一个棋子序列的权值为有多少种将蓝色棋子替换为红绿棋子的方案数使得该棋子序列是好的。给你一个长为 $n$ 的棋子序列，颜色分别为 $c_{1\sim n}$。接下来 $q$ 次操作对 $c$ 进行单点修改，在每次操作后求出当前棋子序列的权值，对 $10^9+7$ 取模。 $n,q\le 2\times 10^5$。 **** 两红子合并为一绿子，两绿子合并为一红子。此类问题可考虑**三进制加法**。给红子绿子分别赋 $1,2$ 的权，则三进制下**所有棋子的权值和不变**。考虑判定一个局面是否合法，尝试构造一个合并方案：如果第一个同色连续段长度大于 $1$ 则取这个连续段最后两个棋子合并，否则取第一个长度大于 $1$ 的连续段的前两个合并。按照这种合并方案，若可执行第一步操作便可不断执行直到仅剩一子。于是我们得出了局面合法的充要条件：权值和模 $3$ 非零且存在长度大于 $1$ 的同色连续段。单次询问需要求出 $f_{k,c}=\displaystyle\sum_{i=0}^k\binom k i[i\equiv c(\bmod\ 3)]$，递推预处理即可。时间复杂度 $O(n+q)$。 **** ### [Xor Cards](https://www.luogu.com.cn/problem/AT_abc249_g) 给你两个长为 $n$ 的序列 $x_{1\sim n},y_{1\sim n}$ 以及一个常数 $k$。你需要选出一个子集 $S$ 使得 $\operatorname{xor}_{i\in S} x_i\le k$，最大化 $\operatorname{xor}_{i\in S} y_i$。 $n\le 5\times 10^5$。 **** 考虑从高往低贪心确定答案的每一位，对此我们先考虑我们能异或出哪些二元组，将 $(x,y)$ 绑定为 $y\times 2^{31}+x$ 丢入线性基即可将二元组规模缩小到 $O(\log v)$ 且保证了所有 $y$ 非零的二元组的 $y$ 的最高位互不相同。 **从高至低贪心，此二元组后的所有二元组均可随意选且不会影响该位**，于是将这个二元组后面所有二元组的 $x$ 放入线性基即可判断此二元组能否选或不选。时间复杂度 $O(n\log v)$。 **** ### [[2023 NOI模拟 Day43] 防诈骗](http://192.168.102.138/JudgeOnline/problem.php?cid=2027&pid=0) 考虑以下博弈问题：有一个长为 $n$ 的 `01` 串 $s_{1\sim n}$，初始全为 `1`，两人轮流操作，每次操作为： - 选择一个下标 $x$ 以及一个正整数 $p$，满足 $x\cdot 2^p\le n$ 且 $s_x=1$，取反 $s_x,s_{x\cdot 2^p}$。不能操作者输。称 $n$ 为合法数当且仅当进行上述博弈问题时后手存在必胜策略。多次询问，每次询问给出一个整数 $k$，求出第 $k$ 小的合法数。 $T\le 200$，$k\le 10^{15}$。 **** 首先将不能操作的位置分离开，两个位置 $i,j$ 能进行一次操作当且仅当 $i,j$ 在二进制下去除末尾的 $0$ 后相同。那么对于每个奇数 $c$，构成一个大小为 $l=\lfloor\dfrac{n}{c}\rfloor$ 的子问题，需要求出其 SG 值。其中子问题为初始有一长为 $l$ 的序列 $s_{1\sim l}$，初始全为 $1$，每次操作选择 $1\le i<j\le l$ 满足 $s_i\bmod2=1$，执行 $s_i\gets s_i-1,s_j\gets s_j+1$。 **由于数只能向后移动，我们不考虑每个位置上的值，而考虑初始每个位置上的 $1$ 当前在哪个位置**。不妨看作初始有 $0\sim l-1$ 堆石子，每次将某堆石子减少 $v$ 个看作向后移动 $v$ 个位置。为了满足只可后移奇数的限制，在出现两堆石子个数相同的石子时需要将它们均移除，不难归纳证明此问题的 SG 值与 Nim 游戏相同。故原问题的 SG 值即为 $$\bigoplus_{i=1}^n[2\nmid i]\bigoplus_{j=0}^{\lfloor{n}/{i}\rfloor-1}j$$ 经过简单的推导可以得到，若 $n$ 的二进制分解为 $n_{0\sim d-1}$，那么 SG 值为 $$\bigoplus_{i=0}^{d-1}[n_i\ne n_{i+1}]i$$ 可以进行数位 DP，求解第 $k$ 小倍增即可，时间复杂度 $O(T\log^3v)$，可以通过。 **** ### [A Horrible Poem](https://www.luogu.com.cn/problem/P3538) 给你一个长为 $n$ 的字符串 $s$，有 $q$ 次询问，每次询问给出一个区间 $[l,r]$，查询 $s_{l\dots r}$ 的最小整周期。 $n\le 5\times 10^5$，$q\le 2\times 10^6$。 **** 所有整周期均为最小整周期的倍数且 $r-l+1$ 也为一个整周期，故将 $r-l+1$ 质因数分解后，**对逐个质因子 $\bm p$ 试除，若当前答案除以 $\bm p$ 仍合法便将其除以 $\bm p$，最终结果即为答案**。使用线性筛、哈希，时间复杂度 $O(n+q\log n)$。 **** ### [基础数论函数练习题](https://www.luogu.com.cn/problem/P5655) 给你一个长为 $n$ 的序列 $a_{1\sim n}$，接下来 $q$ 次询问，每次询问给出 $[l,r]$，求出 $\operatorname{lcm}(a_l,\dots,a_r)$，将答案对 $10^9+7$ 取模。多组数据。 $T\le 300$，$n,q\le 300$。 **** 我们有： $$\text{lcm}(a_1,\dots,a_i)=\text{lcm}(a_1,\dots,a_{i-1})\cdot\dfrac{a_i}{\gcd(a_i,\text{lcm}(a_1,\dots,a_{i-1}))}$$ 那么令 $b_i=\dfrac{\text{lcm}(a_1,\dots,a_{i})}{\text{lcm}(a_1,\dots,a_{i-1})}$，有： $$b_i=\dfrac{a_i}{\gcd(a_i,\prod_{j=1}^{i-1}b_j)}$$ 其中 $b_i$ 的含义即为 $a_i$ 中比 $a_{1\sim i-1}$ 多出的贡献。由于 $\gcd$ 的性质，分母等于 $\gcd(a_i,\prod_{j=1}^{i-1}b_j\bmod a_i)$，于是我们得到了 $O(n^2+n\log v)$ 计算 $n$ 个数的 $\text{lcm}$ 的算法。区间询问，考虑扫描线。现在扫到 $r$，维护 $b_i=\dfrac{\text{lcm}(a_i,\dots,a_{r})}{\text{lcm}(a_{i+1},\dots,a_r)}$。考虑加入 $a_{r+1}$ 对 $b_i$ 的修改： $$b_i\gets \dfrac{b_i}{\dfrac{\gcd(a_{r+1},\prod_{j=i}^rb_j)}{\gcd(a_{r+1},\prod_{j=i+1}^rb_j)}}$$ 令 $s_i$ 表示 $\prod_{j=i}^r b_j$，$c_i$ 表示 $\gcd(a_{r+1},s_j)$，那么有 $c_{i+1}\mid c_i$，故 $\dfrac{c_i}{c_{i+1}}$ 只有 $O(\log v)$ 个位置不为 $1$，目标为判断是否有 $c_i=c_{i+1}$。考察 $c_i=c_{i+1}$ 即 $\gcd(a_{r+1},s_i)=\gcd(a_{r+1},s_{i+1})$ 成立的条件。**对每一质因子 $\bm p$ 考虑**，若 $a_{r+1},s_i,s_{i+1}$ 中分别有 $x,y,z$ 个 $p$，其中 $y\le z$ 恒成立，上式成立要求 $\min(x,y)=\min(x,z)$，等价于 $\min(x,z)\le y$，对应回原式即为 $s_{i+1}\bmod c_i=0$。从左向右依次求出 $c_i$ 即可，时间复杂度 $O(\sum n^2+n\log^2 v)$。 **** ### [[2025 联考 I Day6] 随机游走](http://xsy.gdgzez.com.cn/JudgeOnline/problem.php?cid=2211&pid=0) 给你一张 $n$ 个点的有向图，有 $m$ 个人，其中第 $i$ 个人在时刻 $t_i$ 出现在结点 $p_i$，每个人在出现后的每个时刻均会均匀随机地走向一条出边。记 $f(i)$ 表示时刻 $i$ 中结点 $n$ 上面的期望人数，给定常数 $T$，求出 $f(1),\dots,f(T)$，对 $10^9+7$ 取模。 $n\le 70$，$m\le 10^4$，$T\le 2\times 10^6$。 **** 我们需要对于向量 $V$ 及固定的矩阵 $A$ 求出 $V\times A^{0\sim k}$ 的第 $n$ 项，朴素实现需要每次执行向量乘矩阵，时间复杂度 $O(Tn^2)$。注意到我们只需要求出向量乘矩阵的单项，可以线性求出，我们希望每一个时刻都只需要线性的时间就做到，但我们不可能预处理出 $A^{0\sim T}$。设定阈值 $b$，记 $i=p\cdot b+q$，则 $V\times A^i=V\times A^{b\cdot p}\times A^q$，预处理 $A^{0\sim b}$，查询时对 $p\in[0,\frac kb]$ 求出 $V\times A^{b\cdot p}$ 即可。时间复杂度 $O(n^3b+\dfrac{n^2T}{b}+nT)$，取 $b=\sqrt{\dfrac{T}{n}}$ 即可达到 $O(n^{5/2}T^{1/2}+nT)$。 **** ### [Boolean Computer](https://www.luogu.com.cn/problem/P12020) 给定 $n,m,q$ 以及 $m$ 个在 $[0,2^n)$ 内的整数 $a_{1\sim m}$。现有与、或、异或、与非、或非、同或六种位运算，对于给出的一个长为 $n$ 的运算法则 $s_{0\sim n-1}$，其中 $s_i$ 为六种位运算之一，数 $x,y$ 关于该运算法则的运算结果的第 $i$ 位是 $x,y$ 的第 $i$ 位通过运算 $s_i$ 得到的。接下来给出 $q$ 次询问，每次询问给出一个运算法则 $s_{0\sim n-1}$ 与一个整数 $k$，求出有多少二元组 $1\le i,j\le m$ 满足 $a_i\odot a_j=k$。 $n\le 16$，$m,q\le 10^5$。 **** 单独考虑一位的情况，根据这一位的运算和该位 $k$ 的值，我们会得到一条形如「$a_i,a_j$ 该位需要有 $x$ 个 $1$」或「$a_i,a_j$ 该位需要有 $x$ 或 $y$ 个 $1$」的限制。对于每个询问，对所有限制集大小为 $2$ 的位进行枚举，即可确定每一位需要总共有多少个 $1$。这可以视作将 $a_i$ 的二进制形式看作三进制数，并求有多少对 $(i,j)$ 满足 $a_i+a_j$ 等于给定数，可以使用引入单位根的三进制 FWT 解决。若询问中通过 DFS 枚举，时间复杂度 $O(n3^n+q2^n)$。 **注意到上述算法询问复杂度与询问中限制集大小为 $\bm 2$ 的限制数 $\bm c$ 正相关，不妨考虑阈值分治的思想，设计一个当 $\bm c$ 较大时较快的算法**。考虑将限制集大小为 $1$ 的限制表述成大小为 $2$ 的限制，这可通过容斥做到，一条限制集大小为 $1$ 的限制需要容斥为三条大小为 $2$ 的限制。此时我们需要求有多少对 $(i,j)$ 满足 $a_i+a_j$ 每一位都不等于给定数，这也可通过三进制 FWT 实现。总时间复杂度 $O(n3^n+q\min(2^c,3^{n-c}))$，可以通过。 **** # 构造 ### [旋转序列](https://pjudge.ac/contest/1713/problem/21838) 给定三个整数 $n,k,l$，请构造两个长为 $n$ 的 01 序列 $a_{0\sim n-1},b_{0\sim n-1}$ 满足 $\sum a_i=k,\sum b_i=l$ 并最小化 $\max_j\sum_i[a_i=b_{(i+j)\bmod n}=1]$。 $n\le 5\times 10^5$。 **** 注意到 $\sum_{i,j}[a_i=b_{(i+j)\bmod n}=1]=k\cdot l$，根据**抽屉原理**，答案的下界为 $\left\lceil\dfrac{k\cdot l}{n}\right\rceil$，记为 $c$。接下来我们需要构造出一组取到下界的序列。不失一般性地，令 $a_{0\sim k-1}$ 为 $1$，那么我们要求环序列 $b_{0\sim n-1}$ 的任意长为 $k$ 的子区间之和 $\le c$。连边 $i\to(i+k)\bmod n$，形成了 $\gcd(n,k)$ 个长为 $\dfrac{n}{\gcd(n,k)}$ 的置换环，我们将前 $\left\lceil\dfrac{l\cdot\gcd(n,k)}{n}\right\rceil$ 个置换环上的所有位置上填 $1$，那么对于一个长为 $k$ 的区间，每一置换环上均有恰好 $\dfrac{k}{\gcd(n,k)}$ 个位置在该区间中，所以该区间的和不超过 $c$。在运算中会出现一些取整上的问题，需要精细实现一下。时间复杂度 $O(n)$。 **** ### [[2023 NOI模拟 Day28] 算数](http://192.168.102.138/JudgeOnline/problem.php?cid=1990&pid=2) 给定 $n$ 个整数 $a_{1\sim n}$，你需要构造 $k$ 个整数 $b_{1\sim k}$，再对每个 $i\in[1,n]$ 构造一个只包含 `+,-,*,(,)` 与 $b_{1\sim k}$ 中数的算式，使得其结果为 $a_i$。要求对于每个算式，整数 $v$ 在其中的出现次数不超过其在 $b_{1\sim k}$ 中的出现次数。当 $k\le 12$ 时，你可以获得测试点的全部分数，否则获得 $\dfrac{\max(20-k,0)}8$ 的分数。 $n\le 100$，$1\le a_i\le 10^8$。 **** 令 $v=\max a_i$。一个直接的想法为选择所有的 $2^i$，将每个 $a_i$ 直接二进制拆分。该构造中 $k=\left\lfloor\log_2v\right\rfloor$，可以获得 $15$ 分。 **考虑到我们只用了加法，不妨想想如何利用乘法**。依旧尝试二进制拆分的思路，由于题目的要求，我们需要令每个二的幂只在算式中出现不超过一次。**考虑折半**，令 $t=\left\lceil\dfrac{\left\lfloor\log_2v\right\rfloor}{2}\right\rceil$，构造出 $2^0\sim 2^{t-1}$ 以及 $2^t$ 和 $2^t+1$，将 $\forall j\in[0,t)$ 按照 $a_i$ 中是否存在位 $2^j,2^{j+t}$ 分类，每一类分别乘上对应的系数，可以省去 $0,1$。该构造中 $k=\left\lceil\dfrac{\left\lfloor\log_2v\right\rfloor}{2}\right\rceil+2$，可以获得 $72$ 分。我们使用二进制的原因为每一位上只存在 $0,1$，无需再乘上一些数，而若使用 $b$ 进制拆分，我们还需要加入 $2\sim b-1$，直接进行 $b$ 进制拆分只能得到 $k=\left\lfloor\log_bv\right\rfloor+b-2$，并不优。 **考虑到我们只用了加法和乘法，不妨想想如何利用减法**。目前的瓶颈为需要加入所有的 $2\sim b-1$，若某一位上的数为 $r$，那么若在此位进一位并在这一位使用减法，我们便可将其系数绝对值变为 $r-b$，于是我们也能将这部分贡献折半了。该构造中 $k=\left\lfloor\log_bv\right\rfloor+\left\lfloor\dfrac b 2\right\rfloor-1$，取 $b=9$ 可以通过。 **** ### [Double Knapsack](https://www.luogu.com.cn/problem/CF618F) 给你两个长为 $n$ 且值域为 $[1,n]$ 的数组 $a_{1\sim n},b_{1\sim n}$，你需要在两个序列中分别选择一个子集，使得他们的和相同。构造一组满足要求的方案。 $n\le 10^6$。 **** 要求和相同可以直接采用控制值域的思路。维护一个变量 $x=0$，接下来： - 若 $0\le x<n$，从序列 $a$ 中取出一个元素，将 $x$ 加上其； - 若 $n\le x<2n$，从序列 $b$ 中取出一个元素，将 $x$ 减去其。注意到有 $2n$ 次操作，即有 $2n+1$ 个 $x$，而 $x$ 的值域只有 $2n$，故其必定重复，直接取出这一段的元素即可。时间复杂度 $O(n)$。 **** ### [生产计划](https://www.luogu.com.cn/problem/P11111) 这是一道交互题。给你一棵有 $n$ 个结点的树，每个结点有点权区间 $[l_i,r_i]$，表示要求结点 $i$ 的点权 $a_i\in[l_i,r_i]$。给出 $q$ 个非负整数 $v_{1\sim q}$，对于每个整数 $v_i$，你需要给出一组点权方案使得该树的最大权独立集为 $v_i$ 或判断无解。为避免输出量过大，有解时你只需要输出任意一组合法解的哈希值。在你输出完所有方案的哈希值后，交互库将会给出 $c$ 次查询，每次查询给出一个整数 $1\le k\le q$，若权值 $v_k$ 有解，你需要给出一组符合你给出的哈希值的方案，否则输出无解。多组数据。 $\sum n,\sum q\le 2\times 10^5$，$\sum c\times n\le 10^6$。 **** 首先考虑判断是否有解。注意到，**若将一个点的点权 $a_i$ 增加一，最大权独立集的权值最多增加 $1$，故有解的权值为一个区间**。分别求出 $a_i=l_i$ 和 $a_i=r_i$ 时的最大权独立集即可求出该区间。我们先令 $a_i=l_i$，则在不断将 $a_i$ 增加到 $r_i$ 的过程中一定能到达每个有解的权值。注意到我们可以以任意顺序增加，即可以要求方案中最多只有一个位置 $p$ 满足 $a_p\ne l_p,r_p$。若直接按照编号顺序增加需要维护动态 DP，这并不优秀。考虑**按照 DFS 序增加**，对于每个 $x$ 求出当 $\text{dfn}(i)\le x$ 时 $a_i=r_i$，否则 $a_i=l_i$ 时的最大独立集，可以直接使用换根 DP 求解。询问时直接找到该权值对应的一段即可。时间复杂度 $O(n+q\log n+cn)$。 **** ### [na12xy](https://www.luogu.com.cn/problem/P11866) 给定一个 $n$ 个节点的树，你有一个 $n$ 个点初始无边的图，点编号从 $1$ 到 $n$，以及一个初始均为 $0$ 的整数序列 $a_{1\sim 12}$。你可以进行任意次操作，操作有如下两种类型： - `1 x y`：把 $a_x$ 赋值为 $y$。需要保证在所有 `1` 操作中，$y$ 互不相同。 - `2 x y`：连接编号为 $a_x$ 与 $a_y$ 的点。需要保证两者均不为 $0$。请你构造这棵树，不能有重边、自环。 $n\le 4\times 10^5$。 **** 朴素的删叶子方法无法完成本题的构造。先考虑 $n\le 2\times 10^3$ 的部分分，即序列长度为 $\lceil\log_2n\rceil$。那么考虑直接求出树的重心 $x$，先令 $a_1\gets x$，然后依次递归构造每个子树，处理每个子树时需要保留 $a_1$。容易发现，只会递归 $\lceil\log_2n\rceil$ 轮，该构造合法。现在需要做到序列长度为 $\lceil\log_3n\rceil$，类似地，我们选取一条链使得链上挂的最大子树大小不超过 $\dfrac{1}{3}n$，这样可以通过依次构造链上点的链外子树构造出整棵树。以重心 $x$ 为根对树做轻重链剖分，选取 $x$ 前两大的子树的重链即可。由于我们实际上在做点分治，时间复杂度为 $O(n\log n)$。 **** ## 交互 ### [[2023 NOI模拟 Day48] 超立方体](http://192.168.102.138/JudgeOnline/problem.php?cid=2032&pid=2) 这是一道交互题。有一棵 $n$ 个结点，形态未知的树，定义 $\text{dist}(u,v)$ 为 $u$ 到 $v$ 路径上结点编号的异或和。你可以给出结点 $u$ 与集合 $S$ 进行查询 $\text{query}(u,S)$，交互库会回答你 $\text{xor}_{p\in S}\text{ dist}(u,p)$ 的值。请在 $Q$ 次询问内求出这棵树。多组数据。 $T\le 10$，$n\le 3000$，$Q=4\times 10^4$。 **** 观察询问次数，目标为 $O(n\log n)$ 次询问。定 $1$ 为根，先用 $n-1$ 次询问求出 $d_i$ 表示 $i$ 到 $1$ 路径上的点权编号的异或和。接下来我们可以根据 $\text{query}(u,v)=d_u\text{ xor }d_v\text{ xor }\text{LCA}(u,v)$ 以在一次询问内求出两个点的 LCA。 **考虑增量求解**，逐个将 $2\sim n$ 插入当前的树，维护已插入的点的虚树。考虑插入一个点 $x$，$x$ 与 $1$ 有四种位置关系： - $x$ 单独成为 $1$ 的儿子，此时加边 $(1,x)$； - $x$ 属于 $1$ 的某个儿子 $p$ 的子树，此时递归处理； - $x$ 在 $1$ 到其某个儿子 $p$ 的路径上，此时断边 $(1,p)$，加边 $(1,x),(x,p)$； - $x$ 在 $1$ 到其某个儿子 $p$ 的路径上的一点 $t$ 的其余子树中，此时断边 $(1,p)$，加边 $(1,t),(t,p),(t,x)$，其中 $t$ 为某个未插入的点。这样我们就得到了一个基于增量法的 $O(n^2)$ 次询问的算法。 **考虑重链剖分**，维护当前虚树的重链剖分，考虑一次跳过一条重链。设当前递归到 $r$ 子树，其中 $r$ 为某条重链的链顶，令 $p$ 为该链的链底。用一次查询求出 $t=\text{LCA}(p,x)$。 - 如果 $t=p$，那么由于 $p$ 为叶子，直接加边 $(p,x)$ 即可； - 如果 $t=x$，那么 $x$ 就在这条重链上，可以二分得到其具体位置； - 如果 $t$ 为未插入结点，那么 $t$ 在这条重链上，同样二分出其位置，令 $x$ 为 $t$ 的子节点即可； - 否则，$x$ 在 $t$ 的轻子树内。再讨论最后一种情况。记 $\text{son}(t)$ 为 $t$ 的轻儿子集合，令 $v=\text{query}(x,\text{son}(t))\text{ xor}_{p\in \text{son}(t)}\ d_p$。我们需要确保此处查询的集合大小为偶数，若其为奇数我们再将重儿子加入其中。对几种情形进行分类讨论可以得到： - 如果 $v=0$，那么直接加边 $(t,x)$ 即可； - 如果 $v\text{ xor }t\in\text{son}(t)$，那么 $x$ 在结点 $v\text{ xor }t$ 的子树中，此时递归处理； - 否则，令 $q=v\text{ xor }t$， - 若 $q=x$，那么存在 $r\in\text{son}(t)$ 使得 $r$ 在 $x$ 子树中； - 否则，$q$ 为某个未插入的点，存在 $r\in\text{son}(t)$ 使得 $r,x$ 均在 $q$ 子树中；可使用同样的方式进行询问判断 $r$ 是否在询问集合中，对集合 $\text{son}(t)$ 进行二分即可。单次插入最多进行一次二分，每个未二分的重链使用常数次查询，于是单次插入仅需 $O(\log n)$ 次询问。时间复杂度 $O(n^2\log n)$，询问次数 $O(n\log n)$，常数较小，可以通过。 **** ### [俄罗斯蓝猫](https://www.luogu.com.cn/problem/P11647) 这是一道交互题。有 $n$ 个在 $\left[0,10^{18}\right]$ 中随机生成的非负整数 $a_{0\sim n-1}$。一组询问可以给出不超过 $2n$ 个二元组 $(x_0,y_0),(x_1,y_1),\dots,(x_{m-1},y_{m-1})$，令 $b_i=a_{x_i}+a_{y_i}$，交互库会给出 $b_{0\sim m-1}$ 从小到大排序后的结果。你可以向交互库提出 $n$ 组询问，唯一确定出 $a_{0\sim n-1}$。为了得到满分，你需要保证询问次数不超过 $2$ 次，且在每组询问中保证 $m<n$，$x_i\ne y_i$，$(x_i,y_i)\ne (x_j,y_j)$。测试点内有多组数据。 $T=20$，$5\le n\le 500$。 **** 数据在大值域中随机，故我们假设 $a_i$ 与 $a_i+a_j$ 均互不相同。由于交互库会将结果排序，所以我们大多情况下只能得到一个集合而无法确定顺序。 **由于询问结果的复杂性，我们从一些简单的结构思考起**。我们发现，如果确定了 $a_0$，那么我们询问一个菊花 $(0,1),\cdots,(0,n-1)$ 便可得出 $a_{1\sim n-1}$ 构成的集合。那么第二次询问我们给出一个环，即 $(1,2),(2,3),\cdots,(1,n-1)$，用和简单处理便可得出 $a_0$，但是我们无法确认 $a_{1\sim n-1}$ 的顺序。仔细思考，发现**如果知道了 $a_1,a_2$ 便可按顺序枚举出 $a_{3\sim n-1}$**，为此，我们将两组询问中的 $(0,n-1)$ 和 $(1,2)$ 交换。直接枚举两个询问中调换的数，需要检查得到的 $a_0,a_{n-1}$ 是否均为非负整数，且能按顺序求出一整个环。求出一整个环需要 $O(n^2)$ 的时间复杂度，但是检查非负整数只有 $1/n$ 的概率通过，故直接枚举时间复杂度为 $O(n^3)$ 且难以跑满，可以通过。 ****