9.1 ~ 9.30 做题记录

· · 个人记录

【1】P6680 [CCO 2019] Marshmallow Molecules

将无向边 (u,v) 定向为 u \to v,其中 u<v。则 1,2,\cdots,n 是一组拓扑序。

按拓扑序扫描 u = 1\to n,维护 u 的邻居点集 S_u。取 v = \min S_u,类比左儿子右兄弟表示法,可以将 S_u \setminus \{v\} 挂到 S_v 上,这样扫描到 v 时会计入 |S_v| 的贡献。

注意 S_u 需要去重。set 启发式合并 O(n\log^2 n),线段树合并 O(n \log n)。代码。

【1】P8496 [NOI2022] 众数

考虑对每个数组开一棵权值线段树 T_x,线段树上节点维护子树的摩尔投票信息并。查询操作将 T_{x_1} \sim T_{x_m} 的全树信息进行合并得到候选答案,然后在权值线段树上查询其出现次数即可回答询问。

删除操作需要知道删掉了什么数,可以使用双向链表维护数组 L_x。插入删除在对应链表上操作,并在权值线段树上更新。合并操作就是直接合并两个链表,同时做线段树合并。

视 n,q, \sum m,V 同阶,复杂度 O(n \log n)。代码。

【3-】P11160 【MX-X6-T6】機械生命体

考虑刻画 \text{lowbit}(x \oplus y) \ge 2^k 的 y 组成的结构。我们从低位向高位建立 32 层 01-Trie,将 x 拆成二进制,自顶向下地走向与 x 该位相同的方向,直到完成 k 次游走停止。此时我们所在的子树即为所有可能的 y。

插入删除是平凡的,查询只要维护每个节点的计数器,类比上述游走过程,直到无法进行游走就得到了答案。重点在于+v 的操作。

对 k 层节点,子树中任意数值 x 必可表示为 x=2y+b,其中 b \in \{0,1\} 表示最低位取值,对应着左右儿子。我们将 x+v 写成 2y'+b' 的形式:

考虑维护懒标记 v,下传标记时对 v 的奇偶性进行讨论:

这样我们得到了全局 +v 的做法。

考虑子树 +v 的做法。我们将子树劈下来,对根链 pushup,并对劈下来的子树接上一条根链,打上全局 +v 的标记后做线段树合并。注意及时 pushdown。

复杂度均摊 O(q \log V)。代码。

【2+】P5298 [PKUWC2018] Minimax

考虑求出所有的 D_i。对 w_u 离散化后,设 f_{u,i} 为 u 点取第 i 小权值的概率,对 u 进行讨论:

直接做前缀和优化得到 O(n^2) 做法,获得 40pts。

这种与前后缀和有关的 DP 转移,可以尝试用线段树合并进行优化。设合并 T_1,T_2 时递归区间为 [l,r],维护 [1,l) 的前缀和 p_1,p_2,则有:

复杂度 O(n \log n)。代码。

【2】QOJ6322 Forestry

任意定根后,设 f_{u,i} 为断开 u 到父亲的边,仅考虑 u 子树内部,u 所在连通块最小值为 i 的方案数。预处理对 i 维度离散化。

树形 DP 转移是逐子树加,在 u 处加入儿子 v 时:

我们在 u 处不关心子树外的情况,外部边可以任意断开,则 f_{u,i} 对答案的贡献系数为 i \times 2^{\max(0,n-\text{sz}_u-1)}。

考虑线段树合并优化 DP。转移是 (\min,\times) 卷积,我们对 i,j 的大小关系进行讨论:

这是一个与后缀和相关的转移式。在线段树上维护区间和,合并时动态计算后缀和即可。为了计算答案,我们还需要维护 \sum i \times f_{u,i},而贡献系数 2^{\max(0,n-\text{sz}_u-1)} 是独立的。

复杂度 O(n \log n)。代码。

【1】P3521 [POI 2011] ROT-Tree Rotations

先序遍历考虑自底向上贪心,因为子树的顺序对前缀无影响。

考虑我们位于节点 x,左右子树的先序遍历为序列 a_i 和序列 b_i。我们只要在 x 处最小化跨过左右子树的逆序对。

子树合并的顺序为 a + b 或 b + a,其中 + 表示序列拼接。考虑计算这两种情况新增的逆序对数,取较小者作为决策。

以 a+b 为例,我们可以遍历所有 b_i,只要求出 a 中 a_j>b_i 的 j 的数目。另一方面,我们也可以遍历所有 a_i,求 b 中 a_i>b_j 的 j 的数目。

我们取长度短的序列统计逆序对数,用平衡树维护 a,b 做启发式合并,得到复杂度 O(n \log^2 n)。存在线段树合并的时空 1log 做法。代码。

【2】P10061 [SNOI2024] 矩阵

考虑性质 B,我们类比 DLX 维护双向十字链表,旋转时将子矩阵的外围指针断开,按照新的位置关系连回去。单次修改的复杂度 O(n)。

对于加法操作,直观的想法是做二维差分,但直接维护差分矩阵是困难的。我们考虑将差分值放到十字链表的指针上,对于一个格子,维护其四个方向的权值差:

于是加法操作找到修改矩形的四周,更新一对指针的差值即可。输出矩阵只要根据差值推一遍。

我们注意到,旋转不改变 4 条边的相对循环顺序,只要知道返祖边的方向,在其上加一个偏移量就能找到正确方向。不妨在 n \times n 的矩阵外围建一圈不会被旋转的哨兵节点,从哨兵点出发容易找到操作矩形。

旋转需要进行断边重连,注意到上述寻找过程可以同步求出每个点的真实权值,故直接用真实值更新权值差即可。

复杂度 O(n^2+nq)。实现时可以维护迭代器类似物,记录当前朝向和父亲节点,简化代码编写。代码。

【3】P7447 [Ynoi2007] rgxsxrs

我们使用倍增值域分块,将 [B^k,B^{k+1}) 中的数分到一块,得到 \log_B V 块。修改时:

对于每块开一棵线段树,下标为原序列的下标,线段树上维护区间和,区间 \max 和区间 \min。考虑三种块怎么修改:

类似势能线段树地,维护当前内非零数字的个数,在 \text{max} \le x 或区间为空时剪枝。注意到跌落只会执行 \log_b V 次,均摊复杂度是对的。

视 n,q 同阶,复杂度可以分析到 O\left(n\dfrac{B}{\log B} \log n\log V\right),空间 O(n \log_B V)。实现。

可以使用平衡树代替线段树,空间做到线性但时间常数过大。考虑对线段树底层分块,长度 \le \log n 的节点直接暴力,时间不变的情况下空间优化到线性。

取略大的 B 以平衡时空常数,微调底层分块的阈值后可以通过。我的实现取 B=14,对底层按 16 分块可稳定通过。代码。

【2】P5066 [Ynoi Easy Round 2014] 人人本着正义之名

考虑用 FHQ 维护 01 连续段,区间推平时直接在平衡树上二分出对应区间,然后插入新的连续段。根据颜色段均摊的理论,这个复杂度是对的。

列出 \text{and} 和 \text{or} 运算的真值表,可以得到题目四种操作的本质:

我们用 FHQ 维护维护 01 极长颜色段,修改时仍然二分出对应区间,并用 tag 标记不同段的收缩 / 扩展情况,注意对端点处精细讨论。

这里的颜色段均摊要求极长,所以还需要思考一下实现。比较简单的方案是,平衡树维护颜色段类型和长度,插入新段时前驱后继看是否能合并。注意修改时对两端的颜色段要特殊讨论。

缩段比较复杂,我们需要及时删去长度 \le 0 的段并合并两侧。考虑 FHQ 上维护节点长度的 \min,暴力递归整树对失效段重构,长度 \min \ge 1 就剪枝,势能分析下来复杂度是对的。

区间和则记录额外信息,对每个颜色段讨论它对总和的贡献,标记下传是可以处理的。视 n,q 同阶复杂度 O(n \log n)。代码。

【1】P12127 [蓝桥杯 2024 省 B 第二场] 最强小队

枚举子序列的端点 i,k,则答案为区间 (i,k) 中小于 \max(a_i,a_k) 的数的数目 +2。

分讨 a_i,a_k 的大小关系,下面以 a_i \ge a_k 为例。贪心地,取 a_i \ge a_k 且最大的 k 不劣,在后缀 \max 数组上二分即可。

我们求出 2n 对候选的 (i,k) 后,问题转化为静态 3-side 矩形数点,将 3-side 差分成 2-side 后扫描线配合树状数组解决。复杂度 O(n \log n)。

【1】P15761 [JAG 2025 Summer Camp #1] Colored Tree and Path

考虑线段树维护哈希,询问时提取 u_1 \to v_1 和 u_2 \to v_2 树链对应的线段树,将两棵树作差后在线段树上二分。

多项式哈希和 Sum Hash 都具有可减性,实现采用了双模多项式哈希。

我们求出每个点到根链的线段树,则树链的线段树可以用树上差分的方法求出。使用可持久化线段树预处理,询问在八棵线段树上同步二分即可,复杂度 O(q \log n)。代码。

【3-】P7880 [Ynoi2006] rldcot

转 l-r 二维平面分析,枚举 (i,j) 并将该坐标处的颜色设为 \text{dep}_{\text{lca}(i,j)},则询问是 2-side 矩形数颜色。

取固定的 l,对于颜色 u,若它在 x \ge l 的区域存在多个点,则只需保留 y 坐标最低的点以落入 y \le r 的询问区域。

对 x 轴降序扫描线,维护 f_u 为 x \ge l 且颜色 =u 的点的 y_{\min}。询问是求 f_u \le r 的 u 的数目,以 f 为下标开树状数组即可。

注意到 (i,j) 有 O(n^2) 对,复杂度不可接受。事实上,我们可以只保留一部分点对。

考虑 [l_1,r_1] \subseteq [l_2,r_2] 且 \text{lca}(l_1,r_1)=\text{lca}(l_2,r_2)=x 的点对 (l_1,r_1) 和 (l_2,r_2),可以发现 (l_2,r_2) 是无用的。因为 (l_1,r_1) 可以支配 (l_2,r_2),也即统计 (l_2,r_2) 时一定统计了 (l_1,r_1),则 (l_2,r_2) 对颜色数没有贡献。

我们只要保留不被支配的这些点对,这属于第一类支配对。

考虑在 x 处统计 \text{lca}(i,j)=x 的 (i,j)。由于支配关系是极短的,我们只要对每个 i 找到最小 / 最大的 j 满足 \text{lca}(i,j)=x,则 (i,j) 必为支配对。

我们用一个 std::set 维护子树内所有点的标号构成的集合,在 x 处继承重儿子,暴力枚举轻子树每个点,查出前驱后继后更新支配对,在枚举结束后合并 set。

根据树上启发式合并的理论,上述算法求支配对的复杂度为 O(n \log^2 n),且支配对的数目为 O(n \log n)。

我们只要保留这 O(n \log n) 个支配对,此时再进行 2-side 矩形数颜色即可。复杂度 O(n \log^2 n+q\log n)。代码。

【2+】P8528 [Ynoi2003] 铃原露露

容易树上启发式合并求出 O(n \log n) 个第一类支配对,只需注意前驱后继是在 a_i 中求得的。

考察支配对 (x,y,z),其中 a_x \le a_y 且 z=\text{lca}(x,y),则需要 \forall [a_x,a_y] \subseteq [L,R], a_z \in [L,R]。故 (x,y,z) 会否定掉 [a_x,a_y] \subseteq [L,R] \land a_z \notin [L,R] 的区间。

转 l-r 二维平面分析,则支配对的否定范围是两个 3-side 矩形加法,询问是求 2-side 矩形中点权为 0 的整点数。

将修改差分后对一维扫描线,用数据结构维护另一维,可以发现这是一个扫描线历史和问题,数据结构需要支持区间加,区间求历史 0 个数,保证非负。

记 i 处的历史信息为 h_i。设线段树节点 [l,r] 内的最小值为 \text{mn},其出现次数为 \text{cnt},我们将最小值和非最小值分开维护:

区间 +\delta 的矩阵为 \begin{bmatrix}1 &0& \delta \\0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}。更新历史信息时,若根节点 \text{mn}=0,则对根节点的 V_1 左乘 \begin{bmatrix}1 &0& 0\\0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix},否则忽略操作。可以发现,标记矩阵也需要分最小值和非最小值维护 M_1 和 M_2。

