【听课记录】25.10-LCA-Week2

· · 个人记录

这周内容太爆炸了，所以基本没补，之后有时间再说吧。

10.01 降维

TEST_73（未公开）

题意

给定一棵树，q 次询问只保留编号在 [l,r] 内的点和边后点连通块个数。n,q\le 10^6。

题解

直接点边容斥，边被保留需要两个端点均被保留，在一个矩形内有贡献，直接扫描线即可，复杂度 \mathcal O((n+q)\log n)。没题写不了。

未公开题目

题意

给定 n 个区间 [l,r]，q 次询问给出 L,R,k，求满足 L\le l\le r\le R,r-l+1\ge k 的区间个数。n,q\le 2\times 10^6。

题解

按长度扫描线，这样已经解决了 r-l+1\ge k 的限制。之后可容斥转化为求 \sum[r_i\le R]-\sum[l_i\lt L]+\sum[l_i\lt L][r_i\gt R]，画到平面上也有相同结论。由于询问的 R-L+1\ge k 才可能有答案，最后一个式子可以忽略长度限制单独求。于是要做三遍单点加求前缀和的扫描线，树状数组即可，复杂度 \mathcal O((n+q)\log n)。没题写不了。

这里 lxl 说若三维中有两维对称，一般枚举 / 扫描不对称的那一维。比如本题中左右端点对称，于是扫描剩下的长度维可能比较好做。

P11621 [Ynoi Easy Round 2025] TEST_139

将查询差分成四个右上 2-Side 矩形，修改差分成两个右下角固定的 2-Side 三角和两个左下 2-Side 矩形。分讨两种修改对查询的影响，发现所有贡献条件均为二维偏序，贡献为二次函数，维护多个值进行带修二维数点，CDQ 分治即可，复杂度 O(q\log ^2q)。套两层分治而不用数据结构可以避免离散化。

这里 lxl 说能差分就差分，大部分情况下连常数都不会变大。

Done.

请输入文本

题意

给定 n 个区间 [l,r]，每个区间有权值 w，保证两两不包含。q 次询问给出 L,R,k，求满足 L\le l\le r\le R,r-l+1\ge k 的区间权值和。n,q\le 2\times 10^6。

题解

