9.1 ~ 9.30 做题记录
stripe_python
·
2026-09-12 15:08:14
·
个人记录
【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' 的形式:
若 b=0 ,则 2y+v=2\left(y+\lfloor \frac{v}{2} \rfloor\right)+(v \bmod 2) 。
若 b=1 ,则 2y+v+1=2\left(y+\lfloor \frac{v+1}{2} \rfloor\right)+((v+1) \bmod 2) 。
考虑维护懒标记 v ,下传标记时对 v 的奇偶性进行讨论:
若 v \bmod 2 =0 ,则 0 \to 0, 1\to 1 ,左右儿子位置不变,下传标记 \frac{v}{2} 。
若 v \bmod 2 =1 ,则 0 \to 1, 1 \to 0 ,交换左右儿子,新左儿子下传标记 \frac{v+1}{2} ,新右儿子下传标记 \frac{v-1}{2} 。
这样我们得到了全局 +v 的做法。
考虑子树 +v 的做法。我们将子树劈下来,对根链 pushup,并对劈下来的子树接上一条根链,打上全局 +v 的标记后做线段树合并。注意及时 pushdown。
复杂度均摊 O(q \log V) 。代码。
【2+】P5298 [PKUWC2018] Minimax
考虑求出所有的 D_i 。对 w_u 离散化后,设 f_{u,i} 为 u 点取第 i 小权值的概率,对 u 进行讨论:
若 u 为叶子,f_{u,\text{id}(w_u)}=1 。
若 u 只有左儿子,令 f_u \gets f_v 。
若 u 有左右儿子 l,r ,讨论 u 取 \min / \max ,这个值在左 / 右儿子处取得,四种情况的加和为
f_{u,i}=p_u\left(f_{l,i}\times \sum_{j \in [1,i]} f_{r,j} + f_{r,i}\times \sum_{j \in [1,i]} f_{l,j} \right)+(1-p_u) \left(f_{l,i}\times \sum_{j \in [i,m]} f_{r,j} + f_{r,i}\times \sum_{j \in [i,m]} f_{l,j} \right)
直接做前缀和优化得到 O(n^2) 做法,获得 40pts。
这种与前后缀和有关的 DP 转移,可以尝试用线段树合并进行优化。设合并 T_1,T_2 时递归区间为 [l,r] ,维护 [1,l) 的前缀和 p_1,p_2 ,则有:
若 T_1=\varnothing ,说明 [l,r] 内 f_{l,i} 全为 0 。对 T_2 全局乘 p_u \times p_1 + (1-p_u)(1-p_1) 即可。
若 T_2=\varnothing ,同理对 T_1 全局乘 p_u \times p_2+(1-p_u)(1-p_2) 。
若 T_1 \ne \varnothing \land T_2 \ne \varnothing ,对左右子树分别递归,维护区间和计算出新的 p_1,p_2 作为递归参数。
复杂度 O(n \log n) 。代码。
【2】QOJ6322 Forestry
任意定根后,设 f_{u,i} 为断开 u 到父亲的边,仅考虑 u 子树内部,u 所在连通块最小值为 i 的方案数。预处理对 i 维度离散化。
树形 DP 转移是逐子树加,在 u 处加入儿子 v 时:
若断开 u \to v 的边,f_{u,i} \gets f_{u,i} \times 2^{\text{sz}_v-1} 。
若不断开 u \to v 的边,枚举 v 所在连通块最小值为 j ,则 f_{u, \min(i,j)} \gets f_{u,i} \times f_{v, j} 。
我们在 u 处不关心子树外的情况,外部边可以任意断开,则 f_{u,i} 对答案的贡献系数为 i \times 2^{\max(0,n-\text{sz}_u-1)} 。
考虑线段树合并优化 DP。转移是 (\min,\times) 卷积,我们对 i,j 的大小关系进行讨论:
若 i \le j ,则 f_{u,i} \times \left(2^{\text{sz}_v-1}+\sum \limits_{j=i}^m f_{v,j}\right) \to f_{u,i} 。这里将两种转移合并了。
若 i>j ,则 f_{v,j} \times \sum\limits_{i=j+1}^m f_{u,i} \to f_{u,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 块。修改时:
若 B^k > x ,则块内元素整体 -x 。
若 B^{k+1} \le x ,则块内元素无变化。
若 x \in [B^k,B^{k+1}) ,则需要处理部分块内元素。
对于每块开一棵线段树,下标为原序列的下标,线段树上维护区间和,区间 \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} ,我们将最小值和非最小值分开维护:
最小值:V_1=\begin{bmatrix} \text{mn} \times \text{cnt} \\ \sum\limits_{a_i =\text{mn}} h_i \\ \text{cnt} \end{bmatrix} 。
非最小值:V_2=\begin{bmatrix} \sum \limits_{a_i > \text{mn}} a_i \\ \sum\limits_{a_i >\text{mn}} h_i \\ \text{len}-\text{cnt}\end{bmatrix} 。
区间 +\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 下传进行讨论:
若 v 的最小值等于 u 打标记前的最小值,则 M_1(v) 复合 M_1(u) ,M_2(v) 复合 M_2(u) 。
若 v 的最小值大于 u 打标记前的最小值,则 M_1(v),M_2(v) 均复合 M_2(u) 。
这样我们得到了 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 :
若 a_k \ge a_j ,则 |a_i-a_k| \ge |a_i-a_j| ,点对 (i,j) 支配 (i,k) 。
若 a_k<a_i ,列出 (i,k) 不被 (j,k) 支配的条件为 |a_i-a_k| < |a_j-a_k| ,去掉绝对值得到 a_k-a_i < a_j-a_k ,移项得 a_k-a_i<\dfrac{a_j-a_i}{2} 。
根据推导,每向右寻找一次支配对 (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} 个。
若 |T_x|>B ,我们维护 S'_i \subseteq S_i 且 S_i' 只包含这样的 x 。用 bitset 优化求交,修改 O(1) 查询 O\left(\dfrac{n}{Bw}\right) 。
若 |T_x| \le B ,我们在修改 S_i 时直接枚举 j \in T_x 并将 |S_i \cap S_j| 增加 1 。可以用哈希表动态开点地维护 (i,j) 对的答案,修改 O(B) 查询 O(1) 。
可以将询问离线后划分两类 x 。取 B=\sqrt{\dfrac{n}{w}} 得最优复杂度 O\left(\dfrac{n^{1.5}}{\sqrt{w}}\right) 。
对时空常数的若干优化:
预处理出 |T_x| >B 的 x 后,将所有 x 重标号,这样 S_i' 的 bitset 只要开到 n/B 大小。
对 S_i' 动态开点,当用到 S_i' 时再新开 bitset。
注意到至多 n 个询问,将询问的 (i,j) 离线后离散化,可以将哈希表换成普通数组维护。
对于未在询问中出现的 i ,直接忽略 S_i \gets S_i \cup \{x\} 的修改。
添加这些优化后足以通过。代码。
【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 序:
若 r=x ,则 x 子树 DFS 序为 [1,n] 。
若 r \notin \text{subtree}(x) ,则 x 子树 DFS 序仍为 [\text{dfn}_x,\text{dfn}_x+\text{sz}_x) 。注意这里的 \text{subtree}(r) 是在 r_0 意义下定义的。
若 r \in \text{subtree}(x) ,找到 x \to r 路径上的第一个节点 y ,只要取 y 子树的补集,则 x 子树 DFS 序为 [1,\text{dfn}_y) \cup [\text{dfn}_y+\text{sz}_y,n] 。下图给出了这种情况的一个例子。
在 r_0 意义下有 \text{dep}_y=\text{dep}_x+1 ,找到 r 的 \text{dep}_r-\text{dep}_x-1 级祖先即为 y ,可以使用树上倍增优化。
对于 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 ,进行分步计数:
从 c 个空位中选择 j-x 个,方案数 \dbinom{c}{j-x} 。
给 j-x 个空位填入 1 \sim i-1 中的数,方案数 (i-1)^{j-x} 。
给 c-(j-x) 个空位填入 i \sim m 中的数,方案数 (m-i+1)^{c-j+x} 。
由乘法原理合并,写出答案式
\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 来决策。
若 y,z > x :放的 x 越多越好,只删一侧。
若 y,z<x :放的 x 越少越好,同时删首尾。
若 y<x \land z>x :从左侧先取更好,删去左侧。
若 y>x \land z<x :同理删去右侧。
这就是本题的贪心策略。实现的时候可以拿两个指针维护 S 的首尾位置,预处理每个位置左 / 右侧最靠近的不同字符。复杂度 O(n) 。代码。
【0】AGC007A Shik and Stone
若路径上两点满足右上—左下关系则不合法。
【1】AGC007D Shik and Game
注意到,最优策略每次回头收集硬币时,一定走到最远的未收集位置。根据性质设计 DP:
复杂度 O(n^2) ,考虑优化 DP。对 \max 分类讨论:
若 2x_i-2x_{j+1} \le T ,则 f_i \gets f_j+x_i-x_j+T 。其中 x_i+T 是常数,j 是一段区间,维护 f_j-x_j 的区间 \min 即可。
若 2x_i-2x_{j+1}>T ,则 f_i\gets f_j+x_i-x_j+2x_i-2x_{j+1} 。其中 3x_i 是常数,j 是一段前缀,维护 f_j-x_j-2x_{j+1} 的前缀 \min 即可。
两种情况的分界点可以二分求出。使用线段树优化 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} 为处理完 p_1 \sim p_i 后,当前 k=r-l+1 的方案数。
转移时考察 i 位置的限制类型:
DP 初值为 f_{0,1}=1 。
答案为 \sum \limits_{k=1}^{n+1} f_{n,k} 。
瓶颈在 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 最短路,我们需要支持下面的操作:
找出 \text{dis}_u 最小的点 u ,将点 u 删去。
枚举出边 u \to v ,使用 \text{dis}_u+w 更新 \text{dis}_v 。
我们用 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,更新历史和,查询前缀历史和。

可以用 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 矩形。

由于颜色的出现次数之和是 $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$,故四个方形的排布必然如下图所示:

变量 $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$ 个点构成图的独立集。可以发现图的形态是若干条链:

我们从长为 $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)

## 【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)
到底是谁在会这种抽象观察性质分讨题?
给排列拍到二维折线图。对于一个单调段,一次操作是让一个点上山 / 下山。对于波峰 / 波谷,点的通行是单向的,这是因为极值点两侧值不同,极值可以跨越但是路径不可逆。

找出所有单向通行的位置,那么问题大体上抽象成,有 $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)。