考虑 pushdown 的实现。注意到区间内元素的相对大小不变。设父节点 u,子节点 v,类似 SegBeats 下传进行讨论:

这样我们得到了 O(3^3 q\log n) 的做法。进行半群优化,只维护形如 \begin{bmatrix}1 &0& A\\0 & 1 & B \\ 0 & 0 & 1\end{bmatrix} 的标记即可,且 M_1,M_2 的 A 标记总相同,只需要存一个。

最终复杂度 O(n \log^2 n+ q\log n)。代码。

【2】CF765F Souvenirs

钦定 i<j。转 l-r 二维平面分析,将坐标 (i,j) 的权值定义为 |a_i-a_j|,则查询是 2-side 矩形求 \min,我们需要减少点对数,这属于第二类支配对。

不妨设 a_j \ge a_i,对于 a_j<a_i 的情形同理。

取固定的 i 向右扫描,则 j >i \land a_j \ge a_i 的最小的 j 形成的 (i,j) 必然是支配对。考虑下一个位置 k 满足 i<j<k 且 a_i \le a_j:

根据推导,每向右寻找一次支配对 (i,k),差值至少折半,故 k 只会有 O(\log V) 个,支配对的总数为 O(n \log V)。

我们倒序扫描 i=n \to 1,使用权值线段树维护值域区间内的最小下标。对当前位置 i,设值域上界 R=+\infty,我们在线段树 [a_i,R] 上查询最小的 j,则 (i,j) 为支配对。令 R \gets a_i +\lfloor \frac{a_j-a_i-1}{2}\rfloor 重复上述过程,直到 j 不存在结束这个过程,内层循环至多 O(\log V) 轮。

求出所有支配对后,问题转为静态 2-side 矩形数点,扫描线配合树状数组即可。

复杂度 O(n \log n \log V+q\log n)。代码。

【2】P9678 [ICPC 2022 Jinan R] Tree Distance

转 l-r 二维平面分析,将点对 (i,j) 的权值视作 \text{dis}(i,j),询问是 2-side 矩形求 \min,但点对数量不可接受。

根据第二类支配对的理论,考虑对信息维分治。直接拆开 \text{dis} 会涉及 LCA 深度,这启发我们任意定根后,用点分治的方法枚举 LCA 为 x,钦定 \text{lca}(i,j)=x 后在 x 子树内求支配对。

记 \text{dis}(u,x)=f_u。考察三点 i<j<k,则 (i,k) 被 (i,j) 支配的条件为 f_j \le f_k。取固定的 k,求出点集 S=\{u \mid f_u \le f_k\},则 k 与它在 S 中的前驱后继形成了支配对。

我们将子树按 f 升序排序并扫描,用一个 std::set 维护已扫描点的标号,扫到 u 时查询其前驱后继作为支配对即可。

最后的问题是 2-side 矩形数点,扫描线树状数组即可。复杂度 O(n \log^2 n+q \log n)。代码。

【2】P5607 [Ynoi2013] 无力回天 NOI2017

将 |S_i \cup S_j| 容斥为 |S_i|+|S_j|-|S_i\cap S_j|,问题转化为求集合交。直接维护每个 S_i,复杂度难以低于 O\left(\dfrac{n^2}{w}\right)。

考虑取对偶范围,维护 T_x=\{i \mid x \in S_i\}。我们对 |T_x| 阈值分治,设阈值为 B,则 |T_x|>B 的 x 至多 \dfrac{n}{B} 个。

可以将询问离线后划分两类 x。取 B=\sqrt{\dfrac{n}{w}} 得最优复杂度 O\left(\dfrac{n^{1.5}}{\sqrt{w}}\right)。

对时空常数的若干优化:

添加这些优化后足以通过。代码。

【1】P4689 [Ynoi Easy Round 2016] 这是我自己的发明

只考虑查询操作。子树条件可以用 DFS 序转化,问题变为 x \in [l_1,r_1] \land y \in [l_2,r_2] \land a_x=a_y 的 (x,y) 对数。

在 l-r 二维平面上,(x,y) 的范围是 4-side 矩形,将其差分为 2-side,则只要对 x \le l\land y \le r 求 a_x=a_y 的数目。这是经典的莫队问题,用桶配合普通莫队即可解决。

现在考察换根操作。实际上,换根意义下的子树 DFS 序只有 \le 2 段。设原树根为 r_0,在 r_0 意义下求 DFS 序后,当前树根换为 r,讨论 x 子树的 DFS 序:

对于 DFS 序分段的情况,只需要拆成多个 4-side 矩形并差分。

复杂度 O(n \sqrt{q} +q \log q)。代码。

【1+】P5072 [Ynoi Easy Round 2015] 盼君勿忘

将贡献拆到数值上。设区间长度为 m,数字 x 出现 k 次,只要在 k 个位置中选择至少一个,方案数 2^m-2^{m-k}。记出现 k 次的数的总和为 f(k),答案为 \sum \limits_{k=0}^m f(k) \times (2^m-2^{m-k})。

注意到序列中本质不同的 k 至多 \sqrt{n} 种,直接使用 Hash 表维护 f,询问时扫描整表进行求值即可。

求值时需要计算 2^{m-k} \bmod p,使用 O(1) - O(\log m) 的快速幂会得到 O(\sqrt{m} \log m) 的复杂度。可以使用 O(\sqrt{m})-O(1) 的光速幂进行平衡。

实际上还有另一种手法,我们将快速幂的查询记忆化,求 2^x \bmod p 时找到 y \le x 且最大的 y,只要倍增 2^{x-y} \bmod p,复杂度 O(\log (x-y))。应用微积分知识可以证明复杂度是单根号的。

由于哈希表操作会被调用 O(n \sqrt{q}) 次,常数过大而无法通过。我们可以用双向链表维护有值位置,将哈希表改成普通数组减少常数。

总复杂度 O(n \sqrt{q}+q \sqrt{n})。代码。

【1+】P15534 【MYCOI R1】那猫猫城的集市

先考察 f_i 的性质。由于 f 都是对换操作,故 f 有交换律且 f \circ f =\text{id}。查询是离线静态树链函数复合。

考虑如何维护当前总复合 F。我们用两个数组记录 F 和 F^{-1},则 F \gets f_i \circ F 只需将 F^{-1}(a_i) 和 F^{-1}(b_i) 交换,并更新 f 的点值。对树 DFS,回溯时撤销 f_i 的复合,则节点 u 处的 F_u=f_u \circ f_{\text{fa}(u)} \circ \cdots \circ f_1 且反函数 F^{-1}=f_{1} \circ \cdots \circ f_{\text{fa}(u)} \circ f_{u}。

任意定根后,设 p=\text{lca}(u,v),我们将 u \to v 拆成 u \to p 和 p \to v 部分,对这两段分别 DFS 求解。

先考虑 u \to p 的询问,使用插入—标记—回收算法,在节点 u 处记录 y=F_u^{-1}(x),在节点 p 时查询 (f_p \circ F_p)(y) 即为答案。注意采用后序遍历的处理顺序。

考虑 f_p(y)=(F_p \circ F^{-1}_u)(x),我们写出两个函数的来源:

\begin{aligned} F_p&=f_p \circ f_{\text{fa}(p)} \circ \cdots \circ f_{1}\\ F_u^{-1} &= f_1 \circ \cdots \circ f_{\text{fa}(p)} \circ f_p \circ \cdots \circ f_u \end{aligned}

根据 f_i \circ f_i =\text{id},上下两式复合后中间部分抵消,必有

f_p \circ F_p \circ F_u^{-1}=f_p \circ \cdots \circ f_{\text{fa}(u)} \circ f_u

这恰为 u \to p 的复合函数。

得到中间结果 (f_p \circ F_p)(y) 后,我们继续完成 p \to v 的求解,方法类似。注意 DFS 顺序是先序遍历,以及过程中不应复合 f_p。

复杂度 O(n \log n+q),瓶颈在求 LCA。代码。

【1】P5354 [Ynoi Easy Round 2017] 由乃的 OJ

以一个 \log 的代价,使用重链剖分拍到序列上。

注意到 f 只有位运算,对每个二进制位独立,考虑拆位处理。线段树节点维护两个 64 位数组,表示第 i 个二进制位初始为 0/1 时,区间复合函数的点值,信息可以合并。

这样我们就得到了半群信息。注意信息没有交换律,树剖询问时需要按照 u \to v 的方向跳重链,线段树上还要维护反串信息。

得到信息后,从高位向低位贪心,对第 d 位,若填 0 得 1 则最优,否则若 k \ge 2^d 且填 1 得 1 则令 k \gets k-2^d。

总复杂度 O(n \log^2 n \log V) 难以通过。

注意到这个 64 位数组的值域为 \{0,1\},考虑直接压成 u64 存储,信息合并实现并行计算,复杂度优化到 O\left(n\log^2 n \dfrac{\log V}{w}\right),可以视作去掉了 \log V。代码。

【3】P6666 [清华集训 2016] 数据交互

容易发现撤销操作是假的,插入路径 (u,v) 并将权值设为 -w 即可,得分可以抵消,故下面只考虑插入。

