本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-15 10:10:40

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

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

先差分，将查询矩形差分成 $X\ge a,Y\ge b$ 的形式。之后讨论修改 $(x,y,d)$ 对询问 $(a,b)$ 的贡献形式，发现所有的贡献条件都是二维偏序，只是贡献有的是二次函数，多维护几个值进行带修二维数点即可，可以 CDQ 分治解决，复杂度 $O((n+q)\log ^2n)$。之后应该会写。

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

请输入文本

题意

给定 $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$。

题解

$l,r$ 两维分别递增，画在二维上连起来是折线，因此 $l,r$ 的二维限制一定对应折线上的一段，限制变成了一维的。直接扫描长度一维即可，复杂度 $\mathcal O((n+q)\log n)$。没题写不了。

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

状态数的级别需要用生成函数证，之后还得学学。

[ABC236Ex] Distinct Multiples

P8329 [ZJOI2022] 树

P10591 BZOJ4671 异或图

• 自动机

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$。