### P9061 [Ynoi2002] Optimal Ordered Problem Solver（弱化） #### 题意 给出二维平面上 $n$ 个点 $(x,y)$，支持删除 $x\le X,y\le Y$ 的所有点，询问矩形和。$n,m\le 2\times 10^6$。 #### 题解 由于删除的是一个左下角矩形，删除点形成一段折线。之后对询问差分成左下角矩形。之后容斥，如果已经在折线下方则答案为 $0$，否则分别求询问上方、右方、右上方的和，容斥一下可以得到答案。动态一维偏序和静态二维偏序，均可 $O(n\log n)$ 维护。弱化写不了。 ### P8337 [Ynoi2004] rsxc（弱化） #### 题意 给定 $n$ 个区间 $[l,r]$，保证两两不包含。询问给出区间 $[L,R]$，求所有 $L\le l\le R$ 的区间与 $[L,R]$ 交的长度和。$n,m\le 2\times 10^7$。 #### 题解 即求 $L\le l\le R$ 中 $\sum \min(r,R)-l+1$。由于区间两两不包含，即 $l,r$ 均单调，于是询问对应一段区间内的区间。$(1-l)$ 的和容易前缀和，而 $\min(r,R)$ 在分界线两侧取不同值，找到分界线后也可前缀和算贡献。分界线只与 $R$ 有关，双指针预处理即可，这里可能要先桶排。时间复杂度 $O(n+m)$。弱化写不了。 - 支配降维 可重复贡献时，可删掉无用元素。或错误答案一定被支配掉，此时不用管。 ### P11210 『STA - R8』强制在线动态二维数点 #### 题意 平面上 $n$ 个点 $(x,y)$ 均满足 $x\ge y$，要求支持单点修改坐标，查询 $(l,l)$ 和 $(r,r)$ 两点形成的矩形内 $x-y$ 最小值。$n,q\le 5\times 10^5$。 #### 题解 一个点会把其右下角的点支配掉，因为其答案更优且更容易被包含。这说明贡献点形成一段折线，然而这并没有什么用，因为修改时要支持删点，难以快速维护折线结构。但支配的性质还是要关注的。 考虑将 $(x,y)$ 放到 $x$ 上，并向 $(x,x)$ 连线，求端点在矩形内的最短连线。只有 $x$ 的限制是好做的，考虑去掉 $y$ 的限制。找到 $x\in [l,r]$ 的最小 $x$ 使得其对应的最大 $y\ge l$，则它会支配掉后面所有 $y\le l$ 的点，这时以该 $x$ 为左端点直接查询 $[x,r]$ 的 $x-y$ 最小值即可，答案不会出错。$x$ 可以线段树二分求，时间复杂度 $O(n\log n)$。 ### P11364 [NOIP2024] 树上查询 #### 题意 给出一棵树，$q$ 次询问 $[L,R]$ 长度不低于 $k$ 的子区间中，区间内编号对应的所有点 LCA 深度的最大值。$n,q\le 5\times 10^5$。 #### 题解 考虑区间 LCA 怎么求，显然可以取出 DFS 序最大和最小的两个点求 LCA，也可以求出所有 $i,i+1$ 的 LCA，这些 LCA 中深度最小的即为所求，可以用虚树证。于是设 $a_i$ 表示 $i,i+1$ LCA 的深度，区间 $[l,r]$ 的 LCA 深度即 $a$ 序列 $[l,r-1]$ 区间的最小值。 先特判掉 $k=1$ 的情况，用 ST 表求区间最值即可。剩余部分即求 $a$ 序列上 $[L,R-1]$ 长度不低于 $k-1$ 的子区间最小值的最大值。先画到平面上，考虑区间最小值的形式，每个 $(i,i)$ 点会向左上延伸出一个矩形，碰到比自己小的数时停止。求出该矩形后，可从其左上角向右下角无限延伸，每个点的答案是覆盖其的无限大矩形对应值的最大值。 考虑其实际意义的话，可以认为是找到了最小值不低于 $a_i$ 的极长区间 $[l_i+1,r_i-1]$，由于没有限制 $l\le i\le r$，所以可能会大于 $a_i$。之后求区间 $[s,e]$ 的最小值时，找到包含 $[s,e]$ 的所有极长区间，对其 $a$ 值取最大值即为答案，和平面上的推导相符。 最终要求 $[L,R-1]$ 内长度不低于 $k-1$ 的子区间最小值的最大值，显然长度更大的区间不优，于是只求平面上一条斜线的最大值。考虑对所有能贡献的极长区间求最大值，画到平面上可以拆成两个左上矩形和一个靠左的平行四边形，扫两遍就行，前者可以树状数组，后者只能线段树。复杂度 $\mathcal O((n+q)\log n)$。 ## 10.01 思考题 众数杀手 给定一个由 $1,-1$ 构成的长为 $n$ 的序列，其中有 $x$ 个 $1$，默认 $x$ 远小于 $n$。定义序列权值为所有非负区间并的长度。 - 可能的最大权值是多少？ 考虑令 $1$ 之间的距离足够远，则每个 $1$ 及其两侧会在最终并中，总点数为 $3x$。若全聚到一起，发现总点数也是 $3x$。事实上上界即为 $3x$，因为每个 $1$ 最多使得合法区间拓展 $1$ 的长度，即使不重复贡献也只有 $3x$。最劣应该是隔一个放一个，大概是 $2x$。 - 对于给定序列，输入 $x$ 个位置，如何在 $O(x\log n)$ 复杂度内求其权值？ 考虑从左到右遍历每个位置，每次找左边未被标记的最近 $-1$ 并将其标记，之后清空所有标记，再从右到左做一遍，只有两轮中至少被打过一次标记的位置会产生贡献，将个数加上 $x$ 即为答案。 - 对于给定序列，在 $n,x$ 同阶时，如何求区间和非负的区间个数？ 对其求前缀和后，即求有多少 $i<j$ 且 $s_i\le s_j$ 的对 $(i,j)$，容易用树状数组等做到 $O(n\log n)$。然而注意到原序列只有 $1,-1$，因此可以直接用桶 + 指针实时维护合法的 $i$ 个数，容易做到线性。 - 在 $x$ 远小于 $n$ 时，若上上个问题能 $O(x)$ 求解，是否也能 $O(x)$ 求解上个问题？ 只把上上个问题中不超过 $3x$ 个位置拿出来，对每个原序列上的连续段分别做上个问题即可，总时间复杂度显然为 $O(x)$。 ### P4062 [Code+#1] Yazid 的新生舞会 #### 题意 给定一个序列 $a$，求有多少个区间存在绝对众数。$n\le 5\times 10^5$。 #### 题解 枚举绝对众数为 $t$，令 $b_i=(-1)^{[a_i\ne t]}$，则转化为求 $b$ 有多少个子区间和为正。可以直接套用上面的几个问题求。现在需要快速找到 $3x$ 个位置，考虑直接使用序列并查集，预处理 $l_i=i-1,r_i=i+1$，之后直接查询两边首个未标记位置即可。 由于复原 $l,r$ 数组和清空标记只需操作拿出来的 $3x$ 个位置，于是单次复杂度也是 $O(x)$ 的。由于 $\sum x=n$，总复杂度为 $O(n)$，然而对拿出来的位置操作前需要对其排序，可能不得不加上一个排序的 $O(n\log n)$ 复杂度，也成为了复杂度瓶颈。 ### CF1446D2 Frequency Problem (Hard Version) #### 题意 给定一个序列 $a$，求众数不唯一的最长子区间长度。$n\le 2\times 10^5$。 #### 题解 考虑全局众数 $x$，若有多个则答案为 $n$，否则一定存在最优区间的众数包含 $x$。若众数不包含 $x$，则可以不断扩张该区间直到 $x$ 和某数出现次数相同。同时可将众数条件弱化为 $x,y$ 在区间内出现次数相同，显然这可以取到答案，而这样求到的不合法区间（$x,y$ 不为众数）一定不优，可以扩张直到 $x$ 与原众数出现次数相同。 于是问题变为固定 $x$，对所有 $y\ne x$ 求 $x,y$ 出现次数相同的最长子区间长度。将 $x$ 看成 $-1$，$y$ 看成 $1$，即求最长的和为 $0$ 子区间。仿照上题思路找出所有有效位置，再用前缀和相等判断即可。有一些细节，比如并查集要建在所有 $x$ 上之类。总之时间复杂度 $O(n\log n)$，还在排序。 ## 10.02 树上问题 主要是 LCA 相关性质。 ### CF1062E Company #### 题意 给定一棵树，$q$ 次询问从 $[l,r]$ 中删去一个点后，剩余点 LCA 深度的最大值。$n,q\le 10^5$。 #### 题解 点集的 LCA 与 DFS 序最大和最小两点的 LCA 相同，因此只有删这两个点之一才可能使 LCA 深度增大。维护区间 DFS 序最大最小次大次小值，判断删哪个更优即可。ST 表维护区间最值，LCA 随便求一下，复杂度 $\mathcal O((n+q)\log n)$。 ### CF176E Archaeology #### 题意 给定一棵树，动态维护一个点集，需要支持增删，查询当前点集形成虚树的边权和。$n,q\le 10^5$。 #### 题解 对于大小为 $k$ 且按 DFS 序排序的点集 $S$，其虚树边权和为 $\frac{\sum_{i=0} d_{S_i,S_{(i+1)\bmod k}}}2$，即相邻两点距离之和的一半，正确性比较显然。于是按 DFS 序维护当前点集，插入时跟前驱后继更新一下即可，复杂度 $\mathcal O(q\log n)$。 ### P6071 『MdOI R1』Treequery 做法应该类似上一题，找出 DFS 序上的前驱后继即可，强制在线要主席树。之后应该会做。 ## 10.03-10.04 计数 - 二项式反演 ### CF995F Cowmpany Cowmpensation #### 题意 给出一棵 $n$ 个点的树，要求填入 $[1,k]$ 内的整数，且满足每个的值不大于其父亲，求方案数。$n\le 3000,k\le 10^9$。 #### 题解 有一个显然的 DP，设 $f_{u,i}$ 表示以 $u$ 为根的子树 $u$ 点填 $i$ 的方案数，有 $f_{u,i}=\prod_{v}(\sum_{j\le i}f_{v,j})$，加上前缀和优化后是 $\mathcal O(nk)$ 的。然而注意到 $n$ 个点最多只会填 $n$ 种值，于是考虑求 $g_i$ 表示一共填 $i$ 种值的方案数，答案即 $\sum_i {k\choose i}g_i$。 仍然进行 $f$ 的 DP，且限制第二维不超过 $n$。此时显然有 $g_1=f_{1,1}$，之后有 $g_i=f_{1,i}-\sum_{j\lt i} {i-1\choose j-1} g_j$，这样就求出了 $g$。至于 $k\choose i$ 这种 $k$ 很大 $i$ 较小的组合数，可以预处理 $k$ 的前 $n$ 次下降幂，总复杂度 $\mathcal O(n^2)$。 - min-max 容斥 ### [ABC242Ex] Random Painting #### 题意 给出 $m$ 个在 $[1,n]$ 内的区间，保证每个位置被至少一个区间包含。每次随机取出某个区间，并标记区间内的所有位置，求期望取多少次后所有位置均被标记。$n,m\le 400$。 #### 题解 设 $t_i$ 表示 $i$ 位置第一次被标记的时间，求 $E(\max t_i)$。直接考虑 min-max 容斥，变成了 $\sum_{S}(-1)^{\left|S\right|+1}E(\min_{i\in S} t_i)$。这里 $E(\min_{i\in S}t_i)$ 就比较好算了，根据定义只需求出内部有 $S$ 中位置的区间数量 $c$，则每次取都有 $\frac cm$ 的概率覆盖到 $S$ 内的位置，期望次数为 $\frac mc$。 于是对所有 $c$ 求恰有 $c$ 个区间内有 $S$ 中位置的 $S$ 系数和，直接 DP，设 $f_{i,j}$ 表示最后一个位置选在 $i$，且目前有 $j$ 个区间合法的带容斥系数方案数。初值为 $f_{0,0}=-1$，转移为 $f_{k,j}\rightarrow f_{i,j+\sum[k\lt l\le i\le r]}$，系数为 $-1$。 转移中加的量可以提前二维前缀和预处理，总复杂度为 $\mathcal O(n^2m)$。 - 其他容斥 ### LOJ3395. Yet Another Permutation Problem 不难发现 $k$ 次操作能得到当且仅当存在长为 $n-k$ 的上升子串，再取补集转为对极长上升段长不超过 $n-k-1$ 的排列计数。只关心邻项相对大小，即长为 $n-1$ 的 <,> 串，要求 < 连续段长度不超过 $t=n-k-2$。串固定时可对 > 容斥，对未钦定的 > 位置 DP 求答案。考虑 $t$ 的限制时，同样对未钦定的 > DP，其间为上升段，要求其中原 < 连续段长度不超过 $t$，每有一个 > 乘 $-1$ 的系数，转移系数为所有合法串的容斥系数之和。 设 $i$ 个符号转移系数为 $g_i$，构造 OGF $G(x)=\sum g_ix^i$。为了限制 < 段长，每次拼上一个 >，限制两 > 间 < 不超过 $t$ 个。单个 < 段 OGF 为 $F(x)=\sum_{i=0}^t x^i=\frac{x^{t+1}+1}{x-1}$，枚举 > 数量可得 $G(x)=F(x)\sum_{i=0}^{\infin}(-xF(x))^i$，等比数列求和可得 $G(x)=\frac{F(x)}{1+xF(x)}$，将前式代入化简可得 $G(x)=\frac{1-x^{t+1}}{1-x^{t+2}}$，将分母展开得 $\sum_{i=0}^{\infin}x^{i(k+2)}-x^{i(k+2)+k+1}$，即只有模 $k+2$ 为 $0,k+1$ 的位置有值，于是用 $g_i$ 暴力 DP 即可，复杂度为调和级数的 $\mathcal O(n^2\log n)$。 Done. ### [ABC236Ex] Distinct Multiples 两两不等的限制很难做，将其容斥为若干对 $(u_i,v_i)$ 相等，容斥系数为 $(-1)^{\left|E\right|}$。每次加入一个连通块，需预处理 $k$ 个点的连通图 $(-1)^{\left|E\right|}$ 之和 $g_k$。由于连通图无序组合为任意图，而任意图的 $f_k=(1-1)^{\frac{k(k-1)}2}=[k\le 1]$，需要写出 $f,g$ 之间的关系求 $g$。枚举某个点所在连通块大小，有 $f_k=\sum_{i=1}^k g_i f_{k-i}{k-1\choose i-1}$，由于只有 $f_0=f_1=1$，实际上为 $f_k=g_k+(k-1)g_{k-1}$。由 $f_k=[k\le 1],g_1=1$ 可推出 $g_k=(-1)^{k-1}(k-1)!$。 事实上 $f=\exp g,g=\ln f$，也可以直接通过集合幂级数 ln 求 $g$。此时需将连通块无序组合，每个连通块的权值为 $m$ 除以所有数的 LCM 再乘上容斥系数，枚举子集 / 子集卷积 / 集合幂级数 exp 均可，复杂度 $\mathcal O(3^n+n2^n)$ 或 $\mathcal O(n^22^n)$。 Done. ### P8329 [ZJOI2022] 树 ### P10591 BZOJ4671 异或图 由于需要同时考虑所有点边，只能暴力枚举 $\text{Bell}(n)$ 种点集划分。此时钦定不同点集间无边，提取出这些边后相当于选子集使得异或和为零，线性基可求。每种划分的权值应只与点集数量 $k$ 有关，设其为 $w_k$。此时考虑每种实际图 $G$ 的贡献和，其会在能任意合并连通块得到的状态被统计，若其有 $k$ 个连通块，则贡献系数为 $f_k=\sum_{i=1}^k S_2(k,i) w_i$，其中 $S_2$ 为第二类斯特林数。 根据斯特林反演，有 $w_k=\sum_{i=1}^k (-1)^{k-i}S_{1}(k,i)f_i$。而最终需要 $f_k=[k=1]$，据此可推出 $w_k=(-1)^{k-1}S_1(k,1)=(-1)^{k-1}(k-1)!$。于是每个点集划分的贡献系数已知，爆搜后统计答案即可。总复杂度大概 $\mathcal O(n^2s\text{Bell}(n))$。 Done. - 自动机 ### YDRS005E. 将那朵云彩也跨越 - 其他计数类 DP ### P10547 [THUPC 2024 决赛] 排列游戏 ### [ARC163D] Sum of SCC ### [AGC013D] Piling Up - 形式幂级数与生成函数 ### P4365 [九省联考 2018] 秘密袭击 coat ### [ABC241Ex] Card Deck Score ### QOJ8543 Periodic Sequence - 杂题 ### [ABC288Ex] A Nameless Counting Problem ## 10.05 构造 这部分没有收入做题计划，只记了题号。 - 鸽巢原理 ### CF1450C2 Errich-Tac-Toe (Hard Version) #### 题意 给出一个 $n\times n$ 网格图，其中 $k$ 格非空，每格为 $0$ 或 $1$。可单点修改至多 $\lfloor\frac k3\rfloor$ 次，要求横竖相邻三个元素不全相等，构造方案。$n\le 300$。 - DFS 树 ### P5811 [IOI 2019] 景点划分 #### 题意 给定一张图，要求将其划分成大小为 $a,b,c$ 的三部分，使得至少两个部分连通。$n\le 10^5,m\le 2\times 10^5$。 - 树 ### CF1205D Almost All #### 题意 给定一棵树，要求每个点分配非负整数点权，使得 $\forall x\in[1,\lfloor\frac{2n^2}9\rfloor]$，树上存在点权和为 $x$ 的路径。$n\le 5\times 10^5$。 - 图 ### UOJ670 【UNR #5】获奖名单 #### 题意 给定 $n$ 个长不超过 $2$ 的字符串，要求任意翻转后拼成一个回文串，构造方案。$n\le 5\times 10^5$。 ### CF1270G Subset with Zero Sum #### 题意 给定 $a$，满足 $i-n\le a_i\le i-1$，求一个和为 $0$ 的子集。$n\le 5\times 10^5$。 ####题解 老题了，考虑由 $i$ 向 $i-a_i$ 连边，注意到该图 $n$ 点 $n$ 边，一定是内向基环树森林。又注意到每个环上 $i-a_i$ 的和与 $i$ 的和相等，于是 $a_i$ 的和为 $0$，找到图中任意一个环即为答案，复杂度 $\mathcal O(n)$。 当然之后 LCA 又讲了一遍这个题，是用前缀和和抽屉原理解决的。 - 归纳 ### [ARC122E] Increasing LCMs #### 题意 给定 $a$ 序列，重排使得前缀 LCM 严格递增。$n\le 100,a_i\le 10^{18}$。 ### CF1637G Birthday #### 题意 初始存在 $[1,n]$ 的 $n$ 个数，每次操作取出 $x\ge y$，将其变为 $x+y,x-y$ 两数，希望最终数字全相同且尽可能小，操作次数不超过 $20n$。$\sum n\le 5\times 10^4$。 - 杂题 ### P6948 [ICPC 2018 WF] Single Cut of Failure #### 题意 给出一个矩形，存在若干条线段，均满足端点在边框上且不与边框重合。求多少条满足该限制的线段可切断所有给定线段。$n\le 10^6$。 ### CF1658F Juju and Binary String #### 题意 给定长为 $n$ 的序列，构造尽可能少的长度和为 $m$ 的子串，使得其中 $1$ 所占比例与原序列相同。$m\le n\le 2\times 10^5$。 ### CF1622F Quadratic Set #### 题意 给定 $a_i=i!$，要求选出一个尽可能大的子集，使得其乘积为完全平方数。$n\le 10^6$。