考虑刻画 (u,v) \cup (x,y) \ne \varnothing 的条件,可以将其不重不漏地分为两类:

枚举 z,只要求过 z 的路径 (u,v) 权值和。设 f_u 为过点 u 的路径权值和,则修改是对 f 树链加,查询是单点求 f_z。

类似地,可以发现只要求 p \in (x,y) \setminus \{z\} 的 (u,v) 权值和。设 g_u 为 LCA 为 u 的路径权值和,则修改是对 g_{\text{lca}(u,v)} 单点改,查询是求 (x,y) \setminus \{z\} 树链和。

我们可以将答案写成

\max_{z=1}^n\left( f_z+\max_{\text{lca}(x,y)=z} \sum \limits_{(x,y) \setminus \{z\}} g_u\right)

先考虑单次查询怎么做。记 h_u 为路径 (u,v) 的最大 g 和,其中 v \in \text{subtree}(u),则 h 可以自底向上地转移

h_u=\max\left(0,g_u+\max_{v \in \text{son}(u)} h_v\right)

我们在 z 处取多重集 S_z=\{h_v \mid v \in \text{son}(u)\},记 a_z=\max S_z+\text{semax } S_z,则 z 处的答案就是 f_z+a_z,其中 \text{semax} 为次大值。

对 S_z 轻重分离,设 S'_z=\{h_v \mid v \in \text{lson}(z)\},记 q_z=\max S_z',b_z=\max S'_z+\text{semax } S'_z,则 z 处的答案为

f_z+a_z=\max\left(f_z+b_z, f_z+h_{\text{hson}(v)}+q_z\right)

这个转移可以用 3 \times 3 的 (\max,+) 矩阵表示:

\begin{bmatrix} h_u \\f_u+a_u \\ 0 \end{bmatrix} = \begin{bmatrix} g_u &-\infty & \max(0,g_u+q_u)\\ f_u+q_u &0 & f_u+b_u\\ -\infty & -\infty & 0 \end{bmatrix} \begin{bmatrix} h_{\text{hson}(u)} \\f_{\text{hson}(u)}+a_{\text{hson}(u)} \\ 0 \end{bmatrix}

对树重链剖分,在重链 DFS 序上维护线段树 T。对修改操作进行讨论:

答案即为所有重链答案的 \max,可以在全局用一个 multiset 维护。

复杂度 O(3^3 q \log^2 n)。代码。

【1+】P5987 [PA 2019] Terytoria

我们可以在 x 轴上取 [x_1,x_2] 或其补集,在 y 轴上取 [y_1,y_2] 或其补集,故两个维度是独立的,分别求解后将答案相乘即为所求。

将问题描述为,给定 n 个区间 [l_i,r_i],每个区间可以取 [l_i,r_i] 或 [1,l_i) \cup (r_i,n],最大化被所有区间覆盖的位置数。

对坐标离散化后枚举 x,钦定 x 位置最终被覆盖,则需要对 x \in [l_i,r_i] 的 [l_i,r_i] 区间 +1,对 x \notin [l_i,r_i] 的 [1,l_i) \cup (r_i,n] 区间 +1。答案为 =n 的位置数。

对 x 扫描线,将 [l_i,r_i] 挂在 x 进入和离开的两个时刻,总共只需要 O(n) 次区间 \pm 1,查询 =n 的位置数。比较简单的半群构造是,维护区间 \max 和 \max 个数。复杂度 O(q \log n)。

另解:设 S_x 为覆盖 x 位置的线段集合,按照 S_x 对位置划分等价类,取出元素个数最多的等价类即为最优。

比较两个集合是否相同,容易想到 Sum Hash。对每个区间随机两个整数 a_i,b_i,令区间 [l_i,r_i] 加上 a_i,区间 [1,l_i) \cup (r_i,n] 加上 b_i。两个整点的 Hash 值相同就认为 S_x 相同。

前缀和优化即可,复杂度 O(n \log n),瓶颈在离散化。代码。

【0】CF1093G Multidimensional Queries

考虑将 k 维 Manhattan 距离转换为 Chebyshev 距离。注意到如下结论

\sum_{i=1}^k |a_i-b_i|=\max_{x} \sum_{i=1}^k (-1)^{x_i} (a_i-b_i)

其中 x 是长为 k 的序列,且 x_i \in \{0,1\}。

我们可以将两个 \max 合并成一个,O(2^k) 地枚举所有 x 序列,线段树维护即可。复杂度 O(2^k q \log n)。

【1】ABC295E Kth Number

01 转化 trick。观察如下代数式

\sum_{a} a_k=\sum_{a}\sum_{i=1}^{m} [i \le a_k] = \sum_{i=1}^m \sum_a [i \le a_k]

考虑枚举 i \in [1,m],对 i \le a_k 的 a 序列计数。不妨计数 a_k<i 的 a 序列数目。

设初始空位有 c 个,原本 <i 的数有 x 个。枚举最终 <i 的位置的数目 j,进行分步计数:

由乘法原理合并,写出答案式

\sum_{i=1}^m\left( m^c-\sum_{j =\max(x,k)}^{c+x} \binom{c}{j-x}(i-1)^{j-x}(m-i+1)^{c-j+x}\right)

除以 m^c 即为期望。复杂度 O(nm)。

【2】QOJ17957 RPS Bubble Sort

我们考虑只有两个字符的情况,此时二元关系是全序,则输掉的位置会前移若干位,可以直接算出来。

对原序列分段,保证每段都是只有两个字符的极长段。关键观察是,不存在跨区域交换的字符。原因是某个区域内的赢家一定不能打赢另一个区域。

复杂度 O(n)。代码。

【1】P16968 [SCCPC 2026] 博德之跃 3

不妨将第三种操作描述为,若 S 的首尾字符相同,则同时删去后添加一个到 T 的末尾。

若 S 的首尾字符不相同,显然应该放字典序小的那个。

若 S 的首尾字符均为 x。先判掉 S 全由 x 组成的情况,此时 x 放的越少越好。

考察左侧第一个不同字符 y 和右侧第一个不同字符 z。则 x 放多放少需要根据 y,z 来决策。

这就是本题的贪心策略。实现的时候可以拿两个指针维护 S 的首尾位置,预处理每个位置左 / 右侧最靠近的不同字符。复杂度 O(n)。代码。

【0】AGC007A Shik and Stone

若路径上两点满足右上—左下关系则不合法。

【1】AGC007D Shik and Game

注意到,最优策略每次回头收集硬币时,一定走到最远的未收集位置。根据性质设计 DP:

复杂度 O(n^2),考虑优化 DP。对 \max 分类讨论:

两种情况的分界点可以二分求出。使用线段树优化 DP,支持单点修改,区间求 \min 即可。

复杂度 O(n \log n)。代码。

【2】P14568 【MX-S12-T3】排列

注意到我们只关心元素的相对大小。尝试按位置考虑,从左到右依次决定 p_i 在 p_1 \sim p_i 中的排名。

设当前考虑 p_i,其排名为 x。对四种限制进行分讨:

我们发现,随着 i 的增加,可用的排名区间 [l,r] 不断收缩。设 k=r-l+1,观察四种限制对 k 的影响:

上述讨论说明,我们不必将 [l,r] 放入 DP 状态,直接将 k 作为 DP 的第二维即可转移。

值得说明的是,仅用 k 转移可能会忽略一些情况。例如,前缀 \min 强制 x=1,但如果当前下界 l>1 就不可能选到 x=1。我们发现这种矛盾是静态的,即后缀 \min 之后又出现前缀 \min,当作无解判掉即可。

现在可以列出插入 DP:

瓶颈在 f_{i,k}=\sum\limits_{k' \in [k,i]}f_{i-1,k'} 这个转移,对 f 施加后缀和优化,复杂度 O(n^2)。

【2】P5471 [NOI2019] 弹跳

4-side 矩形连边不可差分,容易想到 KDT 优化建图,边数为 O(m \sqrt{n}),空间无法接受。

考虑模拟 Dijkstra 最短路,我们需要支持下面的操作:

我们用 KDT 维护这些操作。查询全局 \min 可以提取根节点答案,删除 u 则单点修改 \text{dis}_u \gets +\infty。松弛操作是 4-side 矩形 chkmin,可以打标记维护。

这样 KDT 只要存 O(m) 的空间,时间 O(n \log n+m \sqrt{n})。

注意对 KDT 进行最优性剪枝,维护节点 \max,若标记 >\max 则终止,可以通过原题数据。QOJ TLE on extra test#4。代码。

【1】P6134 [JSOI2015] 最小表示

考虑边 u \to v,若 u 可以间接到达 v,则 u \to v 的边没有用,可以删掉。

求出每个点的可达点集后,枚举每条边,若 u 的可达集和可达 v 的点集有交,这条边就能删掉。因为图是 DAG,删掉以后不影响其他可达性的判断。

bitset 优化,复杂度 O\left(\dfrac{nm}{w}\right)。

【1+】AGC020C Median Sum

设 S=\sum a_i,所有子集和关于 S/2 对称。不考虑空集的情况下,所求即为 \le S/2 的最大子集和。

用 bitset 维护可行性 dp,表示能否凑出某个子集和。复杂度 O\left(\dfrac{n^2 V}{w}\right)。

【1】P14057 【MX-X21-T2】[IAMOI R5] 空气蛹

神人题目。

特判掉初始序列有序。注意到有一个空桶的话,令 tmp = a, a = b, b = tmp 即可交换两个位置。对 a 排序后,最小损失为 a_1+a_2-m。

【1+】P5904 [POI 2014] HOT-Hotels 加强版

设 x =\text{lca}(a,b,c),必有 \text{dis}(x,a)=\text{dis}(x,b)=\text{dis}(x,c)。将 (a,b,c) 挂在 x 处统计,要求 a,b,c 分居 x 的不同子树。

将三元组拆成“1+2”统计。记 f_{u,d} 为 v \in \text{subtree}(u)\land \text{dis}(u,v)=d 的 v 的数目,g_{u,d} 为 a, b \in \text{subtree}(u) \land \text{dis}(u,a)=\text{dis}(u,b)=d 且 a,b 分居不同子树的 (a,b) 点对数,逐子树加的过程中,利用 f 可以转移 g:

f_{u,d} \gets f_{v,d-1}\\ g_{u,d} \gets f_{u,d-1} \times f_{v,d-1}

答案为 \sum g_{u,d} \times f_{v,d-1}。复杂度 O(n^2)。

对树高启发式合并,f 的维护是容易的,可以在对位加过程中转移 g。继承 g 需要 g_{u,d} \gets g_{v,d+1} 的前移。

使用 vector 实现,f 倒序存储,g 顺序存储,并对 g 维护下标偏移量,表示头部的若干位置被删除。

复杂度 O(n)。由于 10^5 不卡空间,实现直接采用了 deque。代码。

