工业垃圾选编 - 洛谷保存站

你还知道你在做工业垃圾啊？———题记

## 2025.6 做题记录

但是从 $\text{2025.5.22}$ 开始记录的。

### 326 uoj889（坐标变换，猫树）

贪心，无可救药。考虑强制钦定每一步的 $y\to y+1$，那么对于第 $i$ 行整体平移 $i-1$ 个单位，也就是做 $(x,y)\to (x,x+y-1)$，此时每一步就是向右或者向右下走一步。此时步数就是 $\Delta y$。

由 $n=2$ 的提示，考虑先对一个询问的第 $x$ 行走到头，记为 $p$。那么下一步决策如果存在，且确实在第 $x$ 行那么就是 $(x+1,p+1)$。否则考虑不在第 $x$ 行，已经下去的情况，此时必然经过第 $p$ 行。考虑直接找到集合 $S\subseteq\{x+1,x+2,\cdots,n\}$ 表示 $(S_i,p)$ 可以被抵达。那么对于每个 $S$ 中的元素递归子问题，总规模是 $\leq 2^n$ 的。问题是如何找到 $S$。首先 $p$ 是容易将所有串接到一起跑 SA 后求 lcp 做到 $\mathcal O(1)$ 的。考虑判定一个 $(x',p)$ 是否可以被抵达，这要求每行有区间，满足 $l_i=r_{i-1}+1$，要求 $s_i[l_i:r_i]=s_x[l_i:r_i]$。那么枚举 $x$，求一个 $01$ 矩阵 $M_{i,j}=[c_{x,j}=c_{i,j}]$。然后暴力就是维护一个长度 $n-x+1$ 的列向量 $V$ 表示考虑了当前的列 $V_i$ 表示第 $i$ 行是否可达，逐列扫，然后每个位置维护一个转移矩阵。使用猫树分治做 $\mathcal O(n\log n)-\mathcal O(1)$ 的区间半群信息维护，只有 $01$ 就可以做到 $\mathcal O(\frac{n^3}{\omega})$ 的矩阵乘法以及 $\mathcal O(\frac{n^2}{\omega})$ 的向量乘矩阵，本题数据范围就是 $\mathcal O(n^2)$ 和 $\mathcal O(n)$。这个信息是一个向量乘矩阵，得到一个新向量，再乘矩阵，所以信息合并是 $\mathcal O(n)$ 的。令 $L\to L+nm$ 表示 SA 处理的字符串总长，这样复杂度可以做到 $\mathcal O(L\log L+n^3m\log m+q2^n)$。

进一步优化掉这个 $2^n$。你发现对于第一步拓展得到的集合 $S_i$，额外做一步它们的 lcp，我们只会保留新的点中可达 $y$ 最远的。这样向右迭代的次数是 $\mathcal O(n)$。复杂度优化到 $\mathcal O(L\log L+n^3m\log m+qn^2)$。

### 327 uoj783（分治，从后往前做）

序列是假的，将这些写成区间之间的关系。维护当前带权区间，如果有与 $[l_1,r_1]$ 相交且权值 $\ge x$ 的区间，那么插入 $(l_2,r_2,y)$，询问最终区间集的权值最大值。直接做是不好做的，问题在于不好处理激活一个区间的限制，尤其说是起始区间一直在变，那么正着直接做难以刻画。观察询问，只考虑权值最大值，所以可以只刻画哪些被激活。

写成图论，初始有 $n$ 个区间作为源点，如果 $u$ 区间可以使得 $v$ 区间触发，那么连 $u\to v$。查询源点可达的最大点。这是一个 dag，所以可以从后往前推，然而源点的信息一直在变，$m$ 的操作序列不变，启发我们直接把 $m$ 个区间对应的可达点的最大值 $f_u$ 求出来。那么后面就离线二维偏序一手就好了。关于求 $f_u$，直接对 $[1,m]$ 的操作序列做 cdq 分治即可。时间复杂度 $\mathcal O(m\log m\log n+(n+q)\log n)$。

### 328 20250521 模拟赛

#### B（转 01 序列）

显然转成 $01$ 序列做，搜索出所有长度为 $n/2$ 的 $01$ 序列，找到所有后手必败的序列，构成一个集合 $S$。那么我们只需要处理出：$l$ 个等价类中有 $k$ 个 $1$ 的方案数 $f_k$，然后我们声称答案是关于 $m$ 的 $\mathcal O(n)$ 次多项式，根据 $f$ 容易对一个 $m$ 的答案计算，最终的答案可以插值得出。计算 $f$ 可以容斥：求左半边必败的序列，右半边后手必败序列的个数求和，然后减去两边都必败的序列个数。那么拉出来两边都有的颜色，对这些颜色搜索，只需要两边求：固定下来若干位，剩下随便填，填出来在 $S$ 的方案数。这个对于两边是独立的。也就是说假设有 $x$ 个两边都有的，复杂度是 $2^x2^{16-x}=2^{16}$。那么两边乘一起就是对的。复杂度没算。

#### C（数位 dp，区间 dp 的优美结合）

考虑从高到低进行数位 dp，对于每一位分开计算贡献。考虑处理出脱离 $l,r$ 的位置 $h_i$，这里 $h_i$ 是任意选取的。那么一个位置如果未被脱离就有很好的性质。如果刻画第 $c$ 位造成的贡献，我们可以找出来所有 $h_i\geq c$ 的连续段，形成了若干段子区间，那么考虑一个 $[l,r]$，其中 $l-1,r+1$ 的贡献可以直接贪心填，对 $A$ 做一个 dp 处理出中间有 $a$ 位任意填，开始是 $b$，最后是 $c$ 的最优代价 $cost(a,b,c)$ 即可。这些子区间随着从高往低的过程会越来越多。

考虑记忆化搜索。当前是 $[l,r]$ 区间的子问题，在第 $c$ 位。显然你会找一些断点，递归到上面的子问题。考虑枚举 $l$ 之后的第一个断点 $x$。$[l,x]$ 作为一个子问题向 $c+1$ 递归，$[x,r]$ 向 $c$ 递归。你加一句 $h_{l-1},h_{r-1}\leq c$ 的限制就好了，这个也比较常见。注意你这里的 $x$ 需要记录一手取值。所以状态还要加一个当前 $l-1$ 在这里的取值作为中间的辅助转移。复杂度就是 $\mathcal O(n^3\lg VB^2)$。

### 329 *uoj659（状态划分）

如果要精确刻画低位变化死路一条，但是考虑找到有用的 $+1$ 操作。

考虑将 $+1$ 变成 $\text{xor}$。观察只查询某一位的值这件事，注意到对于 $+1$ 操作，其对 $t$ 位的影响仅和 $[0,t-1]$ 位的状态有关，并且，如果要影响 $t$，必然先影响 $t-1$。那么找到后面第一个影响 $t-1$ 的 $+1$ 操作，如果操作前 $t-1$ 位的值为 $1$ 就赢了，不然还要接着找。

注意到如果 $+1$ 后，一段前缀都是 $0$，高位保持不变，这是划分子问题的突破口。你发现如果一段前缀都是 $0$ 那么形态很好看。考虑当前是 $[0,k-1]$ 为 $0$，$k$ 为 $1$。那么处理一个 $g_{i,k}$ 表示在第 $g_{i,k}$ 次操作前变成了 $[0,k]$ 全 $0$。假设 $v$ 在 $[0,k]$ 是全 $0$ 的，处理出 $f_{i,k}$ 表示 $f_{i,k}$ 次操作执行前第一次回到了 $[0,k]$ 全 $0$。假设如果已经做到了 $v$ 的最低 $k+1$ 位都是 $0$，那么不断跳 $f$ 就好了。对于 $f,g$ 可以通过子问题递归，按序枚举 $k$ 来求出。$f$ 的跳跃使用倍增即可。然后有了 $f,g$ 之后求 $v$ 极长 $0$ 前缀的上升也是容易的。时间复杂度 $\mathcal O(n(\log V+\log n))$。

### 330 qoj8055（边双）

由于图是连通的，所以 $\max a-\min a$ 事实上就是一个下界，因此就是要构造最小值的情况。考虑图是一个环的情况，直觉上一定是按照 $a$ 排序填，但这样会有两倍极差，那么一个环有解当且仅当 $\max a=\min a$。拓展到任意一个边简单环都是同样的，因此一个边双必须是 $a$ 全部相同的。此时直接对边双缩树就是必须要做的一步。接下来直接假定图是一个树，并且每个点上有点权。以这样的视角判定：找到一个 $n$ 的排列 $p$，满足 $a_{p_i}$ 不降，并且 $[1,i]$ 的所有 $p_j$ 构成一个连通块。但这不够，我们还要求每次连通块拓展的那个叶子，与其连接点 $u$ 满足 $a_u=a_{p_{i-1}}$。你发现这样就充要了。更简洁的判定是：对于 $a_u$ 的极大连通块缩到一起，新图构成一个链。

不妨设 $a$ 构成 $k$ 的排列，值为 $i$ 有 $c_i>0$ 个。假设已经知道了一个点是 $1$，那么把他当根，向下选 $k-1$ 个关键点，互为祖先关系，就可以唯一刻画一个方案。你发现重点在于确定关键点，考虑边 $(u,fa_u)$ 是否可以作为切换的边即可，这个与根无关。令一个边关键当且仅当存在一个 $i$ 使得 $u,v$ 两侧的大小分别是 $\sum_{j\leq i}c_j$ 和 $\sum_{j>i}c_j$。因此我们只需要找到 $k-1$ 条关键边的链。显然这是一个上界，直接对子树 dp 然后 dsu on tree 就好了。时间复杂度 $\mathcal O(n\log n)$。

### 331 qoj8546（答案量级的估计，minmax 复合）

如果你直觉答案很多那你就输了。

考虑转化成一个判定性问题，判定一个 $(a_i,b_j)$ 是否可以成为答案。显然 $(\min(i,j),n]$ 的所有操作类型都可以通过已经确定的一个数值来确定。并且需要 $(\max(i,j),n]$ 的所有 $a,b$ 与 $a_i,b_j$ 的大小关系分别相同。**如果根据 $b_j$ 看 01 就倒闭了。** 依然看 $b_j$，考虑这些针对 $y$ 进行一堆 $\max,\min$ 复合的函数，直接化简这个函数。有一个性质是：

>固定 $l,r$，此时 $f(x)=\max(l,\min(x,r))$ 与 $g(x)=\min(r,\max(x,l))$ 等价。

然后考虑 $f(x)$ 复合 $g(x)=\min(x,r')$，那么得到的是 $f'(x)=\min(\min(r',r),\max(x,l))$，另一个同理。所以你发现只有这个函数的 $l,r$ 的 $b_{l}^{-1},b_{r}^{-1}$ 可能存活。所有位置的 $l,r$ 的维护就是喜闻乐见的线段树维护分段函数复合，这个函数很容易描述，可以 $\mathcal O(1)$ 合并。扫描线 $a_i$ 的值即可。

现在只需要检查 $\mathcal O(n)$ 对 $(i,j)$ 是否合法。还有一个问题是 $[2,\min(i,j)]$ 的操作怎么分配。这个时候转 $0/1$ 就有点道理。按照 $a_i,b_j$ 在 $a,b$ 上划分 $0/1$。我们只需要处理出前面得到的 $(x,y)$ 中对于所有 $(A,B)\in\{0,1\}^2$ 是否有可能使得 $x=A,y=B$。那么同样扫描线 $a$，维护 $x=A$ 时最大的 $y$ 以及最小的 $y$。这个依然重点看 $a$ 的 $01$ 序列，找到最后一个对 $0$ 进行 chkmin 或者对 $1$ 进行 chkmax 的位置 $p$。前面全部是 chkmax 或者 chkmin，这是为了让 $y$ 取到最值。后面到 $\min(i,j)$ 之前的部分根据 $a$ 的 $01$ 进行对应的 chkmax 或者 chkmin。线段树维护所有 $p$ 的结果。显然只需要考虑 $\mathcal O(1)$ 个 $p$ 的位置，即前缀最后一个 $0/1$。因此时间复杂度 $\mathcal O(n\log n)$。

### 332 qoj8542（差分，最值分治）

注意到对于一个序列代价就是 $\sum a_i$。所以找到什么 $a_i$ 是可以被生成的。把问题变成减，那么目标是减到全部相同，判定是否非负。第一目标是变成全相等，首先把序列变成不降的，可以直接从后往前贪心一遍，如果 $a_i>a_{i+1}$ 就在 $i$ 执行 $a_i-a_{i+1}$ 次前缀减，其次再变成相等的，从前往后做一遍即可，只需要保证第一步执行后 $a_1\ge 0$。令 $a_0=a_{n+1}=k$，$k$ 足够大，那么判定条件推一下就是 $\sum |a_i-a_{i+1}|\leq 2k$。

回到原问题，需要加最少的代价使得 $a$ 合法。维护当前的 $c=\sum |a_i-a_{i+1}|$。每次找一个$[l,r]$ 满足 $\max_{i=l}^r a_i<\min(a_{l-1},a_{r+1})$。令 $ans\to ans+r-l+1,c\to c-2$，对 $a_{l\sim r}$ 区间加 $1$。其实不难发现这样的 $[l,r]$ 是极长相等的。提出数值相等事件的合并，随便拿个数据结构维护一下这个以及颜色段，合并只有线性次。时间复杂度 $\mathcal O(n\log n)$。糖了，这样的 $[l,r]$ 只会是笛卡尔树区间，按照区间长度贪心即可，自然满足合并的性质。

### 333 *qoj8543（分析上界，根号）

考虑 $F(n)$ 的上界。构造是 $|S_1|=n$，并且 $S_i$ 都能被 $S_1$ 的一个极长前缀和若干 $S_1$ 的前缀表示，并且要求第一个部分是最长的。于是 $F(n)$ 的上界是 $\sum x_i\leq n,x_1\ge x_i$ 的序列 $\{x_i\}$ 的个数。构造是取 $S_1=\texttt{abbb}\cdots$，按照 $x$ 的字典序从大到小进行排布是可以取到上界的。

考虑计数。枚举 $x_1=k$ 可以得到 $F(n)=\frac{1}{1-x}\sum_{k\ge 1}\dfrac{x^k}{1-\sum_{1\leq i\leq k}x^i}$，$\frac{1}{1-x}$ 是在做前缀和变换，这样提出的是 $\leq n$ 的系数和。化简得到 $F(n)=\sum_{k\ge 1}\frac{x^k}{1-2x+x^{k+1}}$。$k\leq \sqrt n$ 直接背包就好了。$k>\sqrt n$ 考虑转化为 $\sum_{i\ge 0}(-1)^i\frac{x^{ki+k+i}}{(1-2x)^{i+1}}$。$i$ 的上界是 $\sqrt n$ 因此直接维护系数和即可。时间复杂度 $\mathcal O(n\sqrt n)$。

### 334 qoj8552（设置子问题）

速通一下。判定合法每次删最后一行，钦定极长的 $1$ 连续段必须是行的，那么后面的部分必须是列延申下来的，对于这些列在后面就不管了，但是要求每列必须是 $1$ 为一个前缀。这样一个 $n\times n\to (n-1)\times m$ 的矩形。显然这个子问题与外面无关，递归判定即可。注意到选极长的这个唯一，因此具有代表元类似的性质。因为选非极长的就说明后面的那个是列延申的，在末端改成行是不影响合法性的。改成计数是容易的，把这个缩矩阵的过程做 dp，复杂度 $\mathcal O(n^2)$。

### 335 *qoj8553（交互）

突破口在于最大子段和如何进行合并。最开始什么都不知道因此只能问所有单点的信息。

考虑先做 $n$ 次查询，可以询问出所有数是否 $>0$。这样可以得出每个数的正负，并且可以知道所有正数的具体数值。此处将 $0$ 视为负数。

考虑将正负的颜色段合并，其实在启示我们做一个类似于线段树结构的查询。如果查询一个正负正的段 $x,y,z$，假设两端的值为 $a,b$，且返回了 $R>\max(a,b)$ 的结果，那么负数段的总和为 $R-a-b$，这种情况下中间的负数段构造前面都是 $0$，最后一个是 $R-a-b$ 即可，因为 $xy,yz$ 都是只取正数部分，否则会中间都取，显然对于任意一个负数段内部这样构造都是正确的。

在后续的分析中，如果两个段合并查询的结果比两者的和都要大，则将两端进行合并。那么上述操作会将正负正合并为一个正，此时和更大。

如果 $R=\max(a,b)$ 就说明中间的和 $\leq-\min(a,b)$。为了消除 $\min$ 的影响，直接取出当前等价正数段中最小的 $a_i$ 的位置 $p$。对于 $lst_p,p,nxt_p$ 中间的部分进行询问。如果可以合并就进行合并，否则两端都不能合并，说明 $\min(|a_{p-1}|,|a_{p+1}|)\ge a_p$。那么后续任意跨过这三个元素的子段中，要么三个全被覆盖，要么三个全不被覆盖。这启发我们进行合并。不妨将 $a_{p-1}$ 直接等效于 $-a_p$，那么这三个就直接合并为 $a_{p+1}$。用两次操作减少了一个负数段，而负数段只有 $n/2$ 个，因此总操作次数 $\leq 2n$。时间复杂度 $\mathcal O(n\log n)\sim \mathcal O(n^2)$。

### 336 *qoj8554（括号匹配）

模拟操作还是太难了，找一下刻画形式。找一个 bot 和洞的一个匹配，那么只需要满足括号匹配形成的区间只有不交或包含关系即可。操作顺序也是显然的，从底往上逐渐剥去括号树的叶子。但是我们需要最小化叶子的数量。

然后这个你也找不到什么贪心的策略，你刻画数列 $a$ 是考虑 $[1,i]$ 的子段然后加入 $i+1$（记得你 pkuwc d2t2 怎么死的吗），因此要设计针对前缀的状态。那么就是你逐渐扫序列来考虑匹配状态。$f_{i,j}$ 表示考虑到数轴的 $i+0.5$，有 $j$ 个区间向 $[i+1,n+1]$ 找匹配。还要再记录一个 $i+0.5$ 的 bot 是否向后匹配。一个状态向后转移就考虑 $i+1$ 的匹配以及 $i+1.5$ 的 bot 的匹配。复杂度 $\mathcal O(n^2)$。

### 337 20250524 模拟赛

#### *A（状态数压缩，凸函数）

观察一个乌龟的行动，一定是最后停在了某一点 $u$ 上，然后考虑所有点到根的路径并，这些边如果不在 $u$ 到根的路径上则会走 $2$ 次，反之为 $1$ 次。因此容易有一个状态设计是 $f_{u,i,j}$ 表示 $u$ 子树内有 $i$ 个乌龟进入，恰好 $j$ 个不出来。可以做到 $\mathcal O(nm^3)\sim \mathcal O(nm^4)$。此时缩减状态数量，考虑固定 $i$ 那么 $j$ 依旧有很多；但是固定 $j$ 之后 $i$ 直接贪心取最小的即可，就是子树合并上来的最大 $j$ 与子树 $c_i$ 的 $\max$ 取较大值。这样状态数就是 $\mathcal O(m)$。然后打表观察到这玩意固定 $j$ 之后是凸的，因此直接闵可夫斯基和做子树合并即可。时间复杂度 $\mathcal O(nm)$。

#### B

大模拟。

#### C（qoj6837，虚树，定期重构，分块）

令 $sub_{u,0/1/?}$ 为 $u$ 子树中 $0/1/?$ 的数量，$anc_{u,0/1/?}$ 为 $u$ 祖先中 $0/1/?$ 的数量，均不包含 $u$。

考虑最优方案的性质：一定满足对于填问号的两个位置，如果形成祖先关系，一定满足：不会出现祖先出现填 $1$ 而后代填 $0$，否则可以调整，在不影响别的位置的情况下交换而变的更优。考虑这种直接设初始 $?$ 都是 $1$，然后从上往下调整 $?$ 是否变为 $0$，就有一个调整的值是 $f_u=sub_{u,1}+sub_{u,?}-anc_{u,0}-anc_{u,?}$。显然初始贡献就是 $\sum_{a_i=0}sub_{u,1}+sub_{u,?}$，令这些是 $\sum g_u$，然后加上所有 $?$ 位置的 $\max(f_u,0)$ 的总和事实上就是正确的，这是因为中间跳掉一定会算少。

考虑怎么修改，每次修改可能会使得 $u$ 祖先的 $g$ 加减 $1$，祖先或后代的 $f$ 加减 $1$，可以考虑定期重构。那么取出包含时刻 $0$ 的若干关键点，间隔为 $B$，那么处理出时刻 $[i+1,\min(q,i+B)]$ 的涉及的点构成的虚树，然后在这个大小 $\leq 2B-1$ 的虚树上我们可以对原树分为 $\mathcal O(B)$ 块，在重构时给一个重标号就行了。那么我们每次会修改 $\mathcal O(B)$ 个块，对其更新并重算贡献。显然对于 $g$ 由于不涉及取 $\max$ 所以可以直接打 tag，只需要记录块中 $a_i=0$ 的数量即可。注意到加减 $1$ 是很好的性质，那么对于一个块我们可以预先计算一下 $\Delta=x$ 的贡献，$x$ 显然只有 $[-B,B]$，可以后缀和预处理。这样平衡一下是 $\mathcal O(q\sqrt n)$ 的复杂度。

### 338 P9983（贪心，ds 优化）

**【Solution 1】**

显然 $q$ 是没什么用的，每次都重新拉出来做。令 $k$ 是定值。有一个类似于 [【ZR NOIP2024 模拟 Day 10】建造军营](https://ng.zhengruioi.com/problem/2956?cid=1727) 的 dp，可以使用长链剖分优化，使用 odt 以及线段树维护这个东西是能过的，复杂度 $\mathcal O(nq\log n)$。

**【Solution 2】**

上面那个不能要了。考虑特殊性质，类似于在 [hba 看到的题](https://www.luogu.com.cn/problem/P8428)，直接贪心，每次找到当前为白色的且深度最大的点 $u$，对其 $k$ 级祖先进行操作，暴力删除子树中为白色的点。可以做到 $\mathcal O(qn\log n)$。进一步拓展这个贪心策略。设每个点离最近白点的距离是 $d_u$，每次任意定根后找到最深的未被染色但最终为黑的点 $u$，找到一个深度最小的可以覆盖 $v$ 且 $d_v\ge k$ 的 $v$，对其染色后，将所有距离 $v$ 不大于 $k$ 的点全部染黑。正确性在于找到 $w=\text{lca}(u,v)$，那么 $w$ 子树可以被全部覆盖，并且 $dep_v$ 更小是不劣的。直接做是 $\mathcal O(qn^2)$ 的。

上数据结构优化这个做法。考虑怎么找 $v$，可以枚举 $w$。其实只需要找满足 $w$ 最浅的点即可，此时这样对应的 $v$ 就是最浅的。因为如果不是最浅的，你就把认为最浅的对应的 $v$ 改到这个上，$w_1,w_2$ 形成祖先关系所以正确。对于一个 $w$ 找到最浅的 $v$ 使得其合法，显然操作后 $w$ 子树都会被删掉，这样的 $v$ 必然确定，容易预处理出所有 $f_w$，这就要求 $dep_u-dep_w+f_w\leq k$，$f_u-dep_u$ 是在祖先链上形成单调性的，对应的 $w,v$ 可以直接二分。

这就转化为以下问题：固定 $k$。封锁一个点 $u$ 以及其 $k-$邻域；查询一个 $u$ 是否被封锁。树剖的思路是对 $u$ 的祖先链进行查询，修改 $u$ 就对其祖先链修改，类似于 [CCO2024] Summer Driving。但是这个不如点分树直接做好。时间复杂度 $\mathcal O(nq\log n)$。

### 339 山东省集三轮 D1T2（分块，整块的定期重构，扫描线）

qoj11109。

对横轴进行扫描线，那么只需要支持：区间 $+1$，区间 $-1$，查询有多少个位置的点值是 $m$ 的倍数。

直接按照 $\sqrt n$ 的块长进行序列分块，散块的重构是平凡的。考虑对于一个整块，每被修改 $m$ 次就进行一次重构，对于每个块维护一个桶 $cnt_i$ 表示模 $m$ 为 $i$ 的元素个数，那么询问可以快速回答。空间的问题就直接转置维度，逐块进行处理，重构的时候将之前的点逐个撤销掉即可，因为点是离散的，但是值域比较大。时间复杂度 $\mathcal O(\frac{n^2}{m}+n\sqrt n)$，空间复杂度 $\mathcal O(n+m)$。重构是因为，你不能计入实际上值为 $0$ 的。

### 340 qoj8948（01 博弈，构造等效的简单情况）

显然最后一个删除的点是一个叶子，那么我们只会关心叶子节点的颜色。Alice 的目标就是删除尽可能多的 $1$ 叶子节点，Bob 是删除尽可能多的 $0$ 叶子节点。

考虑双层菊花的特殊性质。那么删除掉这个子树的根之后，所有叶子可以以任意顺序删除，此时 Alice 一定不会在迫不得已之前去删这里剩下的 $0$，Bob 反之。里面一定是轮流删除 $0,1,0,\cdots$，根据先手决定。直到剩下一种颜色时，另一个人一定不会主动操作这个。所以考虑一个子菊花内部 $0,1$ 叶子数量 $c_0,c_1$ 的关系即可。当 $c_0>c_1$，Alice 不会主动删除 $u$，等价于 $u$ 为 $0$，下面有 $c_0-c_1$ 个 $0$，因此可以向上归纳这个结构，直接挂在根作为 $c_0-c_1+1$ 个 $0$ 叶子，这是**等效**的；当 $c_1>c_0$ 反之亦然。

考虑 $c_0=c_1$ 的情况，先操作者一定不优。注意到这样的点满足子树中其叶子数量必然是偶数，可以留到最后根据 $n$ 的奇偶性处理，如果原来的 $n$ 为偶数那么这个点等效于 $0$，否则等效于 $1$。从下往上逐渐缩菊花就是对的。实现上直接写一个 dp 来刻画所有儿子即可。时间复杂度 $\mathcal O(n)$。

### 341 qoj6794（凸优化）

直接给出结论：存在一种最优方案使得其减法操作均在加法操作前面执行。证明考虑 $01$ 可以让一个位置变成 $0$ 后不动，$10$ 不行，使用相邻的 $+1,-1$ 交换可以使用调整不变影响。令一个数减了 $c_i$ 次，那么对于最终 $b_i\neq 0$ 就需要恰好有 $d_i=b_i-a_i+c_i$ 次加法操作，最优操作次数显然是 $\sum \max(d_i-d_{i-1},0)+\sum \max(c_i-c_{i-1},0)$。对于 $b_i=0$ 要求 $c_i\ge a_i$，对于 $b_i\neq 0$ 不加证明的我们由最开始结论可以推得 $c_i<a_i$。

考虑使用 dp 解决这个锤子问题。我们发现 $d$ 是不重要的，$c$ 是重要的，因此设计 $f_{i,j}$ 表示考虑了前 $i$ 个位置，$c_i=j$ 的最小代价。转移需要对 $b_i$ 是否为 $0$ 进行讨论，$b_i=0$ 相当于推平一段前缀为不合法的，$b_i\neq 0$ 是推平后缀。类似于 WC2025 T3，我们尝试维护差分，发现这个形式就很好，进而可以发现斜率仅在 $\lbrace 0,1,2\rbrace$ 之中，直接维护拐点即可。时间复杂度 $\mathcal O(n)$。

### 342 *qoj9698（区间 dp）

难点在于分析操作的性质与过程。区间 dp 的一个 trick 是带上 $l-1,r+1$。

首先给出这样的结论：对于一种最终序列，存在至少一种操作方案使得其操作 $1$ 对应的 $c$ 按照操作顺序内部不降。证明考虑相邻两个 $c_1>c_2$ 的操作 $1$，将中间的 $\text{chkmax}$ 操作移动到前面，并且将次序换为在实际操作序列相邻的 $c_2,c_1$。然后考虑对操作序列分段，每个操作 $1$ 前面附带了一些内部顺序无关紧要的操作 $2$，可以看作对这个 $2$ 操作提供的 $c_2$ 以及后面黏着的 $c_1$（如果存在）取 $\min$，然后对这个值 $\text{chkmax}$。然后考虑转化为，一个操作 $2$ 可以转化为不执行要求其黏到一个 $c$ 比他小的操作 $1$ 上面。你发现这么做其实操作 $2$ 已经没有用了，我们可以只关心操作 $1$。结论即为把所有操作 $2$ 的 $c$ 变为所有比 $c$ 小的操作 $1$ 的值之一或者不变后，先操作最小的全局 $\min$ 操作，然后操作所有操作 $2$，有多少种最终序列。你这样做的好处是，一个操作 $2$ 可以被统计多遍。在一个后缀考虑就不需要看重复计入的情况。

那么可以考虑区间 dp，大概率要带上一个值域。$f_{l,r,x}$ 表示仅考虑 $[l,r]$ 的原数列，有多少种最终 $a'_{l-1}<x,a'_{r+1}<x$，并且 $a_l\sim a_r$ 均 $\ge x$ 的最终序列。因为这样只需考虑被 $[l,r]$ 包含的操作 $2$。每次可以枚举中间放上的操作，然后做一些容斥的操作。我们考虑倒序扫描 $x$ 进行 dp，记上一轮得到的 $f$ 是 $g$，我们求解这一轮的 $f$。我们记录 $h_{l,r}$ 为选出一些 $g$ 的子段，不要求左右端点连续，这些 $g$ 的乘积的和，此时不被这些子段覆盖的就是需要在本轮进行覆盖。我们求该轮的 $f_{l,r}$ 时可以用容斥的技巧，我们要求所有位置都被覆盖，枚举第一个不被覆盖且无法被覆盖的位置，初始令 $f_{l,r}=h_{l-1,r+1}$，然后减去这些 $f_{l,i-1}h_{i,r+1}$ 的乘积即可。

时间复杂度 $\mathcal O(n^4)$。

### 343 qoj8951（倍增）

显然问题等价于 $m=1$，原因是模 $m$ 不同余的位置一定不干扰。给出一个简洁的代价计算式，可以消除等待带来的影响：$ans=\sum_{i=1}^n\max_{j\leq i}(t_j-jT)+\sum_{i=1}^n iT-t_i$，需要保证 $t$ 递增。

修改可以直接平衡树上做楼房重建，但是复杂度 $\mathcal O(mq\log^2n)$，常数看上去就很大。 注意到修改独立，令修改位置为 $p$，修改后序列为 $[1,k-1],p,[k,p-1],[p+1,n]$。对于一个区间，只需要整体加上斜率为 $-T$ 的直线，再做整体平移。那么问题形如：前侧 $\max$ 为 $x$，对于一个 $[l,r]$ 询问整体平移 $y$ 后的前缀最大值之和。不需要上线段树，直接二分找到第一个 $\ge x$ 的位置，后面容易计算。直接倍增可以 $\mathcal O((n+mq)\log n)$。

### 344 *qoj8952（二分，随机化）

固定 $n$，错排排列的分布趋近于 $\frac{1}{e}$。对于当前所有未确定位置随充分多次，最小值为 $y_1$，然后考虑枚举一个位置是否为 $x$，对于未确定位置一直随充分多次，最小值结果为 $y_2$。如果 $y_2>y_1$ 就说明确实是 $x$。

进一步优化这个想法，每次随一个非错排的排列 $p$，我们尝试找出任意一个归位的位置。这个是可以二分的，因此对于 $[l,mid],[mid+1,r]$，每次随机选择一侧进行随机打乱，直到询问结果小于打乱前，那么这个归位位置就在这一侧。优化，可以用已确定元素替换区间中的元素，这样二分每层只会查 $1$ 次而不是期望 $2e$ 次。询问次数 $\mathcal O(n\log n)$。

### 345 *qoj8956（容斥）

类似题目：[[集训队互测 2023] Permutation Counting 2](https://qoj.ac/problem/7759)

考虑对 $p_i>i$ 先做容斥，就是钦定 $k$ 个位置满足 $p_i\leq i$，求出这样的答案后进行二项式反演。假设已经确定好容斥的集合是 $S$，考虑如何统计满足 $S$ 的序列在降低数上的贡献，可以尝试在内层再做一次容斥。

对于一个统计对象 $q$，钦定一些位置满足 $q_i>q_{i+1}$，有一个好处是，如果一个大于段连接两个 $S$ 中的元素，那么后面那个元素的限制是没有用的，因为前面的上界更严，并且根据大于的限制，前面的大于后面的。但另一个问题是，如果出现 $i\notin S,i+1\in S$ 但钦定了 $p_i>p_{i+1}$，那么是很难计数的。因此我们要求 $i\in S$ 的位置必须有不钦定 $p_i>p_{i+1}$。但是这样就会数漏，因此加入钦定 $p_i<p_{i+1}$ 的限制。那么一个大于可以由不限制减掉容斥得到。那么限制的形式容易被确定为：若干条 $<<<>>>$ 的链，峰顶的限制为 $t_i$，有限制的从左往右递增。从小往大填，前面的数可以继承，因而方案数是容易从左往右计算的。那么对于一个 $S$，可以这样从右往左考虑，如果 $p_i$ 所在的连通块已经被确定峰值，那么 $p_{i-1},p_i$ 的关系只能是未限制或者 $p_{i-1}<p_i$，反之是 $p_{i-1}>p_i$ 或者未限制。这些贡献需要拆开计算。

因此每次确定一个 $<<<>>>$ 的段 $[l,r]$，按照 $r$ 的顺序进行 dp，枚举峰顶的位置 $p$，那么 $[p+1,r]$ 就可以任意被钦定。当然直接枚举很劣，对于 $<,>$ 分步进行转移即可做到 $\mathcal O(n^6)$。

### 346 *qoj9911（构造）

下面的拓扑序都是题面定义的反序。也就是说“根节点”是 $p_1$。

类似于 [DFS Order 3](https://qoj.ac/problem/6503)，容易得到 $k$ 为叶子数量的解法，构造直接取 dfs 序，考虑剥叶子的过程，假设一个点 $u$ 的邻居是 $u_1,u_2,\cdots,u_k$，除了 $u_k$ 都是叶子节点，那么在所有 $u_1\sim u_{k-1}$ 的序列中，都将 $u_k$ 放在这些后面就好了。这样可以得到整整 $61.74$ 分。这启示我们删叶子是个很好的方向。对于一个菊花图，对于根跑 $2$ 次，第二次的叶子顺序与第一次完全相反，这样就是唯一的。

将第一个序列重新标号为 $1\sim n$，得到的树满足以 $1$ 为根情况下 $1\leq fa_i<i$。考虑去掉叶子之后形成的树 $T'$，对于 $T'$ 的所有叶子进行 dfs，将这些点设置为关键点。那么搜索到关键点时，优先遍历 $T$ 的所有叶子节点。如果要区分关键点周围的叶子节点，考虑在遍历到它奇数次时正序，偶数次时反序。

### 347 P6778（莫队二离，top cluster 树分块）

转化为求区间内任意两个点之间的 lca 深度之和，以及 $\mathcal O(n)$ 次路径加以及 $\mathcal O(n\sqrt q)$ 次路径求和。进行 top cluster 树分块，那么一条路径就是所在簇上界点到根路径以及这个点到所在簇上界点的路径。那么对于一个簇打标记，簇内暴力跳。在收缩树上暴力跳即可。

这个很像分块平衡做的操作。处理出 $near_u$ 表示到所在簇路径的最近点，$top_u$ 表示所在簇的上界点。路径分为 $u\to near_u\to top_u\to Root$。处理出簇内到上界点和，整体簇路径加的次数，当前簇路径权值和即可。时间复杂度 $\mathcal O(n\sqrt q)$。

### 348 qoj10307（贪心，凸优化）

考虑固定一些人有 $a+b$ 的贡献，另一些只有 $a$ 的贡献，设两类人分别有 $x,y$ 个，若 $x=0$ 或 $y=0$ 那么平凡，非平凡情况要求 $x>1,y\ge 1$，考虑一对 $(x,y)$ 合法当且仅当 $x+2y+1\leq m,x\ge2$。固定 $x,y$ 后可以直接做贪心，按照 $a$ 从大到小排序后，一定是一段前缀一定产生 $a$ 的贡献，选取一些产生 $b$ 的贡献。因此枚举这个顺序中最后一个选仅 $a$ 的位置 $p$，那么 $[1,p)$ 必然是 $a$ 或者 $a+b$（前面出现 $0$ 那么 $p$ 可以往前移动到这个位置）；$(p,n]$ 中必然是 $a+b$ 或者 $0$。枚举 $p$ 可以做到 $\mathcal O(n^2)$ 的复杂度。

进一步考虑枚举断点然后合并两端的过程，显然选前 $k$ 大求和的函数是凸的。观察 $x+2y\leq n-1$ 的限制，我们已经确保了 $x+y=p$ 是定值，因此确定 $p$ 后合并两端的函数，考虑两端就是 $p$ 左边有 $A$ 个位置决定取 $-b$ 的贡献，$p$ 右边有 $B$ 个位置取 $a+b$ 的贡献。从大到小排序后取前 $n-1-p$ 项与 $0$ 取 $\max$ 后求和即可。那么扫描线枚举 $p$，写一个数据结构：固定 $p$，增删物品，取前 $k$ 项的和，直接使用对顶堆维护容易做到单 $\log$。时间复杂度 $\mathcal O(n\log n)$。

### 349 qoj10308（消环，树的拓扑序）

考虑判定 $G_1,G_2$ 等价，容易想到消环的过程中，最大边权对应的边必须一样，判定的充要条件就是所有点简单环，最大边权的边相同。仙人掌启示我们考虑点双，仙人掌告诉我们一个点双中会有若干边等价，但是你肤浅了，因为你考虑改成一个 $m$ 元不等式组，列一下容易发现限制是一棵树。比如考虑 $E=\{(1,2,5),(1,3,4),(1,4,1),(2,5,3),(4,5,2)\}$，此时将边视为重构树上的一个点，令边 $e$ 的父亲为，覆盖 $e$ 的所有边简单环中最大边权对应的 $e_1$ 中，$w_{e_1}>w_e$ 且 $w_{e_1}$ 最小的 $e_1$，如果 $e$ 是覆盖所有边简单环中最大边权的，那么 $e$ 就是一个根节点，如果 $e$ 是割边那么就是一个孤立点。

令这个重构树为 $T$，你发现答案就是 $T$ 的拓扑序个数，而森林的拓扑序是很容易计算的，最终答案就是 $m!$ 除以所有子树大小的乘积。

问题在于求出 $T$。其实容易想到按照边权从小到大加入边（因为从大到小删除疑似不太有救），而边简单环具体长什么样并不需要关心，我们只需要关心 $e_1,e_2$ 是否可以通过一个点简单环串起来。$e$ 的父亲的寻找变为：每次加入一条边 $e_1$，考虑所有未被标记的 $e$，如果 $e,e_1$ 满足前述条件，则对 $e$ 标记并令 $fa_e\to e_1$。你发现这一步事实上就是在维护点双，可以圆方树刻画。标记的话，将这个东西挂在点双上，每个点双维护待选集合。直接维护圆方树，变为以下的问题：动态维护一个森林，每次 $\text{link}(u,v)$，或者将 $u,v$ 路径缩成一个点。但其实缩树之前的样子就是一个最小生成树的边有用，所以先把这个求出来，然后暴力缩路径就是容易的。使用并查集维护最小生成树的求解以及圆方树路径缩点的操作，使用一个并查集维护方点的合并即可。时间复杂度 $\mathcal O(n\alpha(n))$。

### 350 qoj8630（树链剖分，字符串，平衡修改询问）

直接树剖，那么目标串分为完全在一个重链内部的和跨过两条重链之间的部分。后者直接暴力考虑这条边左右 $\mathcal O(k)$ 个位置，暴力提取出来做哈希，总量级是 $\mathcal O(k\log n)$，而预处理询问串的 $\text{fail}$ 之后，这是均摊 $\mathcal O(1)$ 的，因此这一部分的复杂度是 $\mathcal O(n\log n)$。前者，我们直接对于所有 $u$ 的 $k$ 级祖先仍与 $u$ 一条重链的 $u$ 维护其到 $ktkanc(u)$ 路径的哈希值 $h_u$，那么每次修改就影响 $\mathcal O(k)$ 个 $h_u$（一段截取前缀出来的向下平移，与其等长），此时考虑询问是一个区间内等于目标值的 $h_v$ 个数。使用线段树套哈希表或者哈希表套平衡树，这个是很大常数的 $\mathcal O(n\log^2n)$。

目标是单 $\log$，而询问总数线性可以接受。考虑优化，注意到它只会影响 $\mathcal O(\min(\log n,k))$ 条重链。将树链剖分转为维护树上差分，每个点维护一个集合 $S_u$ 表示 $u$ 到根路径割出来的这些重链，所有字符串的哈希值以及出现次数。那么每次修改就是子树区间插入或删除，可以使用标记永久化的线段树维护。这样每次查询只需要查询 $\mathcal O(1)$ 个 $S_u$ 中 $c$ 的出现次数。时间复杂度 $\mathcal O(n\log n)$。

### 351 qoj10003 / zr3205（扫描线，线段树维护 dp）

做过 noiwc t3 还能不会这个题？三个小时取之。

考虑在平面直角坐标系上刻画，$x$ 轴为时间，$y$ 轴为鸽子的速度。 每只鸽子是一条长为 $T$ 的横线。一只选出的鸽子不能完全在没选出的鸽子集合下方，即这条横线至少有一段上方的鸽子全都被选出。显然对 $x$ 可以进行离散化，保留 $\mathcal O(n)$ 个点，即 $t_i,t_i+T$ 的集合。

我们可以设 $h_i$  表示第 $i$ 秒速度最大的没选出的鸽子的速度。 刻画 $(i,h_i)$ 对应的直方图，那么一只鸽子被选出当且仅当其对应的横线没有被直方图完全覆盖。稍微弱化条件，任取一个直方图，一只鸽子被选出当且仅当其对应的横线没有被直方图完全覆盖，反过来也能对应一个策略。因此考虑对直方图进行 dp。

设 $dp_{i,j}$ 表示考虑前 $i$ 秒，而第 $i$ 秒直方图的高度为 $j$ 最大的收益。再维护 $F_{i,j}$ 表示在 $i$ 和 $i+1$ 秒均会出现的，速度 $\leq j$ 的鸽子可爱程度之和。$A_{i,j}$ 表示在第 $i$ 秒新出现的，速度 $>j$ 的鸽子可爱程度之和。我们希望每条横线的收益只在第一次出现时统计。这个 dp 可能有问题，因为一条线有可能被多次统计贡献。 我们注意到所有鸽子的出现时间是一样的，因此可以强制直方图的“峰”长度至少为 $T$，这样就只会统计一次了。

更进一步的，只有在一条线出现时才会出现 $j>k$ 的转移，即直方图抬高，以规避这只鸽子的贡献。在一条线消失时才会出现 $j<k$ 的转移。即直方图降低，尝试喂到更多鸽子。这些 tag 都比较好合并，可以用扫描线+线段树实现，时间复杂度 $\mathcal O(n\log n)$。

### 352 zr3203（根号分治）

有一个做法是中间插入互不相同的分隔符，利用 SAM 建立反串后缀树，转化为求 $\sum_{l\leq i<j\leq r}len_{\text{lca}(p_i,p_j)}$，对于 $len$ 进行树上差分转化为链加链求和。这个是洛谷 P6778，可以做到 $\mathcal O(n\sqrt n)$，需要使用莫队二次离线。但是这个很垃圾，首先不如改成 trie 树。

对于每个询问 $[l,r]$，设点 $u$ 子树内有 $cnt_u$ 个 $[l,r]$ 中的串结尾，那么答案为 $\sum \binom{cnt_u}{2}$。 设 $siz_u$ 表示 $u$ 子树内的串结尾个数，$\sum siz_i=\sum |S_i|=L\leq 10^5$。考虑根号分治，对于 $siz_i\ge L$ 的点，可以暴力统计贡献。这部分可以离线下来减小常数。 对于 $siz<L$ 的点，这部分点对只有 $\mathcal O(L)$ 对，$q$ 次查询贡献，可以扫描线+分块处理。 这部分也不用存点对，只用在扫描到这个点时遍历其在 $dfn$ 序上前后 $L$ 个点，空间复杂度线性，时间复杂度 $\mathcal O(L\sqrt L)$。

### 353 *zr2838（三等分 trick）

atcoder pakencamp-2022-day2 Habatu。

考虑时光倒流，即断点为 $b$ 按照从小到大考虑，每次走到权值和较大的一方，并保留这个区间，询问最终区间。

一个自然的想法是，设当前区间的权值和为 $s$，考虑能否快速跳到第一个权值和 $\leq\frac{s}{2}$ 的区间。类似于 [[集训队互测 2023] 区间切割](https://qoj.ac/problem/7980)，找到带权中点类似状物，不过选择的是带权三等分点 $x,y$，即最短后缀使得和 $\ge \frac{s}{3}$ 以及最短前缀使得和 $\ge \frac{s}{3}$。那么每次如果 $b$ 的最小值在左区间或者右区间那么一定不影响，因为另一半的和一定更大。这样直到第一次 $b$ 的分割点落在了中间。这样值域区间至少缩到原来的 $\frac{2}{3}$。使用线段树维护找 $lmid,rmid,nxt$，时间复杂度 $\mathcal O(n\log n\log V)$。

### 354 qoj8602（逆用 Hall 定理转化问题）

首先求出 $\text{highbit}$ 的最大值 $k$，显然 $x$ 的下界是 $2^k$，$a_i<2^k$ 的贡献恒为 $1$，而 $a_i\ge 2^k$ 的贡献为 $1/2$，分别为用 $x$ 消除或者用 $x=2^k$ 以及 $x=a_i-2^k$ 消除。那么我们需要选择一个 $x\ge 2^k$，答案就是 $|a|+x+\sum[a_i>x]$，显然查询到 $\text{highbit}$ 之后可以对于不同的 $k$ 分开做，直接莫队可以过一些分。这有点二分图匹配的味道，那么考虑转化成 Hall 定理的形式，那么就要求最大化 $\sum[a_i\leq x]-x$。那么左部图 $a_i$ 对右部的 $j\leq a_i$ 都连边，这是一个最大匹配模型。注意到直接贪心是正确的，因此从大到小能匹配就匹配即可。我们只需要求出保留最多的左部点点数。

那么就预先跑扫描线，维护 $[1,r]$ 在所有 $k$ 的最大匹配，强制在线就直接可持久化。插入 $a_r$ 之后一定会强制匹配 $a_r$，如果不合法就需要删除一个最小的 $l$ 使得其合法。使用 Hall 定理，维护 $w_i=i-\sum_{j\in S}[a_j\leq i]$。那么要求所有 $w_i$ 非负。线段树维护就是 $\mathcal O((n+q)\log n)$。

### 355 *CF1023G（图论转化，缩状态，维护 dp 差分）

这个并没有太好的性质，考虑高复杂度做法，并使用**图论进行刻画**。对于两个限制的鱼考虑能否共用，将一个限制拆成 $f_u$ 个点，若 $x,y$ 可以共用就等价于 $\text{dist}(p_x,p_y)\leq|d_x-d_y|$。那么对于 $x,y$ 连边的就将 $d$ 较小的连向 $d$ 较大的。答案就是这张 dag 上的最小链覆盖。利用 dilworth 定理可以转化为求最大权反链（同一个限制拆出来的要么全选要么全不选）。

这样在树上进行 dp，需要考虑两个不同子树的合并。这样需要额外记录两个时间信息：$x=\max(d_v-\text{dist}(u,p_v))$ 以及 $y=\min(\text{dist}(u,p_v)+d_v)$。那么两个子树的合并就需要满足以 $u$ 为 lca 的路径全部不合法。 两个子树 $v_1,v_2$ 的 $x,y$ 先与 $u$ 合并，得到区间 $[x_1,y_1],[x_2,y_2]$，就要求 $y_2>x_1$ 且 $y_1>x_2$。合并结果是 $[\max(x_1,x_2),\min(y_1,y_2)]$。进一步，摒弃区间的状态。$u$ 合并儿子的多个区间时，显然要求这些区间有公共点。而你是从下往上合并的，这些区间并到一起后是左端点平移 $-w$，右端点平移 $w$，考虑简化限制条件。不记录区间长什么样，而是记录一个**公共点** $x$。如果将所有情况刻画，那么一定是不会漏下最优解的（交点可能卡在两个相邻整数之间，只需要把所有时间和边权乘 $2$）。状态就是 $f_{u,x}$。那么就是所有子树内的限制走不到 $(u,x)$，$(u,x)$ 走不到所有子树内的限制。先令状态中不考虑 $u$ 的贡献，转移考虑 $subtree_u\cup\{u\}$ 对 $fa_u$ 的贡献。

转移就是考虑所有边 $(u,v,w),fa_v=u$，其转移是 $f_{u,x}\to f_{u,x}+\max(f_{v,y}),y\in[x-w,x+w]$；以及 $f_{v,d_i}+c_i\to f_{u,x},x\in(d-w,d+w)$。

这个子树内形成了 $\mathcal O(\text{size}_u)$ 段，因此使用类似于维护分段函数的方法做这个 dp。可以维护差分，对位加就直接使用启发式合并。扩张 $k$ 的操作可以分开维护正负，另外开一个堆维护距离，暴力进行合并相交的正负段即可。时间复杂度 $\mathcal O(n\log^2n)$。

### 356 P9150（断环成链，暴力，scc）

固定起点时，走到的路径显然是确定的，即 $p_i,p_{p_i},\cdots$。而判定能否拓展，只需要维护当前走到的点形成的 scc，直接看所有反向边，此时每个 scc 都是一个区间。每次尽量走直到走不了。这样容易得到 $\mathcal O(nm)$ 做法，问题在于枚举起点。

这个过程很大程度上需要我们做暴力，不是很好简化，所以一个方向是减小暴力的次数，加强一点刻画。也就是说，我们需要联立不同起点间的信息。

不妨设 $i\to p_i$ 形成的置换环大小为 $n$，否则在两个环之间边没用，而环的子问题独立。考虑断环成链，得到一个长度 $2n$ 的序列。那么就有若干限制形如：如果 $[x,y]$ 均被激活，那么 $[x,y]$ 可以合并为一个 scc。另一方面，令一个点到达的最远点为 $to_i$，也即第一问的答案。那么你发现如果 $i$ 在 $j$ 前面，并且 $i$ 可达 $j$，那么就说明 $i$ 至少可以到达 $to_j$，另一方面 $[i,to_i]$ 是只有相离和包含的。这启发我们倒着做整个问题，结合前面的性质，如果跳到 $i$ 时可以直接到 $to_i$，那么我们可以保证扩张的次数是 $\mathcal O(n)$，就是你的过程形如：判定 $p+1$ 是否可达，如果可达则 $p\to to_{p+1}$，否则结束过程。使用序列并查集维护 $[i,to_i]$ 的合并。再在每个等价类里面维护一下。考虑 $p$ 是否可以走到 $p+1$，暴力扫出边实在是太笨了！事实上只需要找最大的 $k<p$ 使得 $(k,p)\in E$，然后看是否在最后一个 scc 之中，预处理之后这是 $\mathcal O(1)$。scc 的合并显然也是可以暴力做的。倒着扫的过程中建立反图，如果当前无法合并就暂时存着，否则直接合并 scc。使用并查集维护 scc 的合并关系。时间复杂度 $\mathcal O(n\alpha(n))$。

### 357 qoj6408（计数背包的撤销）

我们考虑判定一个集合是否可行而不是对操作序列计数。考虑最后选中的集合是 $S$，那么 $S$ 可以成为前 $|S|$ 大当且仅当 $\min(S)\ge\max(U\setminus S)$。$v$ 的限制很神秘，考虑分类讨论 $|S|$ 与 $v$ 的关系，不难发现 $|S|< v$ 与 $|S|\ge v$ 本质相同。$|S|\ge v$ 时一定不会给 $S$ 之外的投票，此时 $\max(U\setminus S)$ 是确定的。考虑令 $\max(U\setminus S)=k$，那么对于所有 $i\in S$，令 $b_i=\max(0,k-a_i)$，那么每次操作就是对 $v$ 个 $b_i$ 执行 $b_i\to b_i-1$，问能否让 $b_i\leq 0$。这个操作成功当且仅当 $\max(b_i)\leq m$ 且 $\sum b_i\leq mv$。

按照 $a_i$ 排序进行 dp，枚举 $\max(U\setminus S)$ 所在的元素为 $k$，那么 $>k$ 的 $b_i$ 均为 $0$，但是前面的 $S$ 中的元素必须有 $\sum b_i\leq mv,\max(b_i)\ge m$。在排序时后面那个就是限制一个区间 $[l,r]$ 的数可以被选入 $S$，对这段区间执行背包 dp 即可。注意到背包是可撤销的，可以从小到大扫描 $k$，$l$ 双指针跑。视 $n,m,V$ 同阶，时间复杂度 $\mathcal O(n^4)$。

### 358 云斗三轮模拟赛 D1T2（set）

不难将问题转化为：$op=1$ 倒序扫操作序列，$op=2$ 正序扫操作序列。每次若 $p=a_i$ 则 $p\to b_i$；若 $p=b_i$ 则 $p\to a_i$。维护 $lst_{i,0/1},nxt_{i,0/1}$ 分别表示上一个或者下一个与 $a/b_i$ 颜色相同的位置 $j$；对着 $2m$ 个点，$lst,nxt$ 分开连边，此时连出来的是一棵树。对于操作一，set 维护前驱后继可以快速找出 $\mathcal O(1)$ 个修改的位置。考虑倍增查询答案。需要支持：改变某个点的父亲或者查询 $k$ 级祖先。使用 $10$ 级算法 lct 可以做到 $\mathcal O(n\log^2n)$。但是 lct 明显是不必要的。注意到这张图是一车链，直接用 set 维护这些链即可。时间复杂度 $\mathcal O(n\log n)$。

### 359 agc022E（贪心，增量判定）

策略是尽量删除 $0$。对于 $0$ 连续段根据其奇偶性保留到 $1/2$ 的长度。如果缩完后长度为 $1$ 且两端均为 $1$，那么显然只能缩到一起，那么就再与两边进行合并。若缩完后长度为 $2$，只能吃掉一个旁边的 $1$ 之后再与两端合并。把这个东西改成增量维护可以做的事情，维护一个栈即可。时间复杂度 $\mathcal O(n)$。

### 360 *P9151（自动机计数）

考虑本质不同序列计数的贪心，对于一个计数对象，假设其可以由 $[x_1,x_2-1],[x_2,x_3-1]\cdots$ 操作而来，那么在多个可以生成它的方案中，选取 $x$ 序列字典序最小的。

将操作转化成删字符是另一个角度：那么就是删掉 $2$ 个相邻的不同字符；选择 $3$ 个相邻的相同字符，删掉 $2$ 个。不难得到一个推论：若 $l\leq r-2$ 且 $s_{l}=s_{l+1}$ 或者 $s_l=s_r$，并且 $r-l$ 为奇数，那么区间 $(l,r]$ 可以被删空。

这个题的思想是自动机匹配。本质不同序列计数可以考虑自动机状物，每个点处理出边 $nxt_{i,0/1}$ 表示后面第一个 $s_j=0/1$ 并且 $(i,j)$ 可以被删空。可以说明这样计数的串可以被全部匹配上，这是因为考虑最小的 $x$ 与另一个对象不同的位置 $i$，匹配串同样位置是 $i<j,s_i=s_j$ 且 $i,j$ 奇偶性相同，我们说明不会出现 $A-j-B$ 合法但 $A-i-B$ 不合法。等价于证明：所有 $k$ 满足 $s[j+1:k]$ 可以删空，必然满足 $s[i+1:k]$ 可以删空。运用上述引理容易证明。由于出边对应字符不重复，所以每条路径自己本身互不相同。这样就说明了“不重不漏”。

接下来构建自动机。考虑处理 $nxt_{u,c}$，找奇偶性不同的出边。令 $s_u=0$，那么 $1$ 的出边就是最小的 $v>u,s_v=1$；$0$ 的出边是最小的 $v_u,s_v=s_{v-1}=0$，手玩一下发现这个确实是对的，因为中间无法产生 $0$ 相邻。注意确认 $0,n+1$ 的连边，这样转化为 $0\to n+1$ 的路径计数。对于 $n+1$ 的连边，$(u,n+1)\in E$ 当且仅当 $[u+1,n]$ 可以被删空；对于 $0$ 的连边，将这个转置，然后选取两种字符各自最靠前的。显然对于任意 $u\leq n$ 都会存在 $(u,u+1)$ 的出边。

总时间复杂度 $\mathcal O(n)$。

### 361 *CF2115E（背包的贪心优化）

显然这个问题有一个做法是直接背包，但是有一个贪心是取性价比最大的物品，这个在一定程度是对的，因此可以结合两者来优化复杂度。有一个结论是，找到性价比最大的物品 $(w_1,c_1)$，那么存在一个最优解使得不是这个物品的个数 $\leq c_1$。否则考虑调整法，将一个当前物品的可重集合 $S$ 替换成 $\frac{\sum_{i\in S}c_i}{c_1}$ 个 $w_1$，由鸽笼原理，必然存在 $S$ 使得 $\sum_{i\in S}c_i$ 是 $c_1$ 的倍数。令 $\max(c_i)=C$，这样做背包的重量范围就是 $C^2$。

令 $f_{u,v,x,0/1}$ 表示当前在 $u$，最优性价比在 $v$，使用了 $x$ 的代价，是否已经经过了 $v$ 的最优答案。由于背包的范围是 $C^2$，那么复杂度是 $nmC^2$，不可接受。一个方向是减小重量范围。考虑询问的 $r<2C^2$ 时直接暴力调用 $mC^2$ 的朴素背包对应的答案；$r\ge 2C^2$ 时用另一个 dp 来做，考虑**引入选取负数个的概念，本质上是改变了 dp 的顺序。** 沿用上述的 dp，但是通过引入选取 $-x$ 个物品 $v$，我们可以将重量范围控制在 $[0,C]$。在 $r$ 足够大的时候，一个最终加上的选大量 $v$ 的方案，会与一个 dp 的真实方案结合，使得对应的 $v$ 选取非负个。询问的时候直接枚举 $v$ 即可，这样复杂度 $\mathcal O(nmC+mC^2+nq)$。

### 362 CF2115D（线性基，贪心）

CF 当晚睡觉前会了这个题，但是已经过了一个小时了而我通过了 $0$ 个题遂睡觉。

显然问题等价于 $x$ 有一个初值，而 $b_i=0$。向线性基中插入 $a_i$，最高位开始贪心的过程启发我们对于每个基记录最晚加入的，这样这个位置的操作者就决定了这一位，因此倒序插入即可。最终从高往低扫线性基，那么每个基对应 $c$ 的位置决定了 $x$ 对 $x\oplus base_i$ 取 $\min$ 还是取 $\max$。总时间复杂度 $\mathcal O(n+\log V)$。

### 363 CF2115F1（根号重构）

考虑定期重构，一个定期重构的套路是，按照 $B$ 分块的话那么序列被切割为 $\mathcal O(B)$ 段整段。由于这个题强制在线，那么只能动态分裂每一段，但是对于一个整段的事件一定是相同的。对于每个段维护一个操作队列，表示插入的元素，另外维护一个值表示是否反转这一段。对于 $1/2$ 操作就维护当前所有段的队列，直接更新即可。对于操作 $3$ 显然我们只需要打一个标记表示是否被删除，等待到询问时再处理。

另一方面，我们可以定位到在这段正在操作的之前，这个位置在之前时间块中所有经历的段，具体来说维护一个排列表示这个置换即可。那么按序扫所有时间块中它的段。对于这个段所有被插入的元素，直接遍历这个队列，如果被打删除标记那么就删除这个元素，如果没有那么就是这个的答案。注意到总插入次数是 $n\sqrt n$，而一个元素只会被删除一次，插入和删除次数相同因此复杂度正确。视 $n,q$ 同阶，时间复杂度 $\mathcal O(n\sqrt n)$。

### 364 *qoj4878（扫描线，贪心）

今天重新感受了一下这个题，有点神秘的，补充一下官方题解的贪心的说明。

根据题解可以得出关于一个 $p$ 的完整贪心做法及其正确性理解，下面考虑从 $p$ 到 $p+1$ 的变化过程。首先说做法，从 $p$ 到 $p+1$ 的过程会加入一些区间和删除一些区间，分别用两个线段树维护左边的 $s_i$ 和右边的 $s_i$。删除的区间就在左边的线段树中将其删掉，这里权值为之前扔给这个区间的左边做题时间；同时也需要在右边的线段树中将其删掉，权值为在右边剩余的权值。也就是说，我们彻底删除掉这个区间对两棵线段树的影响。

加入的区间就在右边的线段树中将其加入进来即可。然后在右边线段树上进行单个 $p$ 的操作，根据题解中的势能分析得到复杂度为 $\mathcal O(n\log^2 n)$。

> 关于这个做法的正确性，只需要说明在 $p$ 时和完整贪心做法等价的前提下，$p+1$ 也和完整贪心做法等价，就可以归纳证明其正确性。
>
> 考虑从 $p$ 变成 $p+1$ 的过程，如果没有删除操作，右边的 $s_i$ 不会变得比原来更小，因为都是加法操作。所以之前需要扔到左边的现在仍然需要扔过去，而左边可行的选择又没有变多，所以之前贪心扔过去的显然现在还是最优的。
>
> 有了删除操作之后，右边的 $s_i$ 可能变小了，但我们的删除操作可以完全删除这些区间的影响。也就是说，之前放到左边线段树这些区间的那些做题时间会原封不动的还回去，所以也是没有问题的。可以在还回去之后重新贪心找到它们应该去的左边位置。

### 365 *云斗三轮模拟赛 D1T3（Bell 数，子树合并转 dfs 序）

咋回事，这个都不会。

> 考虑 $n$ 个点 $m$ 条边的无向图。定义一个生成树的权值是所有边权的乘积，求所有生成树的权值和。保证图的最长点简单路径的点数 $k\leq 7$。$n,m\leq5\times10^4$。

考虑确定一个根 $R$，求出 dfs 生成树，那么深度 $\leq k$ 且没有横叉边。先考虑子树合并怎么 dp，维护子树内边向上的联通情况，记录 $u\to R$ 路径通过子树内选取边划分出的连通块情况。这样复杂度是 $\mathcal O((n+m)\text{Bell}(k)^2)$。

可以按照 dfs 序进行 dp。按照 dfs 序加点，这样的好处是变成插入，而不是合并。考虑把已经加入的点标成黑色，加入一个点 $u$ 时显然其到根路径上全部都是黑的。因此可以决策向上连黑点的划分情况，并且子树中所有点都是白的，黑白点之间的边的上端点仅在于 $u\to R$ 的路径。所以直接记录 $u\to R$ 路径在黑点之间的边形成的连通块即可。这样枚举一个状态往下一个加入点的贡献，时间复杂度 $\mathcal O((n+m)\text{Bell}(k))$。

### 366 P8949（构造，逆向操作）

考虑 $d=2$ 的做法，不妨设 $S$ 的编号是 $1,2,\cdots,n$，并且可以得到一个置换，可以在 $T$ 上作用。首先考虑一步变成链的树的性质，我们猜测取根为 $1$ 即可，并且 $1$ 必须是一度点。你发现以 $1$ 为根后只需要 $fa_i<i$ 即可。所以我们希望 $T$ 做一步变成这样。那么我们倒过来，以 $n$ 为根进行点分治，每次取子树中连通块中编号最大的点连接即可保证 $fa_i>i$，那么这样做时 $1$ 是叶子，倒过来就全对了。实现上从小到大加点即可。

拓展到正解，$d$ 提示我们 $S$ 是操作的重点。有类似于[这个题](https://www.luogu.com.cn/problem/T552828)的事情，可以找一个中间状态 $P$，执行 $T\to P,P\to S$。那么取 $P$ 为一条链的情况。我们希望对 $S$ 做逆操作使得 $S$ 变为一条链。这样做是因为，逆向与正向操作并不等价。那么我们需要在 $d-2$ 次操作内完成 $S\to P$ 的逆过程。考虑与最大度数有关的操作，将 $\text{deg}=d$ 的节点标记为关键节点，取一个一度点作为根，对于关键点 $u$ 在子树中找一个叶子 $v$，连边 $(u,v),(v,fa_u)$ 并且断开 $(v,fa_v),(u,fa_u)$。启发式合并维护叶节点集合，时间复杂度 $\mathcal O(nd\log n)$。

### 367 qoj4791（贪心）

不妨设这些数是 $[1,n+m]$ 互不相同的数。注意到从第二列表插入第一列表的数的位置并不需要关心，我们只需要将最开始第一列表的数删除到有序，那么求出值域上所有在第一列表位置为极长有序的区间 $[l,r]$ 作为最终保留的区间，对于其分开求解，答案取所有情况的最小值。

考虑 $[1,n+m]$ 的数列 $b$，所有状态分别为 $0/1/2$，$b_i$ 表示 $i$ 已经被删除，仍在第一列表，仍在第二列表。我们只需要令第 $l-1$ 个 $1$ 以及第 $r+1$ 个 $1$ 变成 $0$ 即可。令序列 $a$ 表示初始第 $i$ 小的 $1$ 对应的 $[1,n+m]$ 中的值。定义六个变量 $f_0,f_1,f_2,g_0,g_1,g_2$ 分别表示左侧区间 $[1,a_{l-1}-1]$、中间区间 $[a_{l-1}+1,a_{r}-1]$、右侧区间 $[a_{r+1}+1,n+m]$ 的 $1,2$ 的个数。那么对于第奇数个轮次：如果 $f_2=0$ 立刻令 $a_{r+1}$ 变为 $0$，否则 $f_2$ 减小一个，然后需要令某个 $g_i$ 转化为 $f_i$；对于第偶数个轮次：如果 $f_0=0$ 立刻令 $a_{l-1}$ 变为 $0$，否则 $f_0$ 减小一个。 然后需要令某个 $g_i$ 转化为 $f_i$。

我们提前枚举首先删除的是 $a_{l-1}$ 还是 $a_{r+1}$，整个过程分成两个阶段。 针对两个阶段，我们分别采用贪心策略，分别不能转化 $g_0\to f_0$ 以及 $g_2\to f_2$。

总时间复杂度 $\mathcal O(n)$。

### 368 qoj7509（盒's trick）

对 $01$ 串的相邻同项操作时可以对奇数位取反，改成交换相邻两项。显然拆贡献到每条边上，贡献是前后个数差的绝对值。那么随便组合数算一下。可以使用 [LNOI2022] 盒的 trick：对于 $\sum_{i=0}^{lim}\binom{A}{i}\binom{B}{C-i}$ 使用莫队维护 $lim$ 以及 $A,B,C$ 的变化量。

但是这个题上树了，相当于所有询问的区间都是子树的 dfs 序区间，我们需要移动两个指针 $l,r$，显然根据那个 trick 每次是 $\mathcal O(1)$ 的，但是我们希望最小化指针移动次数。这个 dsu on tree 一下是 $\mathcal O(n\log n)$。

### 369 *P9062（支配对，欧氏距离的平面网格化）

考虑找支配对。距离很小的时候直接枚举每个点的周围即可。欧氏距离可以平面网格化，即找一个近似值处理掉，因此取 $L=d,d^2,d^3,\cdots$ 作为边长划分整个平面，假设当前边长是 $d^k$，考虑在相邻的网格中找支配对。这样划分类似于猫树分治，对于一个线段寻找一个划分点的思想。

直接扫描线加入每个点 $i$，然后对于它所在的块，直接将周围 $9$ 个块中的点加入支配对，并且删除所有与 $i$ 距离小于 $d^{k-1}$ 的点。但是想到这个反而需要从证明的角度入手：考虑一个 $p<q<r$，满足 $(p,r)$ 是支配对时 $p,q$ 之间必然满足的限制，容易发现 $\text{dist}(p,q)<d^{k-1}$ 时可以让 $(p,r)$ 在更小的 $k$ 被计入。也就是说，我们要删除更小的 $k$ 已经统计过的贡献。

于是每个时刻每个块中两两距离一定 $\ge d^{k-1}$，在 $d$ 较小只会有常数个。在 $k$ 固定时支配对大小线性，因此总共有 $\mathcal O(n\log V)$ 个支配对。使用分块平衡大量修改与查询，扫描线回答询问，时间复杂度 $\mathcal O(n\log V+q\sqrt n)$。

### 370 *P9109（网格图最长路，分治）

LCS 问题是一个经典的网格图最长路模型，对于这个模型的经典处理方式是分治（感觉只能主动去想分治）。首先对 $S$ 的询问区间做猫树分治，那么对于询问枚举 $[l,mid]$ 在 $T$ 串的断点，那么对于前缀和后缀的匹配是独立的子问题，如果能询问上 $\mathcal O(1)$ 求出这个子问题那么就是 $\mathcal O(mq)$。

因此我们需要快速求解：给定字符串 $a,b$，多次询问 $\text{LCS}(a[l:r],b[1:k])$，在上述子问题中，$b$ 是 $S$ 串的分治一半边，$a$ 是全体的 $T$ 串。我们只需要在 $\mathcal O(|a||b|)$ 的时间完成预处理即可。放到网格图上，相当于每个斜边有边权 $[a_i=b_j]$，每次可以向右或者向下，求保留前缀行以及中间列的最长路。直接套用网格图最长路分治可以获得惊为天人 $\mathcal O((n\log n)^2)$ 做法，获得整整 $34$ 分。

令上述问题的答案是 $F(l,r,k)$。在网格图上画画就容易猜到，扫描线 $r,k$。我们希望走新加入的斜边，增加的 $F(l,r,k)$ 的 $l$ 具有一定性质，我们猜测其形成区间。固定新的 $r,k$ 之后，如果新修改的是 $r$，那么是一段 $l$ 的前缀 $+1$；如果新修改的是 $k$，那么是一段 $l$ 的后缀 $+1$。可以用 $\mathcal O(|a||b|)$ 的时间预处理修改的断点。将断点都递推出来后再处理原问题只需用差分得到 $F$。时间复杂度 $\mathcal O((n\log n+q)m)$。

### 371 20250606 联考 B（贪心，转置维度）

考虑先写一个 dp 完成一个序列 $b$ 的判定，那么就是 $f_{i,j}$ 表示前 $i$ 个数中 $j$ 结尾的 $k$ 间距子序列的最大长度，转移就是继承 $f_{i-1,j}$ 并且令 $f_{i,a_i}$ 是 $f_{i-1,j}+1,j\in[a_i-k,a_i+k]$ 中取 $\max$。直接维护第二维，线段树可以维护出对于给定的 $a$ 当前的所有 $f$。问题即为往后接尽量多的数，使得最终的 $f$ 依然符合所有数 $\leq l$。往后面加数时只需要考察对于 $f$ 的变化。策略一定是选取 $f'_i$ 最小的位置进行修改。因为每次是 $+1$，所以操作最小值的位置不会影响非最小值的位置。也就是说先操作一定不劣。

快速模拟这个过程。我们考虑扫值域，每次从提升 $f'$ 的最小值由 $p\to p+1$ 来考虑。如果当前 $f'$ 的最小值已经超过 $l$ 就寄了，否则考虑所有能变化的点即最小值的所有位置的集合 $S$，使用若干极长连续区间 $[l_i,r_i]$ 刻画，而一个点会影响周围 $2k+1$ 个 $f'$，所以任意 $r_i-l_{i-1}>2k$，那么操作独立。

提升一次时一个区间大概就是 $\lceil\frac{r_i-l_i+1}{k+1}\rceil$ 的时间使得 $f'$ 全部上升，然后由于关键 $f'$ 值的值域是小的，所以可以拿 ```std::set``` 维护所有区间进行快速维护，合并以及拆区间时的代价都是容易计算的。瓶颈在于线段树以及区间的维护，时间复杂度 $\mathcal O(n\log n)$。

### 372 *P8361（调整，欧拉回路）

考虑恰好为 $n$ 弱化成找到最小的 $n$，那么发现 $n\to n+1$ 只需要在中间找到一个向前进位的位置插入 $B-1$ 就可以做到。大胆猜测最小的 $n$ 不大，事实上在本题数据范围下 $n\leq 9$。那么考虑从小到大判定每个 $n$ 是否可行。暴力想法是枚举对应关系的排列和进位然后解出 $a$，虽然可以通过但是太烂了。

考虑找出对应关系的排列 $p$ 构成的置换环。先解决只有一个环的情况。不难发现，环中只有 $4$ 种本质不同的元素：A：不需要进位，也不提供进位的元素；B：需要进位，但不提供进位的元素；C：不需要进位，但提供进位的元素；D：需要进位，也提供进位的元素 。

合法环的一个显然的必要条件是环上各元素的进位次数和枚举的进位情况中的进位次数相等（$|C|+|D|=|B| + |D|$），且至少存在一个 B 类或 C 类元素。或许可以直接构造，但更直接的思路是枚举进位情况以及 $a_1$ 跑欧拉回路。

对于排列存在多个环的情况，实际上本质不同的元素仍然只有上述提到的四种。 我们只需要在枚举单个环的情况时记录 $|B| −|C|$，多个环拼接的过程实际上是做一个无限背包。时间复杂度 $\mathcal O((2^nn+\frac{n^4}{\omega})\sum B)$。

### 373 20250606 联考 C（绝对值函数的性质）

与 $h_0$ 相连接的若干边将环划分为了若干子问题，暴力是预处理 $f_{l,r}$ 表示 $l,r$ 通过被其包含的边做到 $[l,r]$ 也就是内部所有点连通的最小代价，转移枚举 $l,r$ 是否有边再枚举断点，$f$ 的预处理是 $n^3$ 的，可以接受。枚举一个与 $h_0$ 相连的点，可以断环成链做 dp，复杂度 $\mathcal O(n^3q)$。

注意到权值函数的性质，$h_0$ 相连的边不会大于 $2$ 条，原因是这样至少存在两个与 $h_0$ 大小关系相同的点与之相连，如果这两个相邻，这样可以给这两个点相连，然后再选一个点连向 $h_0$；如果不相邻，推一下发现不劣。我们可以将 $h_0$ 按照所有 $\mathcal O(n)$ 个 $h$ 进行分段，然后考虑中心点的连边方式来进行统计答案。如果中心点连了一条边，可以分讨其是较大值还是较小值。对于每种情况，均可以写成：如果 $h_0<x$ 答案就和 $h_0+y$ 取 $\min$。最后二分一下即可。

最终时间复杂度 $\mathcal O(n^3+q\log n)$。

### 374 *20250528 模拟赛 B（lgv 引理）

AT_tenka1_2013_final_e 加强到 $n=27$。

先用扫描线求出所有的连边，视作有向边后显然满足图是一张 dag。可以用拓扑排序加 dp 求出每个点开始连边到最右侧每个蓝点的方案数。

看到连线不交的限制，容易想到 LGV 引理，但是 LGV 引理只能处理点不交的情况，这里还要求平面上边不交。不妨考虑什么时候点不交并且边会相交，注意到只有起点横坐标相同才能相交，所以只有左侧的相邻的红点可能有交。考虑边 $(x_1,y_1)\to (x_2,y_2),(x_3,y_3)\to(x_4,y_4)$，两个红点连边有交当且仅当 $y_1=y_3+1000,y_1=y_4,y_2=y_3$，且 $y_3$ 到 $y_1$ 之间没有黑点。

暴力枚举最左侧红点的第一条连边，然后使用 LGV 引理计数，时间复杂度 $3^nn^3$，可以通过原题数据。假如对于长度为 $k$ 的有交连续段，需要 $f_k$ 次搜索，那么 $n$ 个红点的最坏复杂度就是 $\sum f_i=n,\max \prod f_i$。直接搜是 $f_k=\binom{k+2}{2}$。有一种 $f_k=k$ 的剪枝方法：考虑最低的点，如果选择下面两条边，那么不会出现边交叉情况，如果选择了最上面的边，为了点不交，之后所有点都要选最上面的边。则根据第一次选择最上面的边的红点，一共有 $k-1$ 种情况（最高的点不用分两类），加上全不选共 $k$ 种情况。最劣的复杂度是 $\mathcal O(3^{n/3}n^3)$。

### 375 CF1852E（贪心，区间关系讨论）

首先刻画 $a,b$ 等价的条件。对于每个元素求出出现的最小，最大位置，这样得到每个值有一个区间 $[l_v,r_v]$。对于一个值 $x$，如果存在 $y>x$ 使得 $l_y<l_x\leq r_x<r_y$，那么 $y$ 被支配。显然对于所有未被支配的 $v$，必然有 $b_{l_v}=b_{r_v}=v$。

考虑未确定的元素，观察样例发现会出现 $a$ 中未出现的元素 $v$，显然 $v$ 的区间会被已有区间支配掉，因而如果有多个 $v$，可以让所有区间取并集，将这些 $v$ 合并成它们最大的，因此结论是：最多出现 $1$ 个未在 $a$ 中未被支配掉的元素集合 $S$ 中，出现的元素。因为我们只关心出现的元素的区间，所以如果这些区间都确定了，未确定的 $b_i$ 会填写所有覆盖 $i$ 中的区间的权值最大值。

先把 $v$ 不存在的情况的 $b$ 求出来，然后再计算一个 $v$ 带来的变化量最大值。直接的想法是枚举 $v$，但是被谁支配就很困难。注意到对于一个支配 $v$ 的 $x$，$v$ 的取值一定是最大的 $v<x,v\notin S$，否则调大不劣。另一方面，$v$ 的 $[L,R]$ 也是好确定的，反证就是如果存在 $l_y<L<l_x\leq r_x<R<r_y$ 那么本身就是不合法的。那么在 $L,R,v$ 确定时其贡献也容易计算，扫描线加线段树维护，时间复杂度 $\mathcal O(n\log n)$。

### 376 CF2084F（整体限制的观察）

考虑判定 $b$ 是否是好的，先考虑没有限制 $1$，我们可以做置换使得最终是 $1\sim n$。那么每次操作一定是删除极长归位前缀 $[1,k]$，找到 $k+1$ 的位置 $r$，执行操作 $[k+1,r]$。这一归位过程唯一，我们只需要保证这个过程能否成功执行，也就是说每一步的 $[k+1,r]$ 必须满足还原成 $b$ 的值后 $b_r$ 是最小值。本身是没什么性质的，但是这个相当于将 $a$ 的一些逆序对变为顺序对。也不难注意到一个顺序对不会变成逆序对。因此充要条件就是所有 $i<j,a_i<a_j$ 必须满足 $b_i<b_j$。

由上述限制不难求出一个未出现值 $v$ 在 $c$ 的出现范围限制 $[l_v,r_v]$，树状数组求即可。$c$ 非零部分不合法是无解的。接下来我们宣称直接按照 $l$ 扫，每次填 $r$ 最小的，加上如果有多个就填 $v$ 最小的，这个贪心过程是正确的，因为 $c$ 内部的贡献会被自然满足。时间复杂度 $\mathcal O(n\log n)$。

### 377 20250607 模拟赛 B（暴力，复杂度分析）

加法和异或结合起来没什么性质。注意到 $b_i,k$ 不变，因此每个位置产生贡献的 $a_i$ 只有 $\log V$ 个区间。提出这些区间之后，有 $\log V$ 个黑白交替的区间，颜色表示是否有 $1$ 的贡献。暴力处理每个位置改变区间的事件，维护其到当前区间右端点的距离 $rem_i$。

每次区间加就是对 $rem$ 做减法，找到 $rem$ 的最小值，判定是否会移动区间，找到会移动的进行修改即可。否则终止过程。移动区间只有 $n\log V$ 次，结合线段树的复杂度 $\mathcal O(n\log V\log n)$。

### 378 20250607 模拟赛 C（后缀树）

> 给定数列 $a,b$ 以及长度 $n$ 的字符串 $s$，定义 $f(l,r)=a_{occ(s[l:r],s[1:n])}\sum_{i=l}^r b_{s_i}$，每次给定 $l,r$ 询问 $\min(f(x,y)),[x,y]\subseteq[l,r]$。$n,q\leq 5\times10^5$。

考虑后缀数组，那么 $f(l,r)=a_{\sum [\text{lcp}(suf_l,suf_i)\ge r-l+1]}(pre_r-pre_{l-1})$，其中 $pre_i$ 是 $b_{s_j}$ 的前缀和。不难想到通过 $height$ 从大到小合并的过程维护一个重构二叉树，其具有 $2n-1$ 个节点，叶子节点代表所有后缀，每次选取两个等价类所在的根进行合并，新建一个节点作为它们的父亲。那么一个节点对应的最小长度是确定的，即父节点的 $height$ 值 $+1$，记为 $k_u$，其出现次数显然就是子树大小，对应的串在 $k_u$ 确定时也是唯一的，因此这个节点的权值就是确定的 $val_u$。

接下来倒序扫描线 $l$，对于每个节点 $u$ 维护最小造成贡献的 $r$，记为 $tim_u$。显然每个节点的 $tim_u$ 随 $l$ 减小而不升。查询即为所有 $tim_u\leq r$ 的 $val_u$ 最小值。修改是，对于 $l$ 的所有祖先，将 $tim_u$ 赋值为 $k_u+2l-1$。显然我们可以维护树上单调栈状物。转化为以下问题：给定一棵有根树，每个节点有权值 $a_u,b_u,val_u$，初始 $a_u=\infty$，保证 $b_u\geq b_{fa_u}$。第 $i$ 次修改 $u$ 到祖先的所有点 $v$ 的 $a_v$ 为 $n-i+1$。支持实时给定 $r$，查询 $\min_{a_u+b_u\leq r}(val_u)$。

直接定期重构可以做到 $\mathcal O(n\sqrt{n}\log n)$。这个根号怎么这么慢，写个平方暴力跟他爆了，95 分跑路，具体来说维护一个树上单调栈状物，只有这些点是有效的更新。为什么有人写这个过了 100 分，真无语。

update：正解是 dag 链剖分，更无语了。

### 379 *P9537（终局状态分析，博弈论倒推）

> 启发就是对于这种摸不着头脑的过程，先分析一下终止状态是怎么样的。

另一个启发是，你要有一定的**感觉**，比如先手很难赢，后手很难赢之类的。

分析最终无法操作的状态，一个必要条件是对面集合大小为 $k$ 时，我方集合两两差值的不同值个数 $m$ 有 $m\leq k$。然而我方集合大小为 $n$ 时，必然有 $m\ge n-1$。一个十分松的条件是如果 $n-1>m$ 那么游戏不会在现在停止。注意到完整的一轮结束后 $|S|-|T|$ 是不变的，也容易得到一个推论，如果初始时 $|S|>|T|+1$，那么先手必胜，因为任意时刻必然满足 $|S|-1>|T|$；同理 $|S|<|T|$ 时后手必胜，第一次操作后任意时刻有 $|T|>|S|+1$。于是只需要考虑 $|S|=|T|$ 以及 $|S|=|T|+1$ 的情况。注意到可以凑出的个数 $m=n-1$ 当且仅当集合是等差数列。若当前集合不为等差数列，那么 $|S|<|T|$ 时就可以继续进行，所以只有等差数列能让他停下。

考虑 $|S|=|T|+1$ 且 $S$ 要对 $T$ 操作时，如果 $S$ 无法操作当且仅当 $S$ 构成的公差为 $d$ 的数列，且 $T$ 的构成是 $kd,k\in[1,|S|-1]$。尝试倒推这个过程，分析一点不变量，注意到最终状态下 $S$ 最大的两个元素必然是无法被 $T$ 合成的，并且首项也一定是 $d$ 的倍数，因此，必要条件是在初始状态中，存在 $t,d$ 使得 $td,td+d$ 是 $S$ 最大的两个元素且 $\max(T)\leq td$，并且 $d\mid S_i,d\mid T_i$。这个也是充分的，因为你合成的数太局限了。

考虑 $|S|=|T|$，先手比较难获胜，执行一步交换先后手之后就会变为 $|S|=|T|+1$ 的情况。一步之后需要满足上述的充分必要条件。

合法的位置，注意到值域很小，因此可以直接枚举 $\min S$ 和 $d$，并 bitset 暴力求出位置。枚举后手集合大小，对答案的贡献是范德蒙德卷积。时间复杂度 $\mathcal O(\frac{n^2\ln n}{\omega}+n\ln n)$。

### 380 20250608 模拟赛 A（减少有效转移）

几乎一样的题目：CF771E。

考虑对 III 类区间设计 dp，扫描线时间的过程中，假设当前时间是 $t$，那么 $r\leq t$ 的所有 dp 的更新是确定的，由于 I,II 类区间的权值均为 $1$，因此每次找后继 $r$ 最小的覆盖就是正确的，具体来说每个 III 类区间都会在上下各自对应当前的结尾时间 $c_i,d_i$。在扫描线的过程中，假设区间是左闭右开的，那么我们会将所有当前结尾 $\leq l$ 的进行转移。

由于总的修改次数很多，且很难有什么规律，因此从减少有效转移的角度考虑。假设考虑 I 类区间，有多个可以转移的，继续利用 I,II 类区间权值为 $1$ 的性质。我们宣称在后续第一行的转移中，只用保留 $f$ 最大的，如果有多个则保留 $d$ 最小的。反证处理，如果一个 $f$ 更小的实现反超，那么需要多选取一个区间。而这在上还是下做这个都是不会更优的。因此在第一行删除这个在后续的转移是不劣的。使用两个 set 各自维护上下的转移，一个大根堆维护当前 $f$ 的最大值以实现插入一个 III 区间 dp 初值的计算。时间复杂度 $\mathcal O(n\log n)$。

根据这个过程，cdq 分治是思维量比较小的做法。

### 381 *qoj10865（贪心，单侧递归）

这种题就是，转化问题，这一步很灵活很考验脑子，然后变成工业垃圾题。

**【贪心策略】**

考虑单组询问如何求答案，假设当前机器人大小为 $k$，把大于等于 $k$ 的小兵看成高的，其他看成低的，并且设每个机器人往后递增子序列长度为 $r_i$，这里的递增子序列长度指的是找到下一个比它大的，如果下一个 $\ge k$ 那么就终止，并且不算后面那个。整个序列会被高的小兵划分成若干段，每段以一个高的小兵结尾。对于每一段，只有击败最后一个小兵才能看到下一段。

你的一个贪心策略为：从前往后击败每一段，对于每段，你只会保留不超过一个最高的低小兵，然后击败这一段高小兵。保留一个最高的低小兵是为了击败这个高小兵能够遮挡住后面的小兵。特别的，假设前面保留的为 $p$，并且后面一段的第一个小兵大于 $p$，那么不需要保留，否则可以保留。对于每个小兵，当它大于之前保留的 $p$，那么就用这个小兵的 $r_i$ 加上 $p$ 是否为 $0$ 更新答案。

注意这个答案不一定是最优的，因为每一段保留的低小兵可能会在导致做高小兵时会额外多看到一个。假设当前答案为 $A$，最优答案不会小于 $A-1$。

接着如何判断答案是否为 $A-1$。首先如果有高小兵的 $r_i=A$，那么一定不可行。对于所有 $r_i=A-1$ 的高小兵，那么在碰到这个小兵的时候一定不能保留额外的 $p$，并且前一位必须是高小兵。对于剩下的高小兵，没有额外的限制。所以在做的时候，只需要碰到 $r_i=A-1$ 的高小兵就清空一下 $p$ ，然后判定过程中是否都不超过 $A-1$ 即可。

**【数据结构优化】**

观察到本质不同的 $k$ 只有 $\mathcal O(n)$ 种，事实上可以离线处理出所有答案，询问进行一个二分即可。

先考虑求 $A$。走每一段的时候你发现这个 $x$ 明显就是一个前侧传入的信息，容易想到单侧递归线段树。从小到大扫描最开始的高度 $k$，然后依次把每个小兵从高的变成低的。记录一下每个子树，如果用左子树的 $p$ 最大值进入右子树更新得到的最大答案以及一些其他信息。

接着判断答案是否可能为 $A-1$，我们只要找到所有 $r_i=A-1$ 的高小兵的位置 $q_i$，那么当我们碰到这些高小兵的时候，$p$ 需要清零。那么等价于对于 $q$ 的每一段，你用 $p=0$ 开始执行贪心策略 中间答案不会超过 $A-1$，对于每一段用线段树解决。注意到随着 $k$ 递增，$A$ 逐渐减小。每次 $A$ 变化时提出所有 $q$ 进行判定即可。

时间复杂度 $\mathcal O(n\log^2n+q\log n)$。

### 382 20250609 模拟赛 A（递归子问题的构造）

> 给定 $p,k$，令 $n=p^k$。构造尽可能多的集合 $S_i\subseteq[n]$ 使得 $|S_i|=p$ 且 $\max(|S_i\cap S_j|)\leq 1$。$n\leq 2000$。

给出一种 $|S|=\sum_{i=0}^{k-1}p^{k+i-1}$ 的构造。

首先考虑 $k=2$ 的做法。我们声称必然可以选出 $p$ 个集合两两不交，不妨设这些集合满足 $S_i=[ip,(i+1)p-1]$。那么我们已经将 $0\sim p^2-1$ 分成了 $p$ 组，我们要求后续的 $S$ 中每组恰好选取一个元素。我们还需要额外给出 $p^2$ 个集合，令第 $i$ 组的元素模 $p$ 的结果是 $a_i\in[0,p-1]$，那么等价于给出后续集合的长度为 $p$ 的序列 $a$，要求任意两个序列相同的 $a$ 最多一个。我们枚举 $a_0=i,a_1=j$，采取循环移位的策略，令 $a_k=((k-1)i+j)\bmod p$。容易发现对于任意两个不同的 $(i,j)$ 对，后续的 $a$ 必然互不相同。

拓展到 $k>2$，我们令每一组的长度为 $p,p^2,p^3,\cdots$，但是组数恒定为 $p$。令长度为 $p^q$，那么可以每 $p^{q+1}$ 个元素划分为一段，每段划分 $p$ 组做类似于 $k=2$ 的构造就做完了。

### 383 ?（数论）

> 给定 $n,m$ 求 $\prod_{x\in[1,m]^n}\text{lcm}(x_i)^{\gcd(x_i)}\bmod 998244353$。$n\leq 10^9,m\leq 2\times10^5$。

对原式施加莫比乌斯反演以及交换求和顺序的操作，容易将答案式化为：
$$
\prod_{y=1}^m\left(\prod_{x\in[1,\lfloor\frac{m}{y}\rfloor]^n}(y\times\text{lcm}(x_i))\right)^{\varphi(y)}
$$
可以拆成计算两个部分的乘积，独立计算，答案就是 $F_1F_2$。

令 $F_1=\prod_{y=1}^my^{\varphi(y)\lfloor\frac{m}{y}\rfloor^n}$ 对于 $y$ 进行整除分块，并处理出 $f_1(x)=\prod_{x\leq n} x^{\varphi(x)}$ 以及 $f_2(x)=\frac{1}{f_1(x)}$ 即可。如果对 $f_1,f_2$ 打表可以做到低于线性的复杂度。

令 $F_2=\prod_{y=1}^m\left(\prod_{x\in[1,\lfloor\frac{m}{y}\rfloor]^n}\text{lcm}(x_i)\right)^{\varphi(y)}$，显然只需要处理：$S(k)=\prod_{x\in[1,k]^n}\text{lcm}(x_i)$。整除分块后只需要求 $\mathcal O(\sqrt m)$ 个 $S(k)$ 的点值。而指数方面只需要求 $\varphi(x)$ 的区间和，拆为前缀和后使用杜教筛也可以低于线性。

问题来到处理 $S(k)$。可以把所有贡献拆到质因子上，计数 $g(p,l)$ 表示有多少序列 $x$ 使得 $p$ 上的最大 $\alpha_i\ge l$，那么 $S(k)=\prod_{p\in \mathbb{P},p\leq k}\prod_{l>0}p^{g(p,l)}$。而 $g(p,l)=k^n-(k-\lfloor\frac{k}{p^l}\rfloor)^n$。所以对于 $p^l$ 进行整除分块，我们关心 $[l,r]$ 内有多少数可以表示为 $p^k$，其中 $p$ 是质数。线性预处理这个函数的前缀信息和逆元。

时间复杂度 $\mathcal O(m+m^{1-\epsilon}\log n)$。

### 384 云斗三轮模拟赛 D2T3（线段树分治）

先考虑 $\mathcal O(nq)$ 的做法是，每次扫单调栈处理下一个 $\ge a_i$ 的位置 $nxt_i$，答案就是 $\sum[a_i=a_{nxt_i}]$。考虑先套一个定期重构，令时间块长为 $B$，那么会有一些关键位置被修改，称为黑点。黑点将这些。黑点与黑点，黑点与白点之间的贡献容易暴力扫描每一段来处理，每次复杂度 $B^2$，总复杂度 $\mathcal O(qB)$，可以接受。

考虑白点之间的贡献。如果两个白点身处同一个段中，那么贡献是恒定的，可以单调栈预处理。另一方面，如果两个白点不在同一段中，那么这对贡献匹配点是确定的，但是可能因为黑点而倒闭。注意到这些贡献的白点区间只有包含或者相离（定义为 $r_1\leq l_2$），所以建树后可以直接树剖维护删除一个到根直链的贡献。考虑不建树，处理出 $B^2$ 对白点区间的信息，每段是前缀 $\max$ 向前匹配，后缀 $\max$ 向后匹配，注意到事实上只会有 $\mathcal O(B)$ 对信息非空，因此找到它们并且每次二分当前修改带来的影响。时间复杂度 $\mathcal O(\frac{nq}{B}+qB\log n)$，取 $B=\sqrt{\frac{n}{\log n}}$ 得到复杂度为 $\mathcal O(q\sqrt{n\log n})$ 的做法。

update：正解是考虑线段树分治，可以做到 $\mathcal O(n\log n\log q)$ 的做法。

### 385 *qoj10042（离散化，Hall 定理）

首先考虑离散化，也就是压缩 $l_i,r_i$。我们找出一组尽量靠左的匹配点集。每次选择将 $x$ 序列的当前最小值向左尽量移动到 $l$，保持的形态是：形成若干个极长连续段，每个连续段中间间隔至少为 $2$，这个形态可以被一直保留。不难想到以下的过程，维护关键位置集合 $S$，从前往后扫 $l_i,r_i$，**进行 $\boldsymbol{3}$ 次**如下操作：找到最小的数 $x$ 满足： $x\ge l_i,x\notin S$，此时将 $x$ 加入集合 $S$。那么只需要保留 $S$ 集合的位置用来匹配。

考虑构造一个候选集合 $B\subseteq S$，这个集合内的点两两之差 $>1$。然后再拿 $B$ 和 $n$ 个区间做匹配，这个匹配就是平凡的贪心。使用 Hall 定理。设 $f(L,R)=\sum[l_i\ge L,r_i\leq R]$，$g(L,R)=\sum_{x\in B}[L\leq x\leq R]$，$w(L,R)=R-L+1-2f(L,R)$。

如果 $\min(w)\leq -2$，整个问题无解；如果 $\min(w)\ge 0$，构造 $B=\{2,4,6,\cdots\}$ 即可。如果 $w(L,R)=-1$，那么 $L+2k,k\in[0,\frac{R-L+1}{2}]$ 都在集合 $B$ 中，将这些数暂时加入集合 $F$。在集合 $F$ 的基础上构造集合 $B$ 即可。首先对于 $\min(F),\max(F)$，将其分别减去，加上 $2k$ 的结果加入集合 $B$，否则对于 $F$ 中的两个相邻元素 $p,q$，若 $p$ 与 $q$ 的奇偶性相同，则把 $p+2k,k\in[0,\frac{q-p+1}{2}]$ 加入 $B$ 中；否则，$p$ 到 $q$ 这一段所有数的选择情况一定是 $101\cdots010010\cdots101$，即我们需要选一个 $d$，然后把 $p+2,p+4,\cdots,d−1,d+2,\cdots,q−2$ 加入 $B$ 中。考虑确定 $d$：我们从小到大扫描所有非平凡的 $p,q$，贪心找到最小的 $d$，使得对于任意 $R<q$ 的 $[L,R]$ 都满足 $f(L,R)\leq g(L,R)$。

使用扫描线 $S$ 以及线段树维护，时间复杂度 $\mathcal O(n\log n)$。

### 386 2nd ucup stage4

来点 ucup 娱乐一下。

#### A. qoj7558

这个题抄袭 [PKUSC2024] 分流器。注意到 $x$ 一定是最后变为 $0$ 的，并且由于每一轮 $a_i$ 都是整数，使用整除分块用到的那个理论可以直接拆开，当前的 $a_x$ 形如 $\lfloor\sum\frac{\sum_{i\in S_k}a_i}{2^{k+\Delta}}\rfloor$，$S_k$ 的刻画可以找到 $u\to x$ 的路径集合 $P$，找到 $|P|=k$，对于 $a_u$ 求和。把这个东西左移 $ans$ 位得到一个 $S$，处理一下每个位置的贡献 $f_u=\sum_{path:u\to x}2^{len}$，容易 dp 处理。那么 $S=\sum a_ic_i$，答案就是 $\lfloor\log_2(S)\rfloor+1$，时间复杂度 $\mathcal O(\frac{nm}{\omega})$，因为需要压位处理高精。

#### D. qoj7561

考虑使用动态开点线段树维护。需要处理：区间中 $\sum p_i,\sum p_ip_j,\sum p_ip_jp_k$ 以及加法标记 $tag_i$。显然 $tag$ 与节点信息的合并是容易的，可以对 $tag$ 进行标记永久化，询问时对该节点的 $tag$ 合并后返回。难点在于：预处理节点区间 $[l,r]$ 的信息。可以处理出 $coef_i$ 表示第 $i$ 位的贡献，那么后面两个容易做到 $\mathcal O(n)$ 合并，对于第三个枚举中间位，处理前后缀的和即可。时间复杂度 $\mathcal O(n^2q)$。事实上对于一个 $[l,l+2^k-1]$，可以做到 $\mathcal O(n^3)$ 预处理以及 $\mathcal O(k)$ 的处理。原因是只有 $k$ 位是有值的，这样总复杂度 $\mathcal O(nq\log n)$。

#### F. qoj7563

弱智题。

考虑 $x$ 与一个统计点 $u$ 的 lca 为 $y$，枚举 $x$ 的祖先 $y$。如果 $x=y$ 那么是简单的，线段树维护即可；否则，对于原树做轻重链剖分，对于轻边切换的部分也是可以转化为 $\mathcal O(1)$ 个 dfs 序区间的线段树查询；对于重边，每个点维护 ban 掉重儿子的最大贡献，即 $c_u=\max(d_v-a_v)-2d_u$。修改子树就对子树内所有 $c$ 做区间加，然后向上只需要修改 $\log n$ 个祖先的 $c$。使用线段树维护这些操作，时间复杂度 $\mathcal O(n\log^2n)$。

#### G. qoj7564（容斥，高维前缀和，点减边）

25 秒是给 $n^2$ 跑卷积的人开的，比如我。请注意这个题的样本空间是 $n!$ 而不是 $n^n$，无语。从统计答案的角度，处理出 $f_m$ 表示有多少个 $m$ 大小的子集存在冲突，$m$ 的答案是 $f_m-f_{m-1}(n-m+1)$。还是不好做的，考虑转化成计算不存在冲突的方案数，最终再转化一下。

那么相当于有 $5$ 个区间 $[l_i,r_i]$，每次取交集，判定是否存在某个区间变成空了。交集 $x$ 可以转化为：$[x\ge l]-[x>r]$。考虑钦定一个五元组交集，这个五元组可以直接暴力 dp 做高维前缀和，那么就是 $f_{x_1,x_2,x_3,x_4,x_5}$ 表示 $\sum[l_i\leq x_i\leq r_i]$。另一方面，对于交集钦定可以采用点减边，外层枚举子集 $S\subseteq\{1,2,3,4,5\}$ 表示 $S$ 子集的位中采用的是容斥掉边的形式，带上容斥系数 $-1$ 计算贡献。这些东西加起来就可以得到 $g_i$ 表示 $i$ 个数中无冲突的方案数，注意到这里只计算了代表元的贡献，就是上述计算的是极大的方案数。$g$ 向下传需要做卷积。

令本题 $m=5$ 表示判定字符串的长度，时间复杂度 $\mathcal O(n\log n+2^m(n+|\Sigma|^m))$。

#### H. qoj7565

怎么联考搬过这个题，不能要了。

### 387 uoj871（扫描线，并查集）

将询问挂在 $r$ 上，对 $r$ 从左到右扫描线。

考虑先执行操作 $1$ 再执行操作 $2$。我们需要用最少的操作 $1$ 即若干次单点减 $D$ 使得整个序列变得单调不降。对于一个 $a_i>a_{i+1}$ 而言，$a_i$ 必然操作过。且后续如果要操作 $a_{i+1}$ 就必须要操作 $a_l$。并且为了最小化操作次数，减到合法时我们不会无故操作 $a_i$ 但不操作 $a_{i+1}$。此时满足 $a_{i+1}-a_i<D$。此时两者的操作是同步的，可以合并成一个连续段，并查集维护即可。然后加入一个 $a_r$ 时可以不断操作之前的连续段，会有一些合并操作，可能也会插入 $a_r$。

连续段的均摊操作次数是正确的，直接线段树维护即可。时间复杂度 $\mathcal O(n\log n+n\alpha (n))$。

### 388 *uoj813（递归子问题即消元，拆独立限制）

并非人类。

考虑逐个消掉变量，现在考虑消掉 $x_n$ 的限制。加入一个元 $x_0=0$ 用以刻画 $x_i\in[0,T]$ 的限制。此时有 $x_n\in[\max(x_i-a_{i,n}),\min(x_i+a_{n,i})]$。那么考虑 $x_{1\sim n-1}$ 都确定时，$x_n$ 只用关心两者各自最紧的限制。直接枚举 $p,q$ 表示上下界分别最紧的限制，爆搜这个，那么此时 $a$ 的限制会有变化（注意一下有多个时取 $p,q$ 分别标号最小的），在搜索时更新，这样 $x_n$ 就没用了，会产生一个 $(x_q-x_p+k)$ 的贡献乘入这个部分的答案，递归子问题即可。枚举的同时要维护一个多元多项式，合并时做自然数 $k$ 次幂和，众所周知这是 $k+1$ 次多项式，因此预处理一下就好了。但同时枚举 $(p,q)$ 导致这样的复杂度是 $\mathcal O((n!)^2\text{poly}(n))$。

注意到 $x_n$ 的贡献形如 $(x_q+a_{n,q})−(x_p−c_{p,n})+1$，我们可以将两部分分开计算，也就是利用乘法分配律，这样每次只需要独立决策选 $q$ 还是选 $p$，复杂度降到 $\mathcal O(2^nn!\text{poly}(n))$。

### 389 *uoj814（分块维护函数复合，bitset）

这是暴力。

显然整个过程中，每个位置分开维护，变化过的极长不可通过区间只有 $\mathcal O(q)$ 个，可以直接用 ```std::set``` 维护。这样操作是反转一个区间的状态。我们提取颜色段均摊的操作序列，按照所属位置排列成 $m$ 个区间的序列，每次修改一个区间是否被激活；如果未激活有 $f_i(x)=x$，否则若 $x\in[l_i,r_i)$，则 $f_i(x)=r_i$，反之 $f_i(x)=x$。查询的是 $[l,r]$ 的带入 $x=0$ 的函数复合结果。

考虑直接对 $m$ 分块维护分段函数复合。我们只需要支持快速重构第 $k$ 块对应的总函数 $F_k(x)$。令块长为 $B=\sqrt n$。显然一个块的函数 $F_k(x)$ 只有 $\mathcal O(B)$ 段，所以只需要找到这些关键点。这个函数长成的样子是每段斜率 $1010\cdots$ 的，但是段与段之间可能相差很远。一个关键的性质是：每段的右端点 $x$ 必然就是它的值 $x$ 本身。假设有 $p$ 个关键点，只需要维护一个长度为 $p$ 的 $01$ 序列，其中 $s_i=[F(i)=F(last(i))]$，一个 $01$ 串唯一描述了一个 $F$。容易想到使用 ```bitset``` 加速这个过程。这个只会出现 $1\to 0$，因此暴力修改 $s$ 即可。（注意到在 $B$ 较小时 $\frac{B}{\omega}<\log B$）

还有一个问题就是块与块之间衔接，通过压缩后的 $F$ 来找到返回值，这个事情需要对关键点二分。理论上是可以逐块操作，通过后期的离散化操作还原这些值对应的前驱做到理论去掉 ```std::lower_bound``` 的复杂度。

由于 $m$ 与 $n,q$ 都是同阶的，所以复杂度是 $\mathcal O(n\sqrt n+\frac{n^2}{\omega})$。

### 390 uoj873（根据性质设计 dp）

首先考虑怎么压缩 $h$：对于所有位置排序，令 $h'_i=\max(h_i,h'_{i-1}+1)$。

最终过程对肯定是对高度扫描线，然后有一些点没有被加入树，带来点数 $\times k$ 的代价。那么分为和已经有叶子的点匹配以及与叶子匹配；对于前者，如果确定了是在哪个前缀取，那么代价是确定的：我们声称同样 $h$ 中最小的 $c$ 会立刻匹配掉；注意到抬高后必然不会加新的连接装置。由于叶子会带来免费的名额，所以当前状态叶子的个数也是重要的。

设计 dp：$f_{i,j,k}$ 表示考虑了前 $i$ 的高度，有 $j$ 个叶子，有 $k$ 个点被移动到了 $h_i+1$ 的高度且还没有加入树，此时的最小代价。而叶子是可以贪心用的，因为这个免费名额在什么时候都是一样的，所以转移确定。对于同一高度的，如果想让它成为叶子的话就必须往前缀上去挂，这里的贡献是确定的。转移可以考虑贪心地消掉 $j$。一个性质是被提升的点最终的儿子个数一定 $\leq 1$，所以这些 $k$ 都只能被挂成叶子。转移是 $\mathcal O(1)$ 的，时间复杂度 $\mathcal O(n^3)$。

### 391 *云斗三轮模拟赛 D2T2（树的直径，栈的重构树刻画）

注意到固定 $u$，合法的 $v$ 的必要条件是 $v$ 在 $u$ 到离它最远点的路径上，由经典结论我们只关心直径端点。将 $u$ 挂在对应的直径端点上，以直径端点为根即可。那么就是确定一个有根树，求 $u$ 到根的路径上多少个点是合法的。

预处理每个点子树高度以及不同于这个儿子方向的次长链，一个 $v$ 不合法有两种情况：存在 $u$ 子树外的点 $w$ 使得 $v$ 不合法；或者存在 $u$ 子树内的点 $w$ 使得 $v$ 不合法。这个问题考虑 **从上往下** 处理所有 $u$ 的信息，具体来说维护一个集合 $S$ 表示当前合法的 $v$。注意到第一类点中不合法的 $v$ 在上面不合法在下面也一定不合法；对于第二类点，在 $\text{dfs}$ 点 $u$ 的过程中，先走最长链再走次长链，这样被删除的点就不用再放回来。

注意到 $S$ 的变化事实上是一个栈，我们希望刻画所有 $u,v$ 表示在 $u$ 状态时 $v$ 是否在栈中，还要刻画栈的变化。有一个经典的处理方式：在 push 节点时，令这个点作为一个新的叶子向当前的栈顶连边；pop 就维护当前的栈顶在哪。这样得出来一棵重构树，那么栈的当前信息就是到根的某条链。这样询问转化为两个序列 $p,q$，查询有多少 $x\in[l_1,r_1],y\in[l_2,r_2]$，$p_x$ 为 $q_y$ 的祖先。

这个是经典的。离线并差分为 $[1,r_1],[1,r_2]$，对 $(r_1,r_2)$ 进行莫队可以得到 $\mathcal O(n\sqrt n\log n)$。采用莫队二次离线加 top cluster 树分块可以得到 $\mathcal O(n\sqrt n)$ 的做法。

### 392 xsy5765（dp）

noip t3 难度（？）

> 给定一张连通图 $G=(V,E)$，求一个图的序列，满足 $E\subseteq E_i,V=V_i$ 且两两不满足边双连通等价（$G_1\sim G_2$ 当且仅当任意 $u,v$ 在 $G_1$ 边双连通时，$u,v$ 在 $G_2$ 边双连通），最大化序列长度 $s_0$ 的前提下，最小化边数总和 $s_1$，输出这两个值对 $998244353$ 取模的结果。$n=|V|,m=|E|\leq 6\times10^5$。

边双连通等价当且仅当 $G_1,G_2$ 的割边集合相同，注意到新加的边显然不能成为割边，所以关于 $s_0$ 有一个显然的构造：令 $c$ 为 $G$ 中的割边数量，那么令 $s_0=2^c$ 就是正确的。复制一条割边可以将割边变为非割边，而其他割边不受影响。

显然我们可以将 $G$ 缩边双树 $T=(V,E)$。那么就是，一个树，对于一种对边染色的方案，保留的黑边形成了若干连通块。结论：在连通块大小至少为 $2$ 时，添加的最小边数为 $1$ 度点个数除以 $2$ 向上取整的结果。证明可以考虑找到重心。

考虑将贡献拆到每个可能形成的连通块上。$f_{u,i}$ 表示在点 $u$ 子树内，与 $u$ 边双连通的部分有 $i$ 个叶子的方案数，用 $g_u$ 表示点 $u$ 子树内选定一个（完全位于 $u$ 子树内）连通块的贡献总和。特殊处理一个边双连通分量的根是叶子的情况。由于这个只有 $\lceil\frac{i}{2}\rceil$，所以只需要记录匹配叶子的奇偶，所以 $i$ 这一维也可以被压缩。时间复杂度 $\mathcal O(n)$。

### 393 *xsy5766（扫描线，历史和）

[link - 区间压缩](http://8.138.223.198/p/32)

先考虑对于一个序列计算宽度。压缩就考虑极小的单元，将一个区间压缩到这个小单元上。我们将所有 $l,r$ 拉出来排序放到一起。如果出现相邻两个按顺序是 $l_i,r_j$，那么就必然需要新加一个单位来描述，并且这样做的好处是每个区间内部至少有一个相邻的 $l,r$。换而言之，将所有左端点看作 ```(```，右端点看作 ```)```，令下标相同的左括号在右括号前面，按照值从小到大拼接得到一个串，则宽度为该串中的 ```()``` 子串个数。

注意到操作等价于仅保留与 $[x,y]$ 有交的区间，因为 ```(``` 在 $<x$ 位置一定没有额外贡献，另一边同理。最终相当于保留指定括号串的子序列。容易想到拆贡献，但是直接算每一对就是不独立的。转化成计算 ```)(``` 子串个数就是独立的，计算概率相加即可。

扫描线所有序列的 $l_i$，线段树加历史和，维护矩阵乘法即可。时间复杂度 $\mathcal O(n\log n)$。

### 394 20250613 联考

#### A（拆贡献）

可以归纳说明任意时刻的末尾 $k+1$ 个元素不重复，因此每次只删至多一个。注意到每个元素必然被加入，因此只可能被其颜色的后继删除。若 $(i,nxt_i)$ 从空栈开始执行有 $\geq k$ 个元素（删掉 $i$ 以前的元素不影响 $i$ 到栈顶的距离），那么 $i$ 不会被 $nxt_i$ 删除。这只要求 $(i,nxt_i)$ 有至少 $k$ 种不同的颜色，因此产生贡献的 $k$ 的下界是区间颜色数，离线扫描线树状数组即可。

那么现在总共有 $\mathcal O(n)$ 个三元组 $(l,r,k)$，查询的是有多少三元组满足 $(l_i,r_i,k_i)$ 使得 $[l',r']\subseteq[l,r],k'\leq k$。另一方面，$l\leq i\leq r,nxt_i>r$ 的贡献是一个简单的二维数点。前面的东西直接三维偏序固然可以，但是可以转成二维偏序的。对于 $k$ 进行扫描线，注意到大区间包含小区间的时候大区间颜色数不少于小区间。当 $[l,r]$ 内颜色数不超过询问的 $k$ 时是容易做的。否则不存在 $l$ 小于询问 $l$ 且 $r$ 大于询问 $r$ 但 $k$ 不超过询问 $k$ 的，因此只有相交关系需要被容斥掉，树状数组维护一下就好了。时间复杂度 $\mathcal O(n\log n)$。

#### *B（树上方程消元，线段树合并的撤销）

设 $f_u$ 为 $u$ 到 $1$ 的期望步数，考虑优化高斯消元过程。注意到叶子节点的方程只涉及祖先处，可以先把 $u$ 对 $fa_u$ 的行向量进行消元。考虑从下往上做消元，相当于剥叶子，实现上等于 dfs 出栈序。这个过程其实就是，从下往上合并得到 $1$ 的所有儿子的 dp 真实值，然后从上往下代入并消去这个值，再递归子树做这个过程。

对于方程组系数使用动态开点线段树维护，消元的过程形如对该方程乘以 $t$ 加到另一个方程上，容易使用线段树合并做。得到一个值之后，还原就需要撤销。线段树合并时记忆化，回溯时根据这个记忆化的操作序列来修改即可。时间复杂度 $\mathcal O(n\log n)$。

猜你想搜：[[NOI2024] 登山](https://qoj.ac/problem/9159)。

#### C（带权分块，莫队二离）

显然 $\max$ 是骗人的，我们可以计算 $\sum_{i=l}^r\sum_{j\ne i,j\in[l,r]}occ(s_i,s_j)$。对于 $s_i=s_j$ 多算的贡献可以跑一次莫队消除掉。建出字典树和对应的失配树。可以莫队，在移动指针的时候，我们需要求出一个字符串与原区间中的每一个字符串的贡献，这可以通过在 fail 树上维护子树加单点求值/单点加子树求值来维护。这个形式是经典的莫队二次离线，分块平衡一下是 $\mathcal O(S\sqrt S)$。注意由于字符串不等长，所以需要带权分块。

### 395 AT_arc158_f（拆分限制）

猜一下 $m$ 不是很有用，对于一个 $xyx$，显然可以缩成 $yx$，原因是我们只关心 $[0,k-1]$ 每个位置的最后一次出现，这样形成了一个 $k$ 的排列。从一个长度为 $p$ 的排列拓展到 $m$ 的操作序列，直接施加容斥要求每种数出现至少一次即可。因此问题是对于所有 $l\in[1,k]$ 求出有多少元素互不相同的长度 $l$ 的操作序列合法，事实上就是第二类斯特林数 $\begin{Bmatrix}m\\l\end{Bmatrix}$。

上述转化，启发我们倒序考虑操作序列。容易想到的状态是最后 $|S|$ 个的操作集合是 $S$ 的方案数 $f_S$。考虑拆分限制。我们只要求所有 $b_i$ 在 $b_{i+1}$ 左边。那么我们考虑 $b_i,b_{i+1}$ 的每一位，存在一个集合 $S_i$ 以及 $T_i$ 分别满足 $b_{i,r}<b_{i+1,r}$ 以及 $b_{i,r}>b_{i+1,r}$。求一下在 $a$ 中的相对顺序，得到是否需要逆序这个。如果需要颠倒那么就至少需要进行一次 $x\in S_i$ 的操作；所有 $y\in T_i$ 后面必须要有 $S_i$ 中的元素。那么 $f_S$ 的转移就是简单的：我们需要判定新加入的 $i$ 作为上述的 $y$ 是否满足所有限制。直接分开高维前缀和即可。时间复杂度 $\mathcal O(n\log n+2^kk^2+nk)$。

### 396 P8175（调整法，反悔贪心）

考虑将数轴简化为：$k$ 个商店，处理出 $i$ 到 $i+1$ 的距离 $b_i$，以及第 $i$ 个商店最近的空地距离 $c_i$。则 $pos_i=2\sum_{j<i}b_j$。

行动的策略一定是从左往右考虑每个商店，连续地在当前商店取。那么在一个商店取了多于 $1$ 个时，除了最后一个，前面的部分一定都会通过 $c_i$ 消化；而最后一个可以通过 $c_i$ 或者向右侧走最近的空地消化，这两个决策取较小值。考虑预处理 $nxt,pre$ 表示两个方向最近的空地。令特殊决策是：$c_i$ 在左边但决策向右边商店的 $nxt$ 走，令下一个决策的是商店 $x$，这样可能更优是因为可能出现 $nxt_x-pos_x>c_i$。进一步施加调整法，你发现如果做了特殊决策，那么 $x$ 是一定选满的，也就是说如果做了特殊决策，这个位置的贡献就可以拆成确定的。这样在 $i$ 处就有一个除了移动距离之外的最终物品的额外代价 $ex_i$。

因此可以等价地认为：在第 $i$ 个商店可以用 $2c_i$ 的代价买 $<a_i$ 个物品，以及买最多一个代价为 $ex_i$ 的。前者不优所以正确性是对的。在第 $i$ 个商店时还有代价限制。大根堆维护反悔贪心，时间复杂度 $\mathcal O(n\log n)$。

### 397 *qoj6718（前缀和折线，构造）

记 $s$ 为原数组的前缀和数组，找到 $s_x,s_y$ 分别为 $s$ 的最小值和最大值。不妨设 $x<y$ 否则用一步操作 $1$。因为 $s_x$ 是最小值，操作 $(2,x+1,n)$ 可以把后面所有数都变得非负。同时，最大值依然在 $x$ 的后面。找到最大值 $s_y$，操作 $(3,1,y)$，这样子 $[1,y]$ 的所有数也都非负了。最多用了 $3$ 步操作。这个东西怎么看出来呢，把前缀和折线画出来随便玩玩就好了。

对于 $0,1$ 步操作是平凡的。考虑 $2$ 步操作如何判断和构造。分成三种情况：第一种是一步操作 $1$，然后变成判断是否能一步做完。第二种是两步操作二（两步操作三是一样的）。第三种是先 $2$ 后 $3$，当然先 $3$ 后 $2$ 也是一样的。第二种情况。对于没操作到的地方，肯定都是非负数，所以直接先操作一个前缀不劣，所以第一步操作是一个前缀。第二步操作直接操作 $[1,n]$ 最优。稍加判断前缀和的前缀和的 $\min$，以及前缀和的后缀 $\min$ 即可。

第三种情况，不妨是先 $3$ 后 $2$。枚举第一个操作的右端点，同上，第二次操作还是一定是 $[1,n]$ 最优。那么能不能行就变成了几个不等式。这个不等式形成若干半平面，保留凸壳后在凸壳上二分查找最优值即可。时间复杂度 $\mathcal O(n\log n)$。

### 398 *qoj9491（图论，压缩有效状态，等价转化）

一个路径可以分解为走一条简单路径以及走途径的简单环。假设路径经过的环长度分别为 $l_i$，而路径本身长 $k$，那么所有 $x\bmod \gcd(l_i)=k$ 的 $x$，当 $x$ 充分大时有 $f(n,x)=1$。对于原图强连通，由于可以构造一条路径经过所有点，因此我们声称答案是所有环长的 $\gcd$。这个比较经典：取一棵 dfs 外向生成树，那么 $\gcd$ 就是所有非树边的 $\gcd(w+d_u-d_v)$。接下来我们显然需要将有向图的 SCC 进行缩点，我们可以处理出 $d_i$ 表示这个为 $i$ 的 SCC 的环长的 $\gcd$，记为 $p_i$。如果 $n$ 在 SCC 中，那么就确定答案是这个 SCC 中环长的 $\gcd$ 的因子，容易记忆化求出一个 $01$ 串。

综合上述两个方向，处理出：$f_{u,t,i}$ 表示是否存在 $1\to u$ 的路径，当前路径所有 SCC 的 $\gcd$ 为 $t$，且路径总长模 $t$ 余 $i$。$f$ 的处理是容易使用记忆化搜索，并且这个状态量是正确的，那么最终问题等价于：对于所有 $t\in[1,B]$，将 $f_{t,i}$ 视为 $01$ 串复制无穷次，所有结果求并集得到一个 $01$ 串 $S$。我们需要求出 $S$ 的最小周期。考虑取反后改为取交。显然每个 $f$ 可以缩成最小周期，然后重新令 $t$ 为每个 $f$ 当前的长度。我们可以得到 $ans\mid \text{lcm}(t_i)$。全部互质的情况，我们声称答案就是 $\text{lcm}(t_i)$，因为这个过程可以类比 CRT，压缩后每个位置都是必然有贡献的。

如果两个串的长度满足 $x\mid y$，那么我们可以先对这两个串合并。在子任务 $5/6$ 中保证最终 $t$ 两两互质或者存在全 $0$。这启发我们将当前状态变为 $t_i$ 两两互质的最终状态。显然我们需要修改 $f$ 才能达到修改 $t$ 的目的，因此考虑等价转化当前状态。考虑一个样例：$f=\{\texttt{01},\texttt{0111}\}$，我们发现有一些位置从 $1\to 0$ 之后对 $S$ 没有任何影响。但是找到后可以进行进一步压缩。

考虑不能被 $1\to 0$ 的位置，满足将所属 $f$ 其余位都修改成 $0$ 后，这样求出的 $S'$ 并非全 $0$。针对小质数，我们找到一个 $I$，每次保留 $S$ 中模 $I$ 为 $r$ 的所有位置。 取 $I=2520$，这样每个提取出串的周期是 $d_i=\frac{t_i}{\gcd(t_i,I)}$，这样 $d_i$ 可以表示为 $p^k,p\in\mathbb{P}$。转化为子任务 $6$，对于成倍数的直接合并，最终可以转化为两两互质的状态。时间复杂度 $\mathcal O(nB^2+B^2I)$。

### 399 *20250615 联考 B（最小割，点分治）

先不考虑连通块的限制，我们希望选一个集合最大化 $\sum a_i\sum b_i-\sum c_i$。展开一下，设 $x_i=[i\in S]$，那么得到这个式子是 $\sum a_ib_jx_ix_j-\sum c_ix_i$。取相反数之后需要最小化 $\sum-a_ib_jx_ix_j+\sum c_ix_i$。考虑最小割模型，令 $x_i$ 表示最终 $i$ 与 $S/T$ 连通，相当于对于 $w_{i,j}\ge 0$ 的最小化 $\sum w_{i,j}x_i(1-x_j)$。前面那个就可以转化为 $\sum a_ib_jx_i(1-x_j)+\sum(c_i-a_i\sum b_j)x_i$。对于 $k_ix_i$，$k$ 的正负性可以用 $S,T$ 来解决，即每个点都与 $S,T$ 中的一个有连边。所以上述问题可以转化为最小割问题。

加上连通块的限制，钦定某个点为根，钦定选出的连通块必须包含根节点。这就要求若一个点被选中，则其父亲一定也被选中，那么对原式加上 $-\infty\sum x_i(1-x_{fa_i})$ 的限制即可。同样可以转化为最小割。上述最小割中 $|V|=n+2,|E|=\mathcal O(n^2)$，使用 dinic 的单组复杂度 $\mathcal O(n^{2.5})$。

对整棵树进行点分治，计算分治中心为根时，包含分治中心的答案，结合主定理可以分析出时间复杂度 $\mathcal O(n^{2.5})$。

### 400 uoj876（拆分限制到独立单元分开考虑，二分）

如果确定了匹配对象，那么一定是原数组中第 $i$ 小的匹配待定数组第 $i$ 小的，因此直接枚举红色的起始位置可以得到平方的做法。枚举起始位置很难省掉，考虑从 $a$ 的性质优化。

二分答案 $mid$，那么每个位置允许种植的范围是 $[a_i-mid,a_i+mid]$。注意到题中事实上给的是一个 $2n$ 个点的圆，因此可以任意旋转，我们要一个填半圆。从另一个角度，注意到红蓝的判定完全独立，因此预处理红蓝两个匹配数组针对 $2n$ 个起始位置的匹配合法性，最终只需要暴力扫圆上是否存在距离为 $n$ 的合法点对即可。

不妨设在考虑红色。对 $b$ 从小到大排序。那么一个起点就要求所有对应的 $b_i$ 都在匹配点的正负 $mid$ 范围内，如果有一个爆了就不行。所以对于一个位置，容易求出它可以匹配上的位置区间 $[l_i,r_i]$。另一方面，我们还需要关心它对哪一段半圆产生合法贡献。对于第 $i$ 小的问题，转化为考虑它的意义，就是有 $i-1$ 个位置比它小。半圆可行当且仅当每个 $(a_i,i)$，都有 $<(a_i,i)$ 的个数 $\in[l_i,r_i]$。那么容易扫描线，得到半圆上对应它可行的区间。用一个差分统计，可以做到线性 check。复杂度 $\mathcal O(n\log n)$。

上述做法的精髓是，不断拆开全体的限制，到每个独立的单元上。最后做类似于取交集的方法来保证整体的合法性。

### 401 集合幂级数 exp/ln - 连通性限制

严肃学习《集合幂级数在子图计数问题上的应用》。

对于一般的情形，要求 $[x^{\varnothing}]f(x)=0$。给定一个多项式 $h$。集合幂级数复合 $h(f)=\sum_{i\ge 0}h_if^i$。当 $h=\exp x$ 时，$h_i=\frac{x^i}{i!}$，此时有 $g=h(f)$ 满足 $g_S$ 是 $S$ 所有无序划分的 $\prod f_{S_i}$ 之和。取 $h=\ln(1+x)$ 时 $h_i=(-1)^{i+1}\frac{x^i}{i!}$。

现在考虑如何执行这个过程。考虑占位集合幂级数，初始令 $F_{|S|,S}=f_S$。然后对每个 $F_{i}$ 做 FMT。对于每个集合 $S$，做 $\mathcal O(n^2)$ 的形式幂级数意义下的多项式 $h$ 复合。最后再 iFMT 回去，结果为 $G_{i,S}$ 时，最终 $[x^S]h(f)=G_{|S|,S}$。在集合幂级数 $\exp$ 时，$g_n=\frac{1}{n}\sum_{i=1}^{n}if_ig_{n-i}$；在集合幂级数 $\ln$ 时，$g_n=f_n-\frac{1}{n}\sum_{i=0}^{n-1}ig_if_{n-i}$。总时间复杂度 $\mathcal O(2^nn^2)$。

根据这个过程，我们容易用组合意义来优化这些。比如说 $g=\exp f$ 是好求的，那么可以做 $g\to f$ 的 $\ln$ 变换。例题：连通边集计数；连通二分子图计数（钦定黑白，但是一个不连通二分图会被算 $2^c$ 次，求 $\exp f$ 可以子集卷积）。

### 402 qoj5411（集合幂级数 exp）

显然只需要处理：$f_S$ 表示 $S$ 子集排成一条链的方案数；$g_{S,i}$ 表示在此基础上 $i\in S$ 排在第一个的方案数。答案的统计可以预处理，枚举所有 $x$ 以及其所属集合 $S$。并处理出 $h=\exp f-1$，对答案的贡献就是 $\sum g_{S,i}h_{U-S}$。显然我们只需要按照 $|S|$ 处理出所有 $h_{S,i}$，在最终乘上 $w_{s,i}$ 就可以得到 $h$，$f$ 直接求和即可。令 $n'=n-2$，时间复杂度 $\mathcal O(2^nn^2)$。

### 403 qoj6954（点减边，子集 exp）

首先，对于基环树或者树的贡献可以特殊计算。树可以直接矩阵树定理求 $\det$。环就是 $dp_{S,u,v}$ 表示 $S$ 子集构成链，$u,v$ 分别为首尾，统计时带上 $\frac{w_{u,v}}{|S|}$ 即可。

对于剩下的图，存在多于 $1$ 个简单环。考虑两环相交的情况，由于除去中间这个部分外面还有一个大环，所以两环相交的长度必然是 $\leq 2$ 的，否则在 $>2$ 时，中间的点一定不被外面的大环经过。提出相交的部分，这引诱我们去做点减边容斥，要求所有环必须包含点 $u$ 或者同时包含 $u,v$。而它的判定是从反面：删除 $u$ 以后，剩下的图必须无环。

对于删除 $u$ 剩余图无环的情况，这要求 $U-\{u\}$ 被划分为若干森林，且每个连通块向 $u$ 至少连一条边。处理每个连通块的权值，暴力做子集 exp 即可。对于删除 $u,v$ 剩余图无环的情况，一个连通块内选出不超过一个点与 $u$ 连边，不超过一个点与 $v$ 连边，并且不能都没有。也可以转化为子集 exp。$n$ 很小所以可以直接暴力做。

由于做点减边时会带上树或基环树的贡献导致其被错误计算，所以把上面这些合起来还需要再做一些推导才是答案。时间复杂度 $\mathcal O(3^nn^2)$。

### 404 qoj2068（图上匹配折半，子集 exp）

不妨设 $n$ 是偶数，否则添加一个孤立点即可。考虑添加边 $(2i-1,2i)$，这样算上匹配的边之后形成的是若干环和链。此时匹配的大小是 $\frac{n}{2}$ 减去链的数量。这样添加的好处是 $2i-1,2i$ 必然同时在一个连通块，因此只需要对 $2i$ 进行状压，规模是 $2^{\frac{n}{2}}$。那么对于链就直接设计 $dp_{S,i}$ 表示 $S$ 子集构成链，当前结尾是 $i$ 的方案数。对于环，可以直接钦定最小的点当作环的起点。这样可以求出两个集合幂级数 $f,g$ 分别表示每个集合形成环或者链的方案数。加上原图所求的东西，可以给 $g$ 乘上 $\frac{1}{c}$。最终结果就是 $[x^U](\exp f\times \exp g)$。时间复杂度 $\mathcal O(2^{\frac{n}{2}}n^2)$。

### 405 边双连通 - 连通变换

X 问题：所有子集 $S$ 有权值 $a_S$，有 $b_S$ 个边双连通子图。定义一张连通子图的权值是其所有边双的 $\prod a_{S_i}$，求所有边的导出子图权值和。

分阶段考虑这个问题。设 $n+1$ 个集合幂级数 $p_{0\sim n}$，其中 $p_i$ 表示只允许出现 $\max(u,v)\leq i$ 的割边的边子图权值和。最终希望求出 $p_n$，初始有 $[x^S]p_0=a_Sb_S$。考虑 $p_{u-1}\to p_u$ 的过程，找到以 $u$ 为端点的割边并断开，$S$ 会分裂成 $P\cup T_1\cup T_2\cdots \cup T_k$，它们两两无交并且 $u\in P$。处理出 $c_{u,S}$ 表示 $\sum_{(u,v)\in E}[v<u\wedge v\in S]$。对于一组 $P,T_1,\cdots,T_k$，这样划分出来的是唯一的，乘积的系数都是 $p_{u-1,S}$，对于 $T_i$ 还要带上 $c_{u,T_i}$。令 $q_{u-1,S}=[u\notin S]p_{u-1,S}c_{u,S}$，那么 $p_u=p_{u-1}\times(\exp q_{u-1})$。可以子集 $\exp$，子集卷积做。因此 X 问题可以在 $\mathcal O(3^nn)$ 或者 $\mathcal O(2^nn^3)$ 的时间完成。

但是 $b$ 不已知。令 $a_S=1$，我们容易求出 $p_n$，$p_{n,S}$ 即 $S$ 的边连通子图数量，可以做另一个容斥求出。考虑 $p_u\to p_{u-1}$。我们发现 $u\not\in S$ 的都是已知的，因此 $q_{u-1}$ 是已知的，$p_{u-1,S},u\notin S$ 是已知的。我们找到 $u\in S$ 的 $S$，根据前述信息还原是容易的，直接使用集合幂级数 $\ln$ 还原即可。复杂度也是 $\mathcal O(3^nn)$ 或者 $\mathcal O(2^nn^3)$。

### 406 *uoj962（边双连通-连通变换，容斥）

我们考虑处理出每个连通块的方案数 $R_S$，根据 $1$ 类限制将某些 $R_S$ 改成 $0$（存在 $u\in S,v\notin S$），最终跑子集 $\exp$ 求全集系数就是答案。

注意到 $2$ 类限制形如：边双缩点形成森林，$c=2$ 要求 $s\to t$ 路径上不全是割点。我们考虑一个树上有若干割点，我们将相邻且均为割点的点缩成一个极大的点，满足这里面就是割点。那么令这个缩起来的是集合 $S$。那么根据 $2$ 类限制可以处理 $S$ 本身是否合法。新树就分为两种大点，白点是大小 $>1$ 的边双；黑点是若干割点内部通过生成树连通的集合 $S$。要求黑点不能相邻。处理出一个 $chk_S\in\lbrace0,1\rbrace$ 表示这个极大的黑点是否合法，不合法当且仅当存在 $u,v\in S$。

每个黑点内部的具体系数 $black_S$ 就是求生成树，可以直接矩阵树。注意 $chk_S=0$ 的 $S$ 有 $black_S=0$。再求出每个子图的边双连通方案数 $white_S$。转化成以下问题：对于所有全集的拆分以及针对每个集合的染色，令黑点集合的集合为 $Q_i$，白点集合的集合为 $P_i$。统计合并成一个生成树的方案数，要求黑点不相邻。权值是 $\prod white_{P_i}\prod black_{Q_i}$。

考虑当 $P,Q$ 确定时，施加容斥。连边看作两个阶段：第一阶段只能在 $P_i$ 间连边权为 $−1$ 的边，第二阶段可以任意连边权为 $1$ 的边。设 $trans(F,c)$ 为将 $F$ 每额外选一条割边，贡献乘 $c$ 的 X 问题后得到的集合幂级数。那么 $R=trans(trans(black,-1)+white,1)$。

根据子集 $\exp$ 以及子集卷积的实际实现，复杂度 $\mathcal O(3^nn)$ 或者 $\mathcal O(2^nn^3)$。

### 407 P11567（边双连通-连通变换，容斥）

> 对于子图 $G'$，定义其权值是有 $c$ 条边不被任意 $k$ 个点对中的任意简单路径经过，权值为 $2^c$。求所有原图的所有连通边子图 $G'$ 的权值之和。$n\leq 16$。

容易发现对于一个子图 $G'$ 需要先做边双缩树，然后 $k$ 个点对覆盖了若干路径。权值就是未被路径覆盖的边数 $c$ 的 $2^c$。使用类似于上图的方式，我们先考虑被覆盖的点集。即一棵树上会被划分为若干黑点与白点表示是否被染色，还会有一些黑边。我们将用黑边连接的黑点合并成极大的大点，内部由若干黑边连接成树。在新树上使用白边连接。

处理 $black_S$ 时，如果存在某个限制点对恰好一个在 $S$ 中那么就是非法的。否则考虑处理连通子图方案数 $g_S$，由 $g_S$ 连接时有可能会出现事实上不被覆盖的方案。这样缩一下，得到的是更多部分的拼接，这样在连接他们的边上设立容斥系数，做 $trans(g,-1)$ 即可得到 $black$。同理，在处理 $white$ 时我们先考虑连通的贡献和，可以求总贡献和后求 $\ln$ 反解，显然一个点集的总贡献和就是 $3^{|E(S)|}$（使用枚举子集的复杂度分析方式），然后再对其求 $trans(g,-2)$ 即可。

最后加起来求所有贡献，就是 $trans(white+black,2)$，时间复杂度 $\mathcal O(2^nn^3)$ 或 $\mathcal O(3^nn)$。

## to do

JOISC2024.

JOISC2025.

CTT2023 day1~3。

https://qoj.ac/contest/1398

正在渲染内容...