【1】CF2025F Choose Your Queries

不难发现选择 d 的策略必为,若 a_p=0 则 d=+1,否则 d=-1。设 i 被操作了 d_i 次,则 a_i=d_i \bmod 2。

考虑连边 x_i \leftrightarrow y_i,决策是对无向边定向,最小化奇入度点数。

对于某个点的入边,我们将问题描述为,将入边两两匹配,若全能匹配则为偶入度点,否则为奇入度点,只要最大化匹配数。

然后就是 CF1519E 的套路了,拉出 DFS 树自底向上贪心,保证每棵子树内最多剩下一条未匹配边,在当前点将不匹配边配对,这样向上传递的边也至多剩下一条。

根据定向方案输出构造即可,时间复杂度线性。

【2】P9718 [EC Final 2022] Best Carry Player 2

没想到数位 dp。

从低位向高位 dp,设 f_{i,j,0/1} 为低 i 位恰好进位 j 次需要的最小加数,0/1 表示第 i 位向高位的进位。

转移时直接枚举这一位填什么,新的 j 和进位状态都能算出来。

实现有很多细节,比如判 k=0,判前导零,后导零爆 ll 什么的。代码调不出来开摆了。

【1】P13994 【MX-X19-T3】「LAOI-14」Another Round

枚举 mex,那么相当于钦定一些位置必须选,一些位置可以选。

如果可选位置全都不选更新一个答案,可选位置选一个的话必然选到全局 \max 的位置。查询做个前缀 \max 即可。

【1+】P6186 [NOI Online #1 提高组] 冒泡排序

设 f_i 为 j<i \land a_j>a_i 的 j 的数目。可以证明,一轮冒泡的影响是对 f 前移一位,非零位置 -1。答案为 \sum \max(f_i-k,0)。

用权值树状数组维护 f,只要知道 \ge k 的 f 的个数 & 和即可查询。交换操作只会让两个位置的 f 改变,且改变量是好统计的。复杂度 1log。

【1】P3332 [ZJOI2013] K 大数查询

查询对值域二分转化为求排名。

转二维平面分析,则修改是插入点 (l,x) \sim (r,x),询问是 3-side 矩形数点。

考虑使用树套树维护二维平面。注意到区间插入难以在外层树上实现,不妨交换维度,用外层树维护 y 轴,内层树维护 x 轴。

选用树状数组作为外层树,动态开点线段树作为内层树,修改是对外层树单点修改,对内层树区间加。查询是外层树的缀后查询,内层树的区间求和。复杂度 O(q \log^3 n),代码。

在外层树状数组上倍增即可优化到 O(q \log^2 n)。代码。

【1】P6670 [清华集训 2016] 汽水

建议降蓝。

分数规划问题,考虑二分答案 x,不难列出不等式

\begin{aligned} &\left|\dfrac{1}{|P|}\sum \limits_{e \in P}w_e-k\right| < x\\ -x &< \dfrac{1}{|P|}\sum \limits_{e \in P}w_e-k < x\\ (k-x)|P| &< \sum \limits_{e \in P}w_e < (k+x)|P|\\ &\left\{\begin{matrix} \sum\limits_{e \in P}(w_e-(k+x)) < 0\\ \sum\limits_{e \in P}(w_e-(k-x)) > 0\ \end{matrix}\right. \end{aligned}

令 p_e=w_e-(k+x), q_e=w_e-(k-x),问题转化为判定 \exists P, \sum p_e < 0 \land \sum q_e > 0。

:::::info[点分治]

考虑点分治,从分治中心 u 自顶向下求出 a_v,b_v,表示 u \to v 路径边的 p,q 和。设 v 所属的子树标号为 c_v,只要在 u 处判定

\exists (u,v), a_u+a_v < 0 \land b_u+b_v > 0 \land c_u \ne c_v

限制似乎是三维偏序。考虑对 a_u 排序扫描线,则 a_v < -a_u 的 v 必为一段前缀,只要找到 b_v > -b_u 且 c_u \ne c_v 的 v。

套路地维护 b 的最大值和次大值,并钦定最大值和次大值所属子树不同,只要检查对应的前缀 \max 后。扫描线部分除排序外线性。

:::::

:::::info[边分治]

对树三度化后边分治,问题转化为,给定两对序列 (a_u,a'_v), (b_u,b'_v),在当前层判定

\exists (u,v), a_u+a_v' < 0 \land b_u+b'_v > 0

将 (a_u,b_u) 和 (a_v',b_v') 升序排序,枚举 u,则 a'_v < -a_u 的 v 是一段前缀,预处理 b' 的前缀 \max 即可。

:::::

最终复杂度 O(n \log^2 n \log V),\log 分别是二分,树分治,排序。代码(点分治)。

【0】LOJ6145「2017 山东三轮集训 Day7」Easy

点分治以后只要求 \min \limits_{y \in [l,r]} (d_x+d_y)。求 \min 的话,把 LCA 算浅不优,所以可以丢掉 x,y 分居不同子树的限制。在点分树上每个点对子树维护静态 RMQ 即可。

【1?】P4220 [WC2018] 通道

对 T_1 边分治,对 T_2 在边分虚树上边分治,对 T_3 建立边分虚树后 dp。问题大概形如有两个数组 a,b,最大化 a_u+b_v+\text{dis}_3(u,v),记录每个点下去的 a+\text{dis} 和 b+\text{dis} 的 max 即为,dp 过程逐子树加可以更新答案。

不知道 3log 能不能过,似乎基排建虚树是 2log 的,或许能过,只是口胡。

【0】CF1706E Qpwoeirut and Vertices

建出 kruskal 重构树后问题等价于求区间两两 lca 的点权 max。根据 24noip t4 结论,取 \text{lca}(i,i+1) 的点权算答案即可,静态 rmq 带走。

【0】P4197 [ONTAK2010] Peaks

拉出 kruskal 重构树,树上倍增找到点权 \le x 的最浅点,则子树内的实点都可达,问题变成子树 kth,拍个 dfs 序然后函数式线段树即可。

【1】P4899 [IOI 2018] werewolf 狼人

对点权建立两棵 Kruskal 重构树 T_1,T_2,分别维护 \min 和 \max,则中转点 u 合法当且仅当 a_{\text{lca}_1(s,u)} \ge l 且 b_{\text{lca}_2(u,t)} \le r。

考虑对 T_1 求出 a_{\text{lca}_1(s,u)} \ge l 的 u 组成的集合,T_2 同理,只要判定两个集合交集是否为空。

我们在 T_1 上倍增,求出最浅的 s 的祖先 u 满足 a_u \ge l,则 u 子树内所有点均合法。问题转化为判断两子树是否有交。

使用 DFS 序拍到序列上,问题转化为 4-side 矩形数点,差分成 2-side 后扫描线配合树状数组即可。复杂度 O(m \log m+q \log n)。

【1】CF1777F Comfortably Numb

设 $a_i$ 序列的前缀异或和为 $s_i$,只要求 $a_m \oplus s_r \oplus s_{l-1}$ 的最大值。枚举一侧后可以在 01-Trie 上贪心求得答案。 对 $s_i$ 建立可持久化 01-Trie,在另一侧区间的 01-Trie 上贪心即可。枚举短的一侧算答案,复杂度 $O(n \log n \log V)$。 ## 【0】[P5502 [JSOI2015] 最大公约数](https://www.luogu.com.cn/problem/P5502) 注意到 $x \gets \gcd(x,v)$ 使得 $x$ 改变至多 $O(\log V)$。用 ST 表维护区间 gcd,枚举 $l$,二分找到最右的不改变 gcd 的 $r$ 更新答案即可,复杂度 $O(n \log n \log V)$。 某种意义上属于第二类支配对“每个 $i$ 有 $\log$ 个 $j$”这种模型? ## 【1+】[P11368 [Ynoi2024] After god](https://www.luogu.com.cn/problem/P11368) 对着题意做需要单侧递归线段树维护历史和,复杂度 2log 无法通过。 转 $i-t$ 二维平面分析,则 $a_i$ 是关于 $t$ 的分段常函数,段数总和 $\le n+q$。每个线段对开口向上的 3-side 矩形 chkmax,询问是 2-side 矩形求和。 对 $i$ 轴扫描线,数据结构维护时间轴。扫描线每次移动时,更新历史和拼出询问答案,故我们需要区间 chkmax,更新历史和,查询前缀历史和。 ![](https://cdn.luogu.com.cn/upload/image_hosting/pynv047q.webp) 可以用 SegBeats 配合历史和半群。我们用向量—矩阵法构造半群,信息设计为 $\begin{bmatrix} \sum a_i \\ H \\ \text{len}\end{bmatrix}$,其中 $H$ 是历史和,$\text{len}$ 是区间长。信息合并是对位加,修改操作为: - 区间 $+v$:$\begin{bmatrix} \sum (a_i+v) \\ H \\ \text{len}\end{bmatrix}=\begin{bmatrix} 1 & 0 & v \\ 0 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix} \sum a_i \\ H \\ \text{len}\end{bmatrix} $。 - 更新历史和:$\begin{bmatrix} \sum a_i \\ H+\sum a_i \\ \text{len}\end{bmatrix}=\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix} \sum a_i \\ H \\ \text{len}\end{bmatrix} $。 标记复合是矩阵乘法。进行半群优化,只维护 $\begin{bmatrix} 1 & 0 & A \\ B & 1 & C\\ 0 & 0 & 1\end{bmatrix}$ 形式的标记即可。 现在将半群套用到 SegBeats 上。将标记分成两类,专门作用于最小值和非最小值,标记下传时对最小值和严格次小值分别处理即可。 视 $n,q$ 同阶复杂度 $O(n \log n)$。[代码](https://www.luogu.com.cn/article/azkh91jv)。 ## 【1】[P8512 [Ynoi Easy Round 2021] TEST_152](https://www.luogu.com.cn/problem/P8512) 考虑对 $r$ 扫描线,对每个位置 $i$ 维护 $f_i$ 表示 $i$ 最后被操作的时刻,则 $a_i$ 对询问 $(l,r)$ 有贡献当且仅当 $f_i \ge l$。 注意到只有区间推平操作,可以用 set 维护颜色段均摊,连续段上记录修改时间。以 $f$ 为下标开树状数组,每次修改只会改 $O(1)$ 个位置,查询是后缀求和。 视 $n,m,q$ 同阶复杂度复杂度 $O(n \log n)$。[代码](https://qoj.ac/submission/2987597)。 ## 【1】[GYM106589K 街树的影子](https://codeforces.com/gym/106589/problem/K) 去掉互相包含的贡献后,面积是若干直角梯形,单调栈扫一遍就是线性的。 ## 【1】[AT_kupc2021_c Gacha](https://www.luogu.com.cn/problem/AT_kupc2021_c) 由于本人一开始读错题了,所以文章中的 $a,b$ 是反的。 设 $f_i$ 为遍历前 $i$ 个游戏机,当前位于 $b_i$ 处的最小代价。转移枚举上一个游戏机 $j$,则 $j \to i$ 的策略为: - 从 $b_j$ 走到 $a_i$,收集沿途硬币,代价 $|a_i-b_j|$。 - 从 $a_i$ 走到 $b_{j+1}$,代价 $|a_i-b_{j+1}|$。 - 从 $b_{j+1}$ 走到 $b_i$,激活沿途游戏机,代价 $b_i-b_{j+1}$。 得到转移方程 $$ f_i=\min_{0 \le j < i} (f_j+|a_i-b_j|+|a_i-b_{j+1}|+b_i-b_{j+1}) $$ 求答案时的策略和上述转移不同,需要单独讨论,方法同理。 按绝对值的取值分讨,不难发现只有如下三种情况: - $b_{j+1} \le a_i$,此时转移为 $f_i \gets 2a_i+b_i+f_j-b_j-2b_{j+1}$。 - $b_j \le a_i \le b_{j+1}$,此时转移为 $f_i \gets b_i+f_j-b_j$。 - $a_i \le b_j$,此时转移为 $f_i \gets b_i-2a_i+f_j+b_j$。 由于 $b$ 数组有序,这三种情况的分界点可以二分出来。用两棵线段树维护 $f_j-b_j-2b_{j+1}$ 和 $f_j+b_j$,支持单点修改区间 $\min$ 即可。复杂度 $O(n \log n)$。 ## 【1】[P17101 [ICPC 2017 Qingdao R] Suffix](https://www.luogu.com.cn/problem/P17101) 正序贪心显然是错的,原因是选的长度不同无法对齐。ABC225F 告诉我们,可以考虑倒着贪心,每次选一段后缀拼到开头,取字典序最小的那个作为下一轮的答案。 用滚动哈希优化这个过程。比较简单的实现是,维护反串前缀哈希,用一个指针表示某段前缀是当前的答案,比较字典序就二分 LCS 取上一位,最后记下来决策点并输出。 复杂度 $O(L \log L)$。 ## 【3】[QOJ12103 Intergalactic ship](https://qoj.ac/problem/12103) ## 【2】[UOJ637 A. 数据结构](https://uoj.ac/problem/637) 转 $l-r$ 二维平面分析。对每个 $x \in [1,n]$,我们在二维平面上刻画 $x$ 有贡献的范围。 不妨考察 $x$ 没有贡献的范围,则全局没有 $x$ 当且仅当: - 原来为 $x$ 的数均执行了 $+1$。 - 原来为 $x-1$ 的数没有执行 $+1$。 对第一个条件,找出 $x$ 的最左最右出现位置 $L,R$,则 $x$ 对询问 $(l,r)$ 无贡献,必有 $[L,R] \subseteq [l,r]$。这是一个开口向左上的 2-side 矩形。 对第二个条件,设 $x-1$ 的出现位置依次为 $p_1 \sim p_k$,则 $\forall i \in [1,k], p_i \notin [l,r]$。不妨设 $p_0=0,p_{k+1}=n+1$,考虑相邻位置 $p_i,p_{i+1}$,必有 $[l,r] \subseteq (p_i,p_{i+1})$,这是 $k+1$ 个开口向右下的 2-side 矩形。 最终贡献范围即为两个条件的交集。可以发现,若 $x$ 在原序列中出现过,须满足 $[L,R]\subseteq (p_i,p_{i+1})$,两个范围的交是一个 4-side 矩形。否则 $x$ 贡献 $k+1$ 个 2-side 矩形。 ![](https://cdn.luogu.com.cn/upload/image_hosting/fqculat2.webp) 由于颜色的出现次数之和是 $O(n)$ 的,总矩形数目 $\le 2n$。预处理出所有矩形,差分成 2-side 后扫描线配合差分树状数组解决。 视 $n,q$ 同阶总复杂度 $O(n \log n)$。[代码](https://uoj.ac/submission/874334)。 ## 【2】[P5537 【XR-3】系统设计](https://www.luogu.com.cn/problem/P5537) 注意到树是静态的,考虑对每个节点 $u$ 求出 $f_u$ 表示 $u$ 在兄弟节点中的排名,则一条路径可以视作若干 $f_u$ 组成的序列。询问即求最深的 $y$ 满足 $x \to y$ 的 $f$ 序列是 $a_l \sim a_r$ 的前缀。 根据多项式哈希的可加性,我们对每个 $u$ 自顶向下地预处理 $\text{root} \to u$ 根链的 $f$ 哈希值 $h_u$,询问二分出最大的 $k \in [l,r]$ 满足 $\exists v, h_v=h_u +\sum \limits_{i=l}^k a_i$,则 $v$ 即为所求。注意这里的 $+$ 是哈希值复合。 可以对 $h \leftrightarrow v$ 建立哈希表,用线段树维护 $a$,复杂度 2log。在线段树上二分即可得到 $O(q \log n)$ 做法。 ## 【1】[CF963D Frequency of String](https://www.luogu.com.cn/problem/CF963D) 我们使用 Shift-And 算法求得 $M$ 在 $S$ 中出现位置的 bitset。利用 `_Find_next` 找出所有匹配位置,设其为 $a_1 \sim a_m$,则答案为 $$ \min_{i=1}^{m-k+1} (a_{i+k-1}-a_i+|M|) $$ 我们声称,暴力扫描 $a$ 序列求答案的复杂度是正确的。这是因为,对 $n$ 个互不相同的模式串 $T_i$,它们在文本串 $S$ 中出现次数之和是 $O\left( |S| \sqrt{\sum \limits_{i=1}^n |T_i|}\right)$ 的。 视 $q,|S|,\sum |T|$ 同阶,总复杂度 $O\left(n \sqrt {n}+\dfrac{n^2}{w}\right)$。[代码](https://codeforces.com/contest/963/submission/391320107)。 ## 【1+】[CF1916E Happy Life in University](https://www.luogu.com.cn/problem/CF1916E) 考虑枚举 $x = \text{lca}(u,v)$,取出各子树的最大值和次大值相乘更新答案,问题转化为,高效维护 $x$ 向下路径的颜色数。 考虑自底向上统计答案,维护 $f_y=\text{col}(x,y)$。遍历到 $x$ 时对 $x$ 子树 $+1$,表示加入颜色 $a_x$。需要去重,套路地求出 $p_u$ 为 $u$ 根链上最深的同色点,对 $x$ 的后代 $u$,若 $p_u=x$,则 $a_x$ 会被算重,将 $u$ 子树再 $-1$ 即可。 完成修改后,$f$ 恰为 $\text{col}(x,y)$。枚举 $v \in \text{son}(x)$,查询 $v$ 子树的 $\max$,取最大 & 次大作为答案。 将 $u$ 挂在 $p_u$ 处进行枚举,则 $u$ 的总枚举次数线性。拍 DFS 序将子树转为区间,线段树维护 $f$ 数组即可。复杂度 $O(n \log n)$。[代码](https://codeforces.com/contest/1916/submission/391373680)。 ## 【2】[AGC032D Rotation Sort](https://www.luogu.com.cn/problem/AT_agc032_d) 不妨将操作描述为,支付 $a$ 的代价对任意一个数右插,支付 $b$ 的代价对任意一个数左插。 容易发现每个数至多操作一次。考虑一个 `0AB` 序列,表示每个数的决策,那么 `0` 的位置一定是个上升子序列,对着这个 dp。 设 $f_i$ 为 $i$ 位置填 `0` 的最小代价,枚举子序列的上一个数 $j$ 满足 $p_i>p_j$,只要算明白 $(j,i)$ 区间的 `AB` 代价就能转移了。 不妨设 $p_0=0,p_{n+1}=n+1$。扫描 $k \in (j,i)$,若 $p_k<p_j$ 则必须左插,$p_k>p_i$ 必须右插。如果 $p_j < p_k<p_i$ 则 $k$ 取 `0` 更优,直接扔掉这个转移。 综上,转移式子是 $$ f_i=\min_{j<i \land p_j<p_i} f_j+\sum_{k=j+1}^{i-1} \left\{\begin{matrix} a & p_k>p_j \\ b & p_k<p_j \end{matrix}\right. $$ 枚举顺序改成先 $j$ 后 $i$,枚举 $i$ 同时维护后面那个和式就是 $O(n^2)$ 的。[代码](https://atcoder.jp/contests/agc032/submissions/79412574)。 ## 【1】[P14050 [SDCPC 2019] Connected Intervals](https://www.luogu.com.cn/problem/P14050) 我们用点减边容斥刻画树上连通块。设 $e(l,r)$ 为 $[l,r]$ 内部的边数,区间 $[l,r]$ 的合法条件为 $r-l+1-e(l,r)=1$,即 $r-l-e(l,r)=0$。 考虑树边 $(u,v)$,不妨设 $u<v$,则这条边对 $[u,v] \subseteq [l,r]$ 的区间都有 $-1$ 的贡献。转 $l-r$ 二维平面分析,边 $(u,v)$ 的贡献范围是开口向左上的 2-side 矩形。 对 $r$ 扫描线,则 $r \to r+1$ 时需要全局 $+1$,枚举下边界为 $r$ 的矩形做前缀 $-1$,查询求全局 $=0$ 的位置数。 注意到权值非负,线段树维护 $\min$ 和 $\min$ 数目的半群即可。复杂度 $O(n \log n)$。 ## 【1+】[QOJ18298 Monochrome Tree](https://qoj.ac/problem/18298) 做不出来这种题,水平有点高。 感性理解一下我们给黑点尽量堆到更深处是不劣的。更进一步的结论就是,每个点的子树内都是黑点,贡献是 $\text{size}-1$。那么 $k$ 的答案就是前 $k$ 小的 $\text{size}-1$ 之和。[代码](https://qoj.ac/submission/3004110)。 ## 【2】[CF1946F Nobody is needed](https://www.luogu.com.cn/problem/CF1946F) 考虑下面的刻画:对每个 $i<j \land a_i \mid a_j$ 连边 $i \to j$。询问只保留端点 $\in [l,r]$ 的边,做 DAG 路径计数。 注意整张 DAG 的形态是 $1 \sim n$ 向其倍数连边,故边数是 $O(n \log n)$ 级别的。 我们将询问离线后,对 $l$ 降序扫描线,维护每个 $r$ 作为终点的路径数 $f_r$。记 $g(u,v)$ 为 $u \to v$ 的路径数目,扫到 $l$ 时令 $f_r \gets f_r+g(l,r)$,则询问是区间求和。 不难得到 $g$ 的转移式 $$ g(i,j) = \sum_{(i,k) \in E} g(k,j) $$ 注意 $g(i,j) \ne 0$ 的必要条件是 $a_i \mid a_j$,故只要用 vector 存 $g$ 非零的位置,转移时需要借助临时数组。 我们直接枚举 $i \to k \to j$ 的两条有向边进行转移,时间代价可以分析到 $$ \sum_{i=1}^n \sum_{j=1}^{\lfloor n/i \rfloor} \left\lfloor \dfrac{n}{ij}\right\rfloor=O(n \log^2 n) $$ 也可以写份代码来验证,$n=10^6$ 时上式 $=106030594 \approx 10^8$,可以接受。 使用树状数组维护 $f$,对 $g$ 暴力转移,复杂度 $O(n \log^2 n+q \log n)$。[代码](https://www.luogu.com.cn/article/fjtt5qaj)。 ## 【2】[QOJ20297 Legendary Game](https://qoj.ac/problem/20297) 我们称 $[1,n]$ 为一类数,$(n,n+k]$ 为二类数,$(n+k,2n+k]$ 为三类数。设三种数在最终序列中出现 $c_1,c_2,c_3$ 次,则我们只关心每个位置的数字类型是否合法,最终令每类数自由排列,系数 $\dbinom{k}{c_2}\dbinom{n}{c_1} \dbinom{n}{c_3}c_1!c_2!c_3!$。 注意到 $k$ 的范围很小,考虑枚举 $x=c_2$。这 $x$ 个二类数将序列切分为 $x+1$ 段,每段内部必然是一 & 三交替的。枚举 $c_1$ 或 $c_3$ 的复杂度过大,我们转而关注每段长度的奇偶性。 枚举 $x+1$ 段中存在 $y$ 个奇数段,再钦定 $y$ 个奇数段中恰有 $z$ 个满足:一类数比三类数多一个。选法数 $\dbinom{x+1}{y} \dbinom{y}{z}$。可以求得 $c_1-c_3=z-(y-z)$,联立 $c_1+c_2+c_3=n$ 可解出 $c_1,c_3$ 得到系数。 对于偶数段,存在 `1313...` 和 `3131...` 两种排列方式,枚举 $x+1-y$ 个偶数段中有 $w$ 个非空,选法数 $\dbinom{x+1-y}{w}$,贡献系数 $2^w$。 还有一个系数是,将 $n-x$ 个元素划分为 $x+1$ 段,恰有 $y$ 个奇数段和 $w$ 个非空偶段的方案数。设奇数段长 $2a_i+1$,偶数段长 $2b_i$,可列得不定方程 $$ \sum_{i=1}^y (2a_i+1)+\sum_{i=1}^w 2b_i=n-x $$ 未知量的范围是 $a_i \ge 0$ 且 $b_i \ge 1$。令 $b_i'=b_i-1$,代入化简得 $$ \sum_{i=0}^y a_i+\sum_{i=1}^w b_i'=\dfrac{n-x-y-2w}{2} $$ 这是 $y+w$ 个变量的不定方程解计数问题,答案为 $\dbinom{\frac{n-x-y-2w}{2}+y+w-1}{y+w-1}$。注意特判 $y=0 \land w=0$ 的情形,所有段都是空段,方案数为 $1$。 综上,给出本题的答案式子 $$ \dbinom{k}{c_2}\dbinom{n}{c_1} \dbinom{n}{c_3}c_1!c_2!c_3!\dbinom{x+1}{y} \dbinom{y}{z}\dbinom{x+1-y}{w}\dbinom{\frac{n-x-y-2w}{2}+y+w-1}{y+w-1} $$ 复杂度 $O(k^4)$。[代码](https://qoj.ac/submission/3017580)。 :::::error[为啥没做出来] 做的时候没发现偶数段还有贡献,不知道要枚举 $w$,其他部分都推出来了。 ::::: ## 【1】[ARC197E Four Square Tiles](https://www.luogu.com.cn/problem/AT_arc197_e) 注意到 $H,W \le 3n-1$,故四个方形的排布必然如下图所示: ![](https://cdn.luogu.com.cn/upload/image_hosting/jtn2oigo.webp?x-oss-process=image/resize,m_lfit,w_300) 变量 $x_i,y_i$ 满足 $x_i \in [n, H-n+1] \land y_i \in [n,H-w+1]$。 不妨令 $x_i \gets x_i-n+1, y_i \gets y_i-n+1$,则新的范围为 $x_i \le H-2n+2$ 且 $y_i \le W-2n+2$,设这两个值为 $h,w$。由题目得到如下约束: - $x_i \in [1,h] \land y_i \in [1,w]$。 - $x$ 轴不相交:$x_1 < x_2 \land x_4 < x_3$。 - $y$ 轴不相交:$y_1<y_4 \land y_2<y_3$。 - 方形 $1,3$ 不交:$x_3 \le x_1 \land y_3 \le y_1$ 不成立。 - 方形 $2,4$ 不交:$x_2 \le x_4 \land y_2 \ge y_4$ 不成立。 容易发现 $x,y$ 两维独立,对一维情形进行讨论即可。我们做一个二元容斥: - 总方案数:由 $1 \le x_1 < x_2 \le h$ 得方案数 $\dbinom{h}{2}^2$。 - 突破一个限制:满足 $x_1< x_2 \land x_4<x_3 \land x_3 \le x_1$。枚举 $x_1=i$,则 $1 \le x_4 < x_3 \le i \land x_2>i$,方案数 $$ \sum_{i=1}^h \binom{h}{2}(n-i)=\binom{h+1}{4} $$ - 突破两个限制:满足 $x_1<x_2 \land x_4 < x_3 \land x_3 \le x_1 \land x_2 \le x_4$。画数轴可以发现这个条件是矛盾的,方案数 $0$。 由乘法原理合并独立的两维,答案式子 $$ \binom{h}{2}^2 \binom{w}{2}^2 -2 \binom{h+1}{4} \binom{w+1}{4} $$ 复杂度 $O(1)$。 ## 【1】[ARC174E Existence Counting](https://www.luogu.com.cn/problem/AT_arc174_e) 设 $f_k$ 为数字 $k$ 的答案。我们枚举 $i=1 \to n$,钦定 $\forall j<i, a_j=b_j$ 且 $a_i<b_i$。人话就是钦定 LCP,考虑这种序列对每个 $f_k$ 的贡献。 设 $b_1 \sim b_{i-1}$ 组成集合 $S$,可填入 $a_i$ 的数有 $c$ 个,则 $c$ 是 $x \notin S \land x<b_i$ 的 $x$ 的数目。用权值树状数组维护即可。 对 $k$ 分类讨论: - 若 $k \in S$,$a_i$ 的填法为 $c$,而 $a_{i+1} \sim a_n$ 随意填,$f_k \gets c \times A_{m-i}^{n-i}$。 - 若 $k \notin S$: - 将 $k$ 扔到后 $n-i$ 个位置,$a_i$ 的填法为 $c$,有 $f_k \gets c \times A_{m-i-1}^{n-i-1} \times (n-i)$,其中 $n-i$ 是选出 $k$ 所在位置的方案数。 - 若 $k<a_i$,可以将 $k$ 填到 $a_i$,于是 $f_k \gets A_{m-i-1}^{n-i}$。 用两个差分树状数组维护 $k \in S$ 和 $k \notin S$ 的 $f_k$,支持区间加单点查询。扫描到 $b_i$ 时其从 $\notin S$ 的数组移动到 $\in S$ 的数组里。 注意特判 $a=b$ 的情况,令 $k \in S$ 的 $f_k \gets 1$。 复杂度 $O(n \log m)$。[代码](https://atcoder.jp/contests/arc174/submissions/79453271)。 ## 【1+】[CF1942G Bessie and Cards](https://www.luogu.com.cn/problem/CF1942G) 抽到 $1$ 卡以后立刻丢掉抽下一张,那么 $1$ 卡的作用可以忽略。$0$ 卡和特殊卡都视作 $-1$,$2$ 卡视作 $+1$,则前缀和到达 $-5$ 的时刻停止抽卡,获胜条件取决于这时候是否集齐特殊卡。 可以用格路计数转化条件,抽到 $-1$ 令 $y \gets y+1$,抽到 $+1$ 令 $x \gets x+1$,则牌堆可以刻画为 $(5,0)$ 出发的格路,触碰 $y=x$ 则停止游走。 枚举触碰点为坐标 $k \ge 5$,只要计数 $(5,0) \to (k,k-1)$ 的不越过 $y=x$ 的格路。将终点关于 $y=x+1$ 对称,由单线反射容斥得 $$ \binom{2k-6}{k-1}-\binom{2k-6}{k} $$ 限制为前 $2k$ 张牌必须集齐 $5$ 张特殊卡,方案数 $\binom{2k}{5}$。剩余 $a-(k-5)$ 个 $-1$ 卡和 $c-(k-5)$ 个 $+1$ 卡随意排列,方案数 $\binom{a+c-2k+10}{a-k+5}$。 故合法方案数为 $$ \sum_{k=5}^n \binom{k}{5}\binom{a+c-2k+10}{c-k}\left(\binom{2k-6}{k-1}-\binom{2k-6}{k}\right) $$ 注意加上始终不碰到 $y=x$ 的方案数,计算方法和上面类似,这里不赘述。 除以总数 $\binom{a+c+5}{a,c,5}$ 得到答案。复杂度 $O(n)$。[代码](https://codeforces.com/problemset/submission/1942/392128555)。 :::::error[为啥没做出来] 思路是对的,式子推不明白,各种地方错,然后还没发现碰不到 $y=x$ 的贡献,大了。 ::::: ## 【3】[ABC236Ex Distinct Multiples](https://www.luogu.com.cn/problem/AT_abc236_h) 对互不相同的条件容斥。枚举划分 $P$,每个等价类内部 $a$ 值相同,容斥系数 $\sum\limits_{S \in P} (-1)^{|S|-1} (|S|-1)!$。 :::::info[集合划分容斥] 考虑下面的模型:有 $n$ 个变量 $a_1 \sim a_n$,其中 $a_i \in S_i$ 且 $a_i$ 互不相同,对 $a_1 \sim a_n$ 计数。 对互不相同进行容斥。考虑建图,若 $a_i=a_j$ 则连边 $i \leftrightarrow j$,连通块内部的点值都相同,不同连通块之间无限制。 对无向图 $G=(V,E)$,设 $C(E)$ 为 $G$ 的集合划分,$F(P)$ 为划分 $P$ 对应的方案数,答案即为 $$ \sum_{E} (-1)^{|E|} F(C(E))=\sum_{P} F(P) \sum_{C(E)=P}(-1)^{|E|} $$ 设 $P=\{S_1,S_2,\cdots,S_m\}$,只要在每个 $S_i$ 内部连边并构成连通图。则容斥系数 $$ \sum_{C(E)=P}(-1)^{|E|}=\prod_{S \in P} \sum_{G_S \text{连通}} (-1)^{|E(G_S)|} $$ 问题转化为,对 $k$ 个点的无向图,求所有连通边集 $E$ 的 $(-1)^{|E|}$ 之和,记作 $g_k$。 设 $f_k$ 为 $k$ 个点任意无向图的 $(-1)^{|E|}$ 之和,则 $$ f_k=\sum_{i=0}^{\binom{k}{2}} \binom{\binom{k}{2}}{i} (-1)^i=0^{\binom{k}{2}} $$ 故 $k \ge 2$ 时 $f_k=0$,只有 $f_0=f_1=1$。$f$ 的 EGF 为 $$ F=\sum_{k \ge 0} f_k \dfrac{x^k}{k!}=1+x $$ 根据多项式 $\exp$ 的组合意义: $$ F=\exp G \implies G=\ln F $$ 由 Taylor 展开 $$ G=\sum_{k \ge 1} (-1)^{k-1} \dfrac{x^k}{k} $$ 提取系数得 $$ \left[\dfrac{x^k}{k!}\right]G=\dfrac{(-1)^{k-1}}{k} \implies g_k=(-1)^{k-1}(k-1)! $$ 将 $g_k$ 代入容斥系数,得到最终结论 $$ \sum_{P} F(P) \prod_{S \in P} (-1)^{|S|-1} (|S|-1)! $$ ::::: 记 $\underset{i\in S}{\text{lcm } } d_i=\text{lcm}(S)$。强制点集 $S$ 内 $a$ 值均为 $x$,则必有 $\text{lcm}(S) \mid x$,从而方案数为 $$ F(P)=\prod_{S \in P}\left\lfloor \dfrac{m}{\text{lcm}(S)} \right\rfloor $$ 答案为 $$ \sum_{P}\prod_{S \in P}(-1)^{|S|-1} (|S|-1)! \left\lfloor \dfrac{m}{\text{lcm}(S)} \right\rfloor $$ 利用排除 $\min S$ 转移的 trick,容易 $O(2^n \log V)$ 地求出单个 $S$ 的贡献值 $f_S=(-1)^{|S|-1} (|S|-1)! \left\lfloor \dfrac{m}{\text{lcm}(S)} \right\rfloor$。 构造集合幂级数 $F$,令 $G=\exp F$,则 $[x^U] G$ 即为所求。使用子集卷积 exp 做到 $O(n^2 2^n)$。 总复杂度 $O(n^2 2^n+2^n \log V)$。[代码](https://atcoder.jp/contests/abc236/submissions/79499553)。 ## 【0】[P16342 [科大国创杯初中组 2026] 倍数调整](https://www.luogu.com.cn/problem/P16342) 答案不会超过 $b$,枚举 $b$ 的最终取值以后 $O(1)$ 算即可。 ## 【2】[AGC005D ~K Perm Counting](https://www.luogu.com.cn/problem/AT_agc005_d) 将 $(i,a_i)$ 拍到二维平面上,约束即 $y=x- k$ 和 $y=x+k$ 两条直线上不能有点。 考虑容斥,钦定 $m$ 个位置突破限制,剩余 $n-m$ 个位置随意排列,容斥系数 $(-1)^m (n-m)!$。 约束转化为,选择 $m$ 个点位于 $y=x\pm k$ 上,要求横纵坐标两两不同。我们将横纵坐标相同的点连边,则 $m$ 个点构成图的独立集。可以发现图的形态是若干条链: ![](https://cdn.luogu.com.cn/upload/image_hosting/npwddpef.webp) 我们从长为 $n$ 的链上取大小为 $k$ 的独立集,转化为在 $k$ 个选点间插入 $k-1$ 个未选点,剩余点随意,方案数 $\dbinom{n-k+1}{k}$。 设每条链的长度为 $b_i$,则单链的 OGF 为 $$ F_i=\sum_{k \ge 0} \binom{b_i-k+1}{k} x^k $$ 将 $O(n)$ 个 $F$ 暴力卷积后,取 $x^m$ 项系数即为容斥 $m$ 的答案。 复杂度 $O(n^2)$。[代码](https://atcoder.jp/contests/agc005/submissions/79590009)。 ## 【0】[AGC009C Division into Two](https://www.luogu.com.cn/problem/AT_agc009_c) ![](https://cdn.luogu.com.cn/upload/image_hosting/nxc6y12h.webp) ## 【0】[ZR3650 圆周率](https://www.zhengruioi.com/problem/3650) 答案为 P 和 I 数目的差。赛时写的括号匹配类似物。 ## 【1+】[ZR3649 小跳蛙](https://www.zhengruioi.com/problem/3649) 有个直觉是,我们希望 `2 2 _` 这种结构尽量多,让中间的 `2` 被跳过去。 我们研究一下这个配对结构:定义 $s_i$ 为从第 $i$ 个 `2` 开始,令 $(i,i+1), (i+2,i+3),\cdots$ 两两配对的成本。预处理所有 `2` 的位置后推后缀和即可。 这里对 `2` 的数目分讨: - 如果有奇数个 `2`:形如 `... 2 2 ... 2 2 ... 2`,要求第 $2i-1$ 个和第 $2i$ 个相邻,最后一个 `2` 扔到末尾。 那么前面两两配对的答案可以直接算,最后一个 `2` 扔到末尾也可以算出来。 - 如果有偶数个 `2`,最优决策有两种: - 形如 `... 2 2 ... 2 2 ... 2 2 ...` 两两配对,可以直接算。 - 形如 `... 2 2 ... 2 2 ... 2 1 ... 2` 让单个 `2` 落单,把另一个 `2` 推到末尾。列出这种情况的式子,发现是 RMQ 形式,好维护的。 这两种决策的步数是相等的,原因是 `1` 还是 `2` 在末尾没区别。 [代码](https://www.zhengruioi.com/submission/1113840)。 :::::error[为啥不会做] 我说这个题比 median 难有感觉吗,学生 2h 得 0 分。 应该反思一下,赛时打了半天表然后没瞪出来东西,实际上对着表还是挺好发现奇数 `2` 配对末位 `2`,偶数 `2` 配对或者 `2` 落单末尾 `2` 的结构。多训一点注意力是对的。 做不明白这种分析性质的神秘贪心分讨题,加训。 ::::: ## 【2】[CodeChef GCDS](https://www.codechef.com/problems/GCDS) 从必要条件入手。修改 $a_i$ 只影响跨过 $i$ 的区间,为向两侧传递贡献,$x$ 必须由 $a_{i-1}$ 和 $a_{i+1}$ 的质因子组合而成。 利用线性筛预处理每个数的最小质因子,做到 $O(\log V)$ 分解质因数后,求出 $a_{i-1} \times a_{i+1}$ 的质因子集合 $S$。注意到 $x \le V$,考虑直接爆搜 $x$ 的取值。 这里需要一些剪枝手法。注意到最优的 $x$ 必然是 $S$ 的极大子集,我们将 $S$ 降序排序,每轮搜索时判断当前的 $x$ 与后缀积的组合是否合法,若合法则更新答案后退出,跑的飞快。 问题转化为,单点修改,全局查询区间 GCD $>1$ 的子段数。注意到修改 $i$ 只影响跨越 $i$ 的子段,根据经典结论,前缀 $\gcd$ 的变化次数是 $\log V$ 的,故枚举这些段算贡献即可。 具体地,我们用 ST 表二分预处理出所有 $[l,r]$ 段,满足左端点 $j \in [l,r]$ 的 $[j,i)$ 的区间 GCD 不变,询问时遍历 $i$ 左侧的段和 $i$ 右侧的段计算答案即可,复杂度是 $O(\log^2 V)$ 的。 理论复杂度 $O\left(V+n \log n\log^2 V+n 4^{\omega(V)} \log^3 V\right)$,本题中 $\omega(V) \le 7$。实际上跑的飞快可以通过。[代码](https://www.codechef.com/viewsolution/1364077289)。 :::::error[为啥不会做] 赛时第一步都想不到,猜了一堆其他的结论都爆了。补题比较快就写出来,然后剪了一会枝就冲过去了。 ::::: ## 【1】[ZR3652 特征值](https://www.zhengruioi.com/problem/3652) 设 $S=\sum \limits_{i=1}^n a_i$,则 $f(a)=\min(S \bmod m, m - S \bmod m)$。代入 $F$ 的定义后,两个 $\min$ 可以拆掉,变为 $$ \begin{aligned} F(a)&=\min\left(\min_{[l,r] \subseteq [1,n]} \left(\sum_{i=l}^r a_i\right) \bmod m, \min_{[l,r] \subseteq [1,n]} \left( \left(\sum_{i=l}^r a_i\right)-\left(\sum_{i=l}^r a_i\right) \bmod m\right)\right)\\ &=\min\left(\min_{[l,r] \subseteq [1,n]} (p_r-p_{l-1}) \bmod m, \min_{[l,r] \subseteq [1,n]} \left(p_r-p_{l-1}-(p_r-p_{l-1}) \bmod m\right)\right) \end{aligned} $$ 其中 $p_n=\left(\sum \limits_{i=1}^n a_i\right) \bmod m$。注意到 $p_1 \sim p_n$ 和 $a_1 \sim a_n$ 是双射,转而对 $p$ 计数。 考虑枚举 $x=F(a)$ 并计数 $p_1 \sim p_n$ 的数目,乘上 $x^k$ 作为答案。不妨将恰好容斥为选择至少,记 $c(x,n)$ 为 $F(a) \ge x$ 的 $a_1 \sim a_n$ 的数目,则 $n$ 的答案为 $$ \text{ans}_n=\sum_{x=0}^n x^k (c(x,n)-c(x+1,n)) $$ 下面考虑 $c$ 的求法。由 $F(a) \ge x$ 可列得约束: $$ \forall 0\le i<j\le n,\left\{\begin{matrix} (p_j-p_i) \bmod m &\ge x\\ p_j-p_i-(p_j-p_i) \bmod m &\ge x \end{matrix}\right. $$ 令 $i=0$ 可得 $p_j \in [x,m-x]$,条件转化为 $\forall i<j, |p_i-p_j| \ge x$。 取升序序列 $s_1 \sim s_n$,满足下列两个条件: - $\forall i\in [1,n),s_{i+1}-s_i \ge x$。 - $\forall i\in [1,n], s_i \in [x,m-x]$。 可以证明 $p_1 \sim p_n$ 的升序排列和 $s_1 \sim s_n$ 是双射。对 $s$ 计数后乘系数 $n!$ 即可。 令 $t_i=s_i-x \times i$,则 $t_i \in [0,m-x(n+1)]$ 且 $t_i \ge t_{i+1}$。令 $u=m-x(n+1)$,由不降序列计数,答案为 $$ c(x,n)=\binom{u+n}{n}n! $$ 合法条件为 $u \ge 0$,解得 $x \le \frac{m}{n+1}$。外层循环枚举 $n$,内层枚举 $x$ 到 $\frac{m}{n+1}$ 是调和型枚举。 注意预处理 $x^k$ 的值,总复杂度 $O(m \log k+m \log m)$。[代码](https://www.zhengruioi.com/submission/1113700)。 ## 【2+】[P17273 [eJOI 2026] Automata](https://www.luogu.com.cn/problem/P17273) 到底是谁在会这种抽象观察性质分讨题? 给排列拍到二维折线图。对于一个单调段,一次操作是让一个点上山 / 下山。对于波峰 / 波谷,点的通行是单向的,这是因为极值点两侧值不同,极值可以跨越但是路径不可逆。 ![](https://cdn.luogu.com.cn/upload/image_hosting/d70skse3.webp) 找出所有单向通行的位置,那么问题大体上抽象成,有 $n$ 个点的一条链,有些边被定向,然后询问联动下是否能走到同一点。 不妨考虑 $k=2$。这种题一般是必要条件拼拼乐,观察一些情况: - $S=T$ 或者 $\to S \leftrightarrow T$ 或者 $S \leftrightarrow T \gets$ 赢了。 - $S \to \cdots \to T$ 或者 $S \gets \cdots \gets T$ 赢了。 - $S \gets \cdots \to T$ 输了,先判掉这种。 - $\to S \to \cdots \gets T$ 赢了,移动 $T$ 的时候 $S$ 会被卡住。 - $S$ 往右和 $T$ 往左迈的第一步是一样的,将两个点卡在某条边处就赢了。 - $l \gets S \to m \gets T \to r$。我们让 $S$ 跑到 $m$ 并且 $T$ 跑不过 $S$ 就赢了,也就是 $S \to m$ 的距离短于 $T \to r$ 的距离。同理判掉 $T \to m$ 和 $S \to l$ 的比较。 考虑 $k$ 一般的情况,我们总能找到一个分界点,使得左侧的行为和 $S$ 一致,右侧的行为和 $T$ 一致,所以直接给最左最右点拉出来判就是充要的,转化为 $k=2$。 实现可以扫出来每个点两侧最近的有向边,然后把上面条件填进代码里。复杂度 $O(n)-O(1)$。 ## 【1+】[AT_jsc2019_qual_f Candy Retribution](https://www.luogu.com.cn/problem/AT_jsc2019_qual_f) 不妨令 $a_i \gets a_i+1$ 转而计数正整数序列。令 $m \gets n-m$ 转为升序排序后 $a_m=a_{m+1}$。 先将 $[l,r]$ 差分成 $[1,r] \setminus [1,l)$,变成总和有一个上限 $r$。 做一个单步容斥,用总数减去 $a_m<a_{m+1}$ 的序列数。枚举总和 $k $ 得到总数 $\sum \limits_{k=1}^r \dbinom{k+n-1}{n-1}=\dbinom{r+n}{n}$。 枚举排序后 $a_m=x$,排列被分成两段,$1 \sim m$ 段的值域为 $[1,x]$,而 $m+1 \sim n$ 段的值域为 $(x,n]$。 再来一次单步容斥:钦定 $1 \sim m$ 段的值域为 $[1,x]$,然后减掉钦定为 $[1,x-1]$ 的方案数,则 $a_m=x$ 的限制可以丢掉。 问题转化为,计数恰有 $m$ 个数 $\le a$,$n-m$ 个数 $\ge b$,总和不超过 $r$ 的序列。这个可以容斥也可以 GF 启动,下面是熔池观点。 **钦定至少** $i$ 个位置 $>a$,由二项式反演,容斥系数 $(-1)^i \dbinom{m}{i}$。 令钦定的 $i$ 个位置减去 $a$,选定的 $\ge b$ 的位置减去 $b$,总和为 $r'=r-m-i \times a-(n-m)b$。剩余选法为 $\dbinom{r'+n}{n}$。 答案即为 $$ f(a,b)=\binom{n}{m}\sum_{i=0}^{m} (-1)^i \binom{m}{i} \binom{r'+n}{n} $$ 其中 $r' \ge 0 \implies i \le \dfrac{*}{a}$,$*$ 是 $O(n)$ 级别的常数。 在外层循环枚举 $x$ 得到 $a,b$,内层循环枚举 $i$,根据 $i$ 的合法条件可知,这属于调和型枚举,复杂度是 $O(n \log n)$ 可以通过。[代码](https://www.luogu.com.cn/article/uwatuto9)。 :::::error[为啥没做出来] 这种组合计数基础练习题不会做,可以似一似了。 对着 $a_m=a_{m+1}$ 没有做单步容斥,直接枚举的两边的总和硬算,然后推了半天不会处理 $=x$ 的部分。 后面研发出来这个做法,然后用 OGF 算 $f$ 写错式子,喜提调不出来。问了 dpsk 才知道哪里挂的。 ::::: ## 【2】[P16416 【MX-X28-T5】「FAOI-R12」单人旅行](https://www.luogu.com.cn/problem/P16416) 设 $M_i=\{t_1,t_2,\cdots,t_{i-1}\}$,必有 $M_i=[1,i] \setminus \{x_i\}$,其中 $x_i$ 是当前 $\text{mex}$。对 $c_i$ 和 $x_i$ 的相等关系分讨: - 若 $c_i\ne x_i$,则 $t_i=x_i$ 且 $x_{i+1}=i+1$。 - 若 $c_i=x_i$,则 $t_i=i+1$ 且 $x_{i+1}=x_i$。 令全集 $U=\{1,2,\cdots,n\}$,枚举 $S \subseteq U$ 满足: - 对 $i \in S$,要求 $c_i \ne x_i$。 - 对 $i \in U \setminus S$,要求 $c_i = x_i$。 将 $[c_i \ne x_i]$ 容斥为 $1-[c_i =x_i]$。钦定 $T \subseteq S$ 使得: - 对 $i\in T$,要求 $c_i = x_i$。 - 对 $i\in S \setminus T$ 无限制。 容斥系数 $(-1)^{|T|}$。可以发现 $(T,S \setminus T, U \setminus S)$ 构成对全集 $U$ 的划分,带着容斥系数进行 DP: - 设 $f_{i,j}$ 为满足下列条件时,带容斥系数 $(-1)^{|T|}$ 的合法权值和: - 仅考虑 $1 \sim i$。 - 第 $i$ 个位置实际上满足 $c_i \ne x_i$,则 $x_{i+1}=i+1$。 - 序列 $c$ 中消耗了 $j$ 个带限制元素,即约束 $c_i=x_i$ 的 $c_i$。 - 仅考虑 $T$ 和 $U \setminus S$ 位置上填入的数。 - 转移时,枚举连续 $k$ 个位置划入 $U \setminus S$,接下来第 $i+k+1$ 个位置划入 $T$ 或 $S \setminus T$。 - 对于位置 $i+1 \sim i+k$: - $x$ 恒为 $i+1$,产生的 $t$ 分别为 $i+2 \sim i+k+1$。权值积 $\prod \limits_{u=1}^k \left(a_{i+u} (i+u+1)+b_{i+u}\right)$。 - 选定 $k$ 个 $=i+1$ 的数随意排列,方案数 $\dbinom{\text{cnt}_{i+1}}{k}k!$。 转移系数 $q=k!\dbinom{\text{cnt}_{i+1}}{k}\prod \limits_{u=1}^k \left(a_{i+u} (i+u+1)+b_{i+u}\right)$。 特别地,若 $i+k=n$,直接将 $q \times f_{i,j}$ 累加到 $\text{ans}_{j+k}$ 中并跳出循环,表示最后一个位置落在 $U \setminus S$ 中。 - 对于位置 $i+k+1$,产生的 $t$ 为 $i+1$,贡献系数 $w=a_{i+k+1}(i+1) + b_{i+k+1}$。 - 划入 $T$,转移 $qw(\text{cnt}_{i+1}-k)(-1)f_{i,j} \to f_{i+k+1,j+k+1} $。其中 $\text{cnt}_{i+1}-k$ 是选法数,$-1$ 是容斥系数。 - 划入 $S \setminus T$,转移 $qw\times f_{i,j} \to f_{i+k+1, j+k}$。 - DP 初值为 $f_{0,0}=1$。 - 答案为 $\sum \limits_{j=0}^n (n-j)!(\text{ans}_j+f_{n,j})$。系数 $(n-j)!$ 是 $|S \setminus T|$ 个元素任意排列的方案数。 注意 $\sum \text{cnt}_i=n$,从而总复杂度 $O(n^2)$。[代码](https://www.luogu.com.cn/article/3yi78w7h)。 :::::error[为啥没做出来] 一直在延迟钦定,搞出来一车四五次方的 poly 做法。 后面去做容斥,但是我是做 $[c_i >x]=1-[c_i \le x]$,然后转移式子整个列完,写完过不去。询问 gemini 发现做法假了,花费 2.5h 得零分。 发怒了,上面这个做法是在 gemini 老师协助下,对着我原本的式子改出来的,其实就是容斥的东西变了一下,转移差不多。 ::::: ## 【1】[ARC183C Not Argmax](https://www.luogu.com.cn/problem/AT_arc183_c) 注意到我们只关心相对大小,考虑最值分治式 DP: - 设 $f_{l,r}$ 为 $[l,r]$ 区间的合法方案数。注意我们仅关心相对大小。 - 转移枚举 $k$ 并钦定 $k$ 为 $[l,r]$ 的区间 $\max$ 位置。先判定 $k$ 是否合法: - 若 $x_i=k$ 且 $[l_i,r_i] \subseteq [l,r]$ 必不合法。容易验证其余情况都合法。 转移将 $[l,k)$ 和 $(k,r]$ 进行合并。只要重新钦定大小顺序,保证同组排名不变,选法数 $\binom{r-l}{k-l}$。转移方程 $$ f_{l,r}=\sum_{k \in [l,r]} \binom{r-l}{k-1}f_{l,k-1} \times f_{k+1,r} $$ - DP 初值为 $f_{i,i-1}=f_{i,i}=1$。注意特判 $l_i=r_i$ 的情形,不存在合法排列。 - 答案为 $f_{1,n}$。 预处理 $S_k=\{[l_i,r_i] \mid x_i=k\}$,只要判定 $\exists [l',r'] \in S_k, [l',r'] \subseteq [l,r]$。对每个 $S_k$ 递推出 $a_x=\min \limits_{l_i \ge x} r_i$,查询 $(l,r)$ 判断 $a_l \le r$ 是否成立即可。 复杂度 $O(m+n^3)$。[代码](https://atcoder.jp/contests/arc183/submissions/79639704)。