1 月做题记录

1 离线动态图连通性

众所周知的做法是离线后对时间轴做线段树分治，需要使用可撤销并查集维护加边撤销，查询两点连通性，复杂度 \(O(n\log^2 n)\)。

事实上我们可以做到 \(O(n \log n)\)。考虑线段树分治结构。在线段树上每个点有一个集合 \(S \subseteq E\)，我们要维护一个图，递归进入这个结点时我们需要加入 \(S\) 内的所有边，离开时撤销，递归到叶子时需要支持一次查询两点连通性。

考虑不使用并查集维护之，递归到每个点加入边时，考虑子树内的所有边 \((u,v)\)，包含修改边与查询边，我们只关心这些边的连通情况，即只关心这些边对应的连通块编号。递归到一个结点时，我们将这个点对应的边拉出来 DFS，然后考虑子树内的所有边，更新其所属连通块编号。这样复杂度是每个点子树内边数和，显然还是 \(O(n \log^2 n)\)，但是显然每个子树内多条本质相同的边没有意义，故复杂度可以做到每个点子树内本质不同边数和，这样就是 \(O(n \log n)\) 的。

2 P5416

对每个点考虑其存活时间，是其子树除去其子树内若干小子树，小子树就是删除的部分。用 DFN 序区间刻画子树形态，这样对于所有点总共有 \(O(n)\) 段存活时间，线段树分治即可。

3 QOJ8363

我们的目标是对于每个 \(i<j\) 判定是否存在 \((i,j)\) 这条边。

将所有这样的 \((i,j)\) 按照 \(j-i\) 从小到大排序，对于长度 \(l\) 从小到大依次确定所有 \(j-i=l\) 的出现过的边。

对于固定的 \(l\)，考虑分治，对于目前分治区间 \([l,r]\)，我们的目标是找到所有 \(i \in [l,r]\) 的 \((i,j)\) 对。考虑将所有 \(i \in [l,r]\) 的 \((i,j)\) 对拼在一起，形如 \(i,i+l,i+2l,\cdots,i+kl,i+kl+1,i+(k-1)l+1,\cdots\)，使得所有对都作为相邻的出现过，且其余的相邻位置都满足差小于 \(l\)。在前缀和后缀拼接一个相邻差为 \(1\) 的即可。这样总询问次数就是 \(O(n \log n)\) 的了。

4 LOJ4988

考虑 Boruvka，对于每个连通块找出向外最小出边，维护目前得到的可能成为答案的一组共享端点的边，每次加边都可以通过若干次 \(1\) 类询问得到新的边集，然后使用一次 \(2\) 类询问即可确定最小出边。这样的过程只会进行 \(n-1\) 次，故询问 \(2\) 的次数即为 \(n-1\) 次，询问 \(1\) 是 \(O(m \log n)\) 的，但肉眼可见根本跑不满，可以通过。

5 神秘题

限制等价于每个 \(b\) 大于等于前缀 \(a\) 的最大值。这个限制相当不容易直接下手，尝试将路径分步维护。具体来说，对于一条路径，我们希望在所有 \(a\) 的前缀最大值处分段。按照 \(a\) 从大到小确定每个点的答案，那么对于目前的点 \(u\)，其答案来源于所有 \(j\) 满足 \(a_j>a_u\) 的点 \(j\)，且 \(u\) 到 \(j\) 可以只经过 \(a_k \leq a_u,b_k \geq a_u\) 的点到达。对 \(a\) 从大到小扫描线，每个点 \(k\) 有一个存活区间。我们的操作可以形式化描述成每个点有存活状态和点权，支持单点修改点权与存活状态，查询一个点能到达的存活的点的点权最大值。

离线做线段树分治，维护可撤销并查集即可。线段树分治时先向右侧递归然后向左侧递归就可以解决修改点权的问题。

6 神秘题

考虑类似猫树分治，也就是递归处理横跨区间中点的答案。对于分治区间 \([L,R]\)，中点为 \(mid\)，对于询问区间 \([l,r]\) 满足 \(l \leq mid < r\)，考虑在 \(r\) 第一次跳到 \(mid\) 左侧时统计这之前的答案，并将新的 \(l,r'\) 递归进入左区间求解。对于寻找 \(r'\)，简单倍增处理即可。复杂度 \(O((n+q)\log^2 n)\)。

7 P3527

直接整体二分是 \(O(n\log^2 n)\) 的。此外有两个学习价值较大的做法。

第一个做法是考虑对于第 \(i\) 次修改 \(l,r,a\)，在 \(l\) 处添加 \((i,a)\)，在 \(r+1\) 处添加 \((i,-a)\)，然后从前往后用主席树维护之，查询时在主席树上一起二分，时空复杂度均为 \(O(n \log n)\)。

另一种做法是你考虑整体二分时也用这个差分做法而不是在内部使用非线性数据结构，这也是可以做的，时间复杂度 \(O(n \log n)\)，空间线性，写起来可能比较麻烦。

8 P14889

一棵有向树是以点 \(k\) 为根的根向树，当且仅当对于任意 \(u \neq k\)，点 \(u\) 恰有一条出边，此外点 \(k\) 没有任何出边。

每个除点 \(k\) 之外的点恰有一条出边，意味着所有有向边边 \(u \rightarrow v\) 的起点 \(u\) 构成的可重集恰好等于 \(\{1,2,\cdots,n\}\setminus \{k\}\)，而维护集合相等的经典方法是考虑哈希。以异或哈希为例，对于每个点 \(u\) 随机权值 \(w_u\)，我们只需要动态维护 \(\bigoplus \limits_{(u\rightarrow v)\in E} w_u\)。在树上维护这类结构的经典方法是，固定根后对于每个点将儿子和父亲分开维护，这样修改一个点的信息只会影响到其父亲的信息，从而做到高效维护整个结构。

9 UVA1625

对于每种字符，若其第一次和最后一次出现分别位于 \(x,y\)，其中 \(x \leq y\)，那么 \(y-x\) 就等于区间 \([x,y-1]\) 长度。这也就意味着在进行 DP 的过程中，可以把贡献拆到 \([x,y)\) 内的每个点上。这样直接记 \(f_{i,j}\) 表示长度为 \(i,j\) 前缀对应的答案即可。复杂度 \(O(nm)\)。

10 P3581

考虑按值域依次插入 \(1\) 到 \(n\)，维护连续段 DP 结构，插入 \(i\) 时限定其左右两侧只能是 \([i-p+1,i)\) 之间的数。对于这 \(O(p)\) 个数记录一下他们的状态即可。

11 ABC261G

考虑 \(S\) 的每个字符最终会对应 \(T\) 的一段区间，这些区间 \([l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\) 满足 \(r_i=l_{i+1}-1\) 且 \(l_1=1,r_n=m\)。故只需要能求 \(f_{i,l,r}\) 表示字符 \(i\) 变为 \(T\) 的子串 \(T[l\cdots r]\) 的最小代价即可，这个转移不难，推一下就很容易了。

12 P3592

对于限制区间最值问题，考虑对笛卡尔树结构进行 DP。

\(f_{l,r,c}\) 表示区间 \([l,r]\) 最小值大于等于 \(c\)，仅考虑所有包含于 \([l,r]\) 的区间贡献时的答案，\(c\) 这一维做离散化，不难做到 \(O(n^3m)\)。

13 LOJ6433

相对简单的一个题。枚举集合 \(S\) 钦定其为最短的最大前缀和，计算有多少种排列使得其确实如此。要求即为 \(U - S\) 的排列满足任意一个前缀和为负数且 \(S\) 的排列满足任意一个后缀和为正数。这个的方案数容易 DP 求出。复杂度 \(O(n2^n)\)。

14 QOJ7895

首先，在树上做容量上界为 \(m\) 的背包，转移时枚举左右大小进行合并，复杂度是 \(O(nm)\) 的，原因是考虑将背包合并过程看作 DFN 序上两个点在 LCA 处的贡献，易得其确实为 \(O(nm)\)。

注意到 \(f_{i,j}\) 的 \(j\) 这一维其实只有 \(\min(k,\dfrac{sz}{k})\) 个状态，所以直接做就是 \(O(n\sqrt n)\)。

15 Subset Sum

题面：

给定长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\) 以及正整数 \(w\)，判定是否存在 \(a\) 的子集和为 \(w\)。

\(n \leq 10^4\)，\(1 \leq a_i \leq 8000\)，\(1 \leq w \leq \sum a_i\)。

解法：

朴素背包不低于 \(O(\dfrac{n^2V}{w})\)，无法通过。

令 \(f(S)\) 表示 \(\sum \limits_{i \in S} a_i\)。先随意找出一个集合 \(S\) 使得 \(s=f(S) \leq w\) 且 \(S\) 是极大的，即对于任意 \(i \notin S\)，\(s+i > w\)。

接着我们需要进行调整。即判定是否存在集合 \(A \subseteq S\) 与集合 \(B \subseteq U-S\)，使得 \(s-f(A)+f(B)=w\)，即 \(f(B)-f(A)=w-s\)。显然 \(w-s \in [0,V]\)，否则若 \(w-s>V\)，\(S\) 必定不是极大集合。

问题变为在 \(S\) 内找集合 \(A\)，在 \(U-S\) 内找集合 \(B\)，使得 \(f(B)-f(A)=k\)，其中 \(k \in [0,V]\)。直接做复杂度还是 \(O(n^2V)\) 的，因为背包的值域依然可以达到 \(O(nV)\)。考虑类似 Equal Sums 一题，将过程分步，每次如果和小于 \(0\) 则向 \(B\) 中加入某个数，否则向 \(A\) 中加入某个数。若是如此，DP 过程中值域就只需要记录 \(O(V)\) 个状态，代价是需要分别记录 \(S\) 和 \(U-S\) 选的前缀是什么，故复杂度还是 \(O(n^2V)\)。

具体来说，记 \(f_{i,j,k}\) 表示 \(S\) 中选了前 \(i\) 个，\(U-S\) 中选了前 \(j\) 个，现在的和是 \(k\) 是否可行。其中 \(k\) 是 \(O(V)\) 量级的，所以复杂度并没有变优。

但这么做有一个好处，由于变量值都是 \(0\) 或 \(1\) 且 \(i,j\) 的限制是选了前多少，所以 DP 值有单调性。具体来说若 \((a,b,k)\) 可行，则对于任意 \(c \geq a, d \geq b\) 都有 \((c,d,k)\) 可行。我们希望记 \(g_{i,k}\) 表示对于 \(i,k\) 来说最小的 \(j\) 使得 \(f_{i,j,k}=1\)。这个应该就好做了，对着刚才的转移过程刻画一下细节即可。复杂度 \(O(nV)\)。

16 NFLS 训练赛 T4

直接维护是困难的，原因大概是难以维护 \(\sum \limits_{i} \dfrac{t_i}{2^{c_i}}\) 与整数 \(x\) 的大小关系。虽然静态的这个问题是可以做的，大概是考虑依据 \(2\times 2^{-k}=2^{-(k-1)}\)，从而按照 \(k\) 从大到小依次做 \(s_{k-1}\gets \lfloor \dfrac{s_k}{2}\rfloor\)，对比 \(s_0\) 和 \(x\) 即可。但是原问题大概是对 \(c\) 的后缀加形式，这个动态过程不方便维护。

考察问题的难点究竟在于什么。最让我们头疼的问题是速度减半过程可能发生非常多次，以至于不可能真正维护速度，使用浮点数或者高精度都是不现实的。

这时需要一个高妙的转化。首先考虑如果 \(x\) 足够大，以至于所有减速带都会被撞到，那么答案容易维护。

接下来做法的动机就是尝试规避不好看的结构，也就是速度减半。考虑把问题等效于速度恒定，但减速时距离翻倍。也就是说，每秒执行 \(x \gets x - 1\)，遇到减速带时，\(x \gets 2x\)，求第一次使得 \(x=0\) 的时刻。

对时间轴建立线段树，每个点维护最小的 \(x\) 使得以 \(x\) 的最终距离进入区间时，在区间内的任意时刻 \(x\) 都为正数，以及维护以 \(x\) 进入后最终得到的 \(x\) 是多少。第三个量可能被取模，但是若如此则整个过程必定经过所有减速带，这时答案不难计算。上述变量都不难合并，查询只需要一个线段树二分状物即可。

这个题的精妙之处在于这个神秘转化，很厉害啊。

17 P14832

场上完全不会这个题，笑哭。

题意大概是说给你一个 \(n\) 个点 \(m\) 条边的 DAG，每个入度为 \(0\) 的点写了一个权值 \(0\) 或 \(1\)，此外每个点都给定一个 \(a_i\)。你可以任意次反转一个入度为 \(0\) 的点的 \(01\) 点权，花费对应的 \(a\) 值。操作后，对于任意一个点 \(u\)，如果其能同时被点权为 \(0\) 和 \(1\) 的某两个入度为 \(0\) 的点到达，则需要额外花费 \(a_u\) 的代价。试求最小总花费。

范围十分奇怪，这个结构启发我们考虑网络流。

首先我们考虑如何刻画一个点同时被 \(0\) 和 \(1\) 类点到达。考虑建两层图，一层是原图，一层是原图的反图，容量都是 \(+\infty\)，对于每个入度非 \(0\) 的点 \(u\)，在第一层向第二层对应的点连一条容量为 \(a_u\) 的边，表示这个点可以删去，花费是 \(a_u\)。对于入度为 \(0\) 的点，根据其原颜色分类讨论，两者对称，不妨考虑原点权为 \(0\)。此时本来是 \(S\) 向第一层对应点连了一条边，但可以花费 \(a\) 的代价改为从第二层对应点向 \(T\) 连一条边。不放连两条边，\((S,u,L)\) 与 \((u',T,L+a_u)\)，\(L\) 是一个极大值。这样可以确保两条边恰好断一条。跑最大流即可。

18 P14909

这个题挺有意思。

根据子任务 \(1,2\) 的提示不难看出我们应该考察 \([1,r]\) 的答案与询问区间 \([l,r]\) 的答案的关系。

首先先把前缀答案集合求出来。这很简单。考虑 \(f_i\) 表示 \([1,i]\) 的最大权独立集，则转移是 \(f_{i-1}\rightarrow f_i\) 与 \(f_{i-2}\cup \{i\} \rightarrow f_i\)，\(n\) 次询问内即可求出所有 \(f\)。

考虑询问区间 \([l,r]\)，根据 \(f_r\) 尝试求出区间答案。我们考虑找到 \(f_r\) 内大于等于 \(l\) 的最小位置，称之为 \(x\)，显然其只可能是 \(l,l+1,l+2\) 中的一个，这是因为所有数都是正数，不可能有相邻三个位置同时不选。

若 \(x=l\)，则区间答案显然就是 \(f_r\) 中截取 \([l,r]\) 部分。

若 \(x=l+2\)，则区间答案显然就是 \(f_r\) 中截取 \([l,r]\) 部分，然后加上 \(l\)。

上述两类结论的发现与证明都是简单的。

较难的是 \(x=l+1\)，此时区间答案有可能选 \(l\) 也有可能不选，需要进一步分析。

为了方便描述考虑定义在 \([1,r]\) 的一个 \(01\) 序列，每个位置 \(i\) 描述了 \(i \in f_r\) 是否成立，即 \([1,r]\) 的最大权独立集是否包含 \(i\)。

考虑 \([l,r]\) 中最靠前的相邻的 \(00\)，则在第二个 \(0\) 与其之后的区间最大独立集和 \(f_r\) 截取这段后缀应该是相同的，容易反证。

在这个位置之前的结构就是连续的 \(010101\cdots 10\)，结尾是 \(0\)。此时可以发现最优策略一定是不变或者翻转一个以 \(1\) 结尾的前缀。证明是考虑一定不存在 \(i\) 使得其为 \(1\)，但是在区间答案中 \(i\) 与 \(i-1\) 都是 \(0\)。

问题进一步可以归结为区间查询最大值。考虑预处理按 \(r\) 扫描线维护单调栈，查询直接求即可。次数不超过 \(3n+q\)。

19 P11707

考虑先二分答案 \(mid\)，记 \(d_{u,v}\) 表示原链上 \(u,v\) 两点间的距离。对于任意满足 \(d_{u,v} > mid\) 的二元组 \((u,v)\)，其必定需要通过新增的边以减小两点之间的最短距离。

假设最终新增的边为 \((a,b)\)，其中 \(a<b\)。尝试对于每个 \(b\) 研究是否存在合法的 \(a\)。对于每个上述满足条件的 \((u,v)\)，不妨令 \(u<v\)，则显然 \(b \geq u\)，分类讨论 \(b \in [u,v)\) 与 \(b \geq v\)。

先考虑 \(b \geq v\)，则其对应的 \(a\) 显然是和一个包含 \(u\) 的区间取交。对于 \(b\geq v\) 的形式，不难发现对于每个 \(u\) 只需要找到最小的满足 \(v > u\) 且 \(d_{u,v} > mid\) 的 \(v\) 并考虑这一对 \((u,v)\) 的影响。这些 \((u,v)\) 二元组的两维都是单调不降的。所以对于每个 \(b\)，只需要考虑最近的和最远的符合 \(v \leq b\) 的两组即可。

同理 \(b \in [u,v)\) 时，也只需要考虑最近和最远两对。看起来直接写是 \(O(n \log n \log V)\)，没准精细实现一下就是 \(O(n \log V)\)，我也不清楚。

纯口胡，假了告诉我。

20 P12019

首先每个点扩展到的一定是一个矩形，否则必然有一个位置相邻至少两个被覆盖。

进一步，观察最终扩展出的矩形形态。显然其外层一圈要么是 \(1\) 要么是矩形外部，并且其内部没有一行或一列全都是 \(1\)。如果能找到所有这样的关键矩形，那么对于每个点求答案即找出包含这个点的最小矩形。

按照列从右向左扫描线，我们希望在每个关键矩形的左上角的左上角找出这个关键矩形。其实这个过程只需要对于每个点维护向下向右的极长连续 \(1\) 长度然后做一个单调栈状物即可。同时你会发现关键矩形数量是 \(O(nm)\) 的。

找出所有之后对每个点找包含其最小的是容易的，线段树每个点挂一个 multiset 就可以维护，复杂度 \(O(n^2 \log^2 n)\)，但远远跑不满。

21 CF2178G

这个题的提示有点明显了。限制是每条弦出现偶数次，所以考虑异或哈希，则相当于所有可行的链的弦异或和最终等于 \(0\)。

记 \(f_i,g_i\) 表示以 \(i\) 结束的弦数量奇偶性与以 \(i\) 结束的弦的异或总和。转移需要从所有 \(l_i \cap l_j \neq \varnothing\) 的地方转移，看起来是二维限制但是考虑若 \(l_i=(u,v)\)，将 \(j\) 的两端点分开把限制改为统计在 \(u,v\) 构成的弧上的所有答案异或，这样如果不交则必然贡献偶数次之后抵消，有交则必定恰好贡献 \(1\) 次。复杂度 \(O(n \log n)\)。

22 CF1271F

形式化考虑问题。等价于给定非负整数 \(a_1,a_2,\cdots,a_7\) 以及 \(l_1,r_1,l_2,r_2,l_3,r_3\)，试求多元不等式组 \(\begin{cases} c_4 + c_5+c_6+c_7 \in [l_1,r_1] \\ c_2+c_3+c_6+c_7 \in [l_2,r_2] \\ c_1+c_3+c_5+c_7 \in [l_3,r_3] \end{cases}\)

是否存在 \(c_i \in \mathbb{Z}\) 且 \(0 \leq c_i \leq a_i\) 的解。

枚举 \(c_6=x\) 与 \(c_7=y\)，要求 \(c_4+c_5 \in [l_1',r_1']\)，\(c_2+c_3 \in [l_2',r_2']\)，\(c_1+c_3+c_5 \in [l_3',r_3']\)，注意到 \(c_1,c_2,c_4\) 都只出现在一个不等式中是独立的，所以限制等价于限定了 \(c_3\) 的范围，\(c_5\) 的范围，以及 \(c_3+c_5\) 的范围，不难直接解出。复杂度 \(O(n^2)\)。进一步可以只枚举 \(c_6+c_7\) 做到线性。

23 CF1279F

首先进行一些简单转化，不难得到问题等价于每个点有一个非负权值，选不超过 \(k\) 个点，相邻差 \(\geq l\)，最大化点权和。这是经典的关于 \(k\) 有凸性的函数，wqs 二分即可，复杂度 \(O(n \log n)\)。

24 CF1292C

这个结构很简单吧。不知道在考察什么。

显然 \(\sum \limits_{u,v} \mathrm{mex}(u,v)\) 等于从 \(0\) 到 \(n-2\) 依次考虑所有边，考察每个前缀边集的并，要求其是一条路径，贡献是有多少条路径包含这条路径。

那么记 \(f_{u,v}\) 表示目前这段前缀的边集并是 \(u,v\) 的答案。转移是容易的。复杂度 \(O(n^2)\)。

25 CF1418G

好题。

有一些技巧性较低的做法，比如考虑每种数然后拉出一些限制，然后扫描线维护线段树之类的，应该是容易的，没想过细节。

但是我们还可以做到线性。考虑从左向右扫描线，对于每个 \(r\) 考虑哪些 \(l\) 符合条件。首先我们不难双指针出一个最小的 \(l\) 满足 \([l,r]\) 内每种数出现次数至多为 \(3\)。然后考虑限制每种出现次数都是 \(3\)。对于每个前缀考虑记下每种数出现次数模 \(3\) 意义下的值，那么做个哈希即可。复杂度线性。

26 CF1422F

显然得从质因数角度考虑问题。按照 \(r\) 扫描线对每个质因数维护单调栈结构，修改在线段树上操作即可。由于强制在线得将过程可持久化下来。复杂度 \(O(n \omega(v) \log n)\)。

27 CF1572F

对于每个 \(i\) 其能到达的显然是一段区间，不妨记为 \([i,x_i]\)。操作等价于对 \(x\) 进行单点修改，然后对于一段前缀做 \(x\) 的区间 chkmin。询问等价于对于每个 \(i\) 执行区间 \([i,x_i]\) 加 \(1\) 后查询区间和。

由于有区间 chkmin 考虑用吉司机线段树维护这个结构。每个点维护最大值次大值以及最大值出现次数，注意到将所有最大值改为 \(v\) 的这个操作对于每个位置而言进行的操作是一样的，所以另使用一棵线段树维护 \(b\) 即可。复杂度 \(O(n \log^2 n)\)。

28 CF1606F

考虑 \(k\) 确定怎么做。

本质上要选 \(v\) 子树内一个包含点 \(v\) 的连通块，设其为 \(S\)，最大化 \(f(S)-(|S|-1)k\)。\(f(S)\) 表示下面挂着的点的个数。

记 \(g_u\) 表示在 \(u\) 子树内选一个包含 \(u\) 的连通块 \(S\)，最大的 \(f(S)-|S|k\)。则 \(g_u=-k+\sum \limits_{v} \max(1,f_v)\)。查询点 \(v\) 答案即求 \(\sum \limits_{x \in \mathrm{son}_v} \max(1,f_x)\)。

按照 \(k\) 离线从大到小，维护一些树上结构即可。

29 CF1697F

由于值域只有 \(10\) 做一些简单的 2-SAT 建图即可。

30 CF1804F

还挺牛。

令直径为 \(D\)，任意选点 \(u\)，考虑距离 \(u\) 最远的距离为 \(d\)，则必有 \(d \in [\lceil \dfrac{D}{2} \rceil,D]\)，上界显然，下界原因在于若最远小于等于 \(\dfrac{D}{2}\) 那么两个直径端点之间就有一条小于 \(D\) 的路径了。

然而时刻动态维护 \(d\) 仍然不可行，一开始先算出一个 \(d\)，考虑若某个时刻真正的 \(d' \geq \dfrac{d}{2}\)，那么以 \(d\) 作为答案仍然可行。于是每次二分出第一个使得 \(d' < \dfrac{d}{2}\) 的时刻重算新的 \(d\) 即可。复杂度 \(O(n \log^2 n)\)。

31 CF1657F

【模板】2-SAT。

32 QOJ8005

直接做子集 DP 是 \(O(3^n)\) 的，无法通过。

考虑折半。由于一个集合的代价取决于权值最大的，而折半方式是我们自行选定的，不妨考虑将权值从小到大排序后分半，这样一来所有同时包含左右两侧的集合的最大值一定在右侧。

对左右两侧先做子集 DP，复杂度 \(O(3^{\frac{n}{2}})\)。然而存在一些同时包含左右两侧的集合难以处理。如果直接继续对整个 \(2^n\) 做子集 DP，记录左右两侧状态 \(L,R\)，每次转移到 \(L \subseteq L'\) 与 \(R \subseteq R'\)，复杂度依然是 \(O(3^n)\)。

但是我们之前是按权值排序后分半的，这启发我们对上述 DP 进行分布转移。进一步，我们不再进行 \((L,R) \rightarrow (L',R')\) 的转移，取而代之的是尝试 \((L,R) \rightarrow (L,R') \rightarrow (L',R')\)。在第一层转移时我们可以直接计算新方案的花费，第二层转移则限制子集和不超过 \(w\)。先将所有 \((L,R)\) 贡献给 \((L,R')\)，复杂度 \(O(2^{\frac{n}{2}}\times 3^{\frac{n}{2}})=O(6^{\frac{n}{2}})\)，所有这样的贡献都形如二元对 \((s_1,s_2)\)，\(s_1\) 表示方案花费，\(s_2\) 表示 \(R \rightarrow R'\) 的子集权值和。

进行 \((L,R') \rightarrow (L',R')\) 的转移，要求 \(s_2+c(L'-L) \leq w\)，最小化 \(s_1\)。按照 \(s_2\) 排序对应一段前缀。将方案按 \(s_2\) 排序对每个前缀预处理 \(s_1\) 最小值和个数即可。上一些手法可以将排序的 \(\log\) 干掉，复杂度 \(O(6^{\frac{n}{2}})\)。

33 CF868F

DP 形式形如 \(f_{i,j} = \min \limits_{k} \{f_{k-1,j-1}+w(k,i)\}\)。其中 \(w(l,r)\) 是区间相等对个数。

很难不注意到 \(w\) 满足四边形不等式，直接二分栈的复杂度取决于单次区间询问 \(w\)，如果可以在 \(T(n)\) 的复杂度内解决就可以在 \(O(T(n)\times nk\log n)\) 的复杂度内解决问题。

很遗憾区间询问 \(w\) 并不好做，目前只能做到 \(O(\sqrt n)\)，而 \(O(nk\sqrt n \log n)\) 显然无法接受。

在这个问题上，我们考虑对决策单调性结构做分治。对于目前分治区间 \([l,r]\)，决策区间 \([L,R]\)，取中点 \(mid = \lfloor \dfrac{l+r}{2} \rfloor\)，在决策区间每个位置 \(i\) 计算 \(w(i,mid)\)。此时我们引入一个新的概念，我们动态维护某个关键区间 \([l',r']\) 的 \(w(l',r')\)，每次查询一个区间的 \(w\) 时，按照莫队的扩展方式 \([l',r']\) 移动到询问区间。

我们声称这样做的复杂度就是 \(O(nk \log n)\)，考虑怎么证明这一点。显然我们的复杂度瓶颈仅在于计算 \(w(*,mid)\)，更具体地应该仅在于计算 \(w(L,mid)\)，因为所有其他的 \(i\) 进行的移动仅为 \([i,mid]\rightarrow [i+1,mid]\)。

假设最终决策点在 \(p\)，则递归到 \([l,mid),[L,p]\) 与 \((mid,r],[p,R]\)。首先有 \([*,mid] \rightarrow [L,m']\)，以及左侧某个区间转移到右侧。但不难发现所有区间端点总在 \([L,R]\) 内移动，且递归进两部分子树只需要关于 \(R-L+1\) 线性次更新。所以复杂度和直接分治是一样的，都是 \(O(n \log n)\)。故问题被我们做到了 \(O(nk \log n)\)。

34 LOJ3919

首先 \(w(l,r)\) 是子区间计数形式，自然满足四边形不等式，所以答案关于 \(k\) 有凸性，考虑 wqs 二分。

wqs 二分后，问题形式变为将序列划分若干区间，每划分一段有一个常数 \(c\) 的贡献，每一段还需要额外的 \(w(l,r)\) 的贡献，问划分方案的最小贡献。对其 DP，\(f_i\) 表示 \([1,i]\) 划分的答案，转移形如 \(f_i = \min \limits_{j} \{f_{j-1}+c+w(j,i)\}\)。这是一个在线的决策单调性结构，CDQ 分治，内层分治做莫队转移，复杂度 \(O(n \log^3 n)\)。

35 P10181

答案关于 \(k\) 上凸。对于 \(k \leq \sqrt n\)，直接做 \(f_{i,j}\) 的 DP，复杂度 \(O(n\sqrt n \log n)\)。

对于 \(k > \sqrt n\)，考虑此时凸函数斜率必定小于等于 \(\sqrt n\)，这是因为答案不超过 \(n\)。故对所有 \(\leq \sqrt n\) 的整数斜率做 wqs 二分里的切凸包形式即可计算答案。这部分的 DP 也是 \(O(n \sqrt n \log n)\)。

写的好没准就过了。这里的 \(\log\) 来源于 DP 时的线段树结构。据说可以上并查集做到 \(O(n \sqrt n \alpha(n))\)。

36 QOJ5013

好题啊。

显然划分出的段每段都可以取 \(\max(c_0,c_1)\)，且有一段可以取 LIS 即一段前缀 \(0\) 一段后缀 \(1\)。

基于此不难设计 \(O(n^3)\) 到 \(O(n^2)\) 的一些 DP 结构，然而都无法通过整个题。

继续观察性质。注意到当 \(m \geq 2\) 时，我们可将问题转化为，取 \(m+1\) 段，每段都取 \(\max(c_0,c_1)\)。显然新问题答案不小于原问题答案，此外我们要证明不大于。如果有相邻两段分别选了 \(0\) 和 \(1\) 则合并成原问题的一组解，否则形如 \(1\cdots 1 0\cdots 0\)，\(1\) 和 \(0\) 内部都可以合并得到一组 \(m=2\) 的解。

此外，我们考虑原序列的一个极长同色连续段，可以说明其在答案中必定也是连续一段。将同色连续段合并，每个段有一个长度，问题等价于选一个子序列，同色连续段数不超过 \(m+1\)，总长最大。把问题改为删去一些连续段，删两端会减 \(1\) 个同色连续段，删中间会减 \(2\) 个。有自然的限制是不能删相邻两个，一定不优。两端暴力枚举情况，中间的是经典反悔贪心。复杂度 \(O(n \log n)\)。

37 P5372

对网格图黑白染色，注意到空格一定是黑格，并且每个 \(1 \times 2\) 矩形都同时包含黑白两色。考虑进行图论建模。将每个黑点视作一个点。对于每个原矩形 \((x_1,y_1),(x_2,y_2)\)，不妨设 \((x_1,y_1)\) 是白，其目标是到达 \((x_1,y_1),(x_3,y_3)\)，则要求空格某个时刻从 \((x_3,y_3)\) 到达 \((x_2,y_2)\)。连边 \((x_3,y_3) \rightarrow (x_2,y_2)\)。这个图形态很特殊，问题在于其不一定连通。为此考虑对于 \((x_1,y_1),(x_2,y_2),(x_3,y_3)\)，若不连通，从中间拉出一个 \((x_4,y_4)\) 使得其与起点连通，中间加一个，仍然能跑欧拉路径。

38 CF600F

一般无向图的最小边染色为 \(d\) 或 \(d+1\)，其中 \(d=\max \limits_{i} \mathrm{deg}_i\)。

对于二分图，最小边染色必定为 \(d\)。构造方案是，依次加入所有边 \((u,v)\)，考虑 \(u\) 的最小没有出边颜色 \(c_u\) 和 \(v\) 的最小没有出边颜色 \(c_v\)。\(c_u = c_v\) 时直接染为 \(c_u\)，否则不妨令 \(c_u<c_v\)，给这条边染 \(c_u\)，给 \(v\) 的原 \(c_u\) 色邻边染 \(c_v\)，给对应的原 \(c_v\) 色邻边染 \(c_u\)，依次类推。由于没有奇环，调整也不会出现环。不难说明确实构造到了颜色数为 \(d\) 的染色方案。

39 P10062

考虑 \(C=n\)，此时前若干行都填满。对于每一列我们已经可以确定其剩下的颜色是哪些。建立二分图，左侧是 \(n\) 列，右侧是颜色，左侧每一列向能填的颜色连边。注意到无论左右，所有点的度数都是 \(n-R\)，对二分图进行边染色可以得到一组色数为 \(n-R\) 的染色，进而划分出 \(n-R\) 个完美匹配，每个完美匹配对应一行，则必然有解。

考虑 \(C<n\)，我们希望先把右上角剩下的 \(R \times (n-C)\) 的矩形填满，然后再考虑下面的。类似地，建立二分图，左侧是行，右侧是颜色，每行连向可以选的颜色。如果存在右侧某个颜色的度数大于 \(n-C\)，那么在这些列里一定填不完，必然无解。否则找一个 \(n-C\) 边染色就变为了 \(C=n\) 的问题。

总复杂度 \(O(n^3)\)。

40 P10107

查询答案时，我们希望把结构改为询问 \(x\) 和同深度的 DFS 序之前的所有点的贡献和，减去 \(x\) 在这层的前驱与之前的贡献。总而言之就是要能维护每个点对应同深度的 DFS 序在其之前的所有点贡献。

原问题是二进制结构考虑对其倍增。\(f_{u,i}\) 表示 \(u\) 的 \(2^i\) 层的上述对应答案。\(i \rightarrow i+1\) 本质上是对 \(u\) 向下走 \(2^i\) 步到达的点对应的区域所有点权异或 \(2^i\)。那么记 \(g_{u,i}\) 表示 \(u\) 与同层 DFS 序列靠前所有点子树对应的子树内的，点权第 \(i\) 位为 \(1\) 的点的个数即可。查询同理。复杂度 \(O((n+q)\log n)\)。

41 AGC030F

从小往大插入延迟钦定一下就做完了。复杂度 \(O(n^3)\)。

42 联考模拟赛 T1

将 L 形看作左右和上下分别二选一。对每个关键点，左右两个点连一条边，上下两个点连一条边。问题变为给每条边确定一个方向，使得每个点入度不超过 \(1\)。

有解当且仅当每个连通块是树或基环树，方案数不难计算。

43 联考模拟赛 T2

等会。

44 联考模拟赛 T3

需要一个名为毛毛虫剖分的科技。

只考虑后两种操作，树剖可以轻松解决。因为 \(qk\) 不大，所以希望复杂度和 \(O(qk)\) 有关。一种刻画小邻域的方式是枚举 \(u\) 和 \(v\) 的 LCA，也就是从 \(u\) 向上跳 \(k\) 步，可以转化为 \(O(k)\) 次操作某个点子树内深度等于某定值的所有点。这个问题很容易使用 BFS 序解决，但 BFS 序无法解决链和子树操作。

这启发我们结合两种方式，尝试考虑一种新的对点标号的方式使得其可以处理子树，链和小邻域修改。这就是毛毛虫剖分要解决的大致问题。

记邻域最大范围为 \(K\)。初始有一个空序列，加入一个点指的是将其加入序列末尾，即令其标号为目前序列长度加 \(1\)。毛毛虫剖分对点的标号构造过程如下：

1. 对树进行重链剖分。从根开始 DFS，每次到达一条重链顶端时，加入这条重链从上往下第 \(K+1\) 个点与之后的所有点。然后先递归进入重儿子后递归进入其他所有轻儿子。

2. 考虑每个点 \(u\) 存在集合 \(S_u\) 初始为空。按照 BFS 序对每个没有加入序列的点 \(v\)，令 \(z\) 为 \(v\) 的 \(K\) 级祖先，若不存在令 \(z\) 为根，将 \(v\) 加入集合 \(S_z\)。过程结束后，对于每个点 \(u\)，将 \(S_u\) 内的点按深度从小到大排序。

3. 进行第二次 DFS。从根开始，每遇到一个点 \(u\)，依次加入 \(S_u\) 内的所有点。然后先递归进重儿子后递归进轻儿子。

至此我们得到了这棵树的毛毛虫剖分标号。依次尝试刻画小邻域，子树，链。

小邻域：转化为 \(O(K)\) 个对于 \(x\) 子树距离 \(x\) 恰好为 \(d\) 的所有点的整体操作。其中有 \(d \leq K\)。注意到这些点中最多只有一个点是第一次加入重链 \(K+1\) 或之后的，而其他点必定都是后面给其 \(K\) 级祖先的，所以可以转化为 \(O(1)\) 个毛毛虫剖分上的连续区间。问题转化为 \(O(K)\) 次区间操作。

子树：对于点 \(u\) 子树，注意到在步骤三中加入的其子树内距其其至少为 \(K+1\) 的所有点构成连续区间，而在步骤一中加入的这样的点显然也构成一个区间。对于距离其不超过 \(K\) 的点仿照小邻域的做法。问题转化为 \(O(K)\) 次区间操作。

链：类似一般重链剖分，每条重链最多 \(O(K)\) 个点暴力修改，其他点构成连续区间。问题转化为 \(O(K \log n)\) 次区间操作。

使用线段树维护，本题即可做到 \(O(qK\log^2 n)\)。

45 AGC023E

先考虑如何计算排列 \(p\) 的个数。假设 \(a_1 \leq a_2 \leq \cdots \leq a_n\)。依次考虑每个 \(i\) 上能填什么数。显然有 \(\max(0,a_i-i+1)\) 种。所以答案应该是 \(\prod \limits_{i=1}^n \max(0,a_i-i+1)\)。

对原问题，先考虑一个 \(O(\mathrm{poly}(n))\) 的算法。只需要枚举 \(i,j\) 不难计算 \(i<j\) 且 \(p_i>p_j\) 的方案数。然后对这个式子做一个数据结构优化状物即可。

46 AGC036F

容易计算得到 \(p_i\) 的范围 \(l_i=\lceil \sqrt{n^2-i^2}\rceil\)，\(r_i=\lfloor \sqrt{4n^2-i^2}\rfloor\)。

随着 \(i\) 增大，\(l_i\) 与 \(r_i\) 均单调不增。注意到 \(i\geq n\) 时有 \(l_i=0\)，并且如果所有 \(l\) 均为 \(0\) 那么答案显然是排序后 \(\prod (r_i-i)\)，故我们希望对 \(i < n\) 的 \(i\) 做容斥，钦定 \(k\) 个 \(p_i < l_i\)，贡献系数 \((-1)^k\)。

对于固定的 \(k\) 考虑怎么求答案。\(i \geq n\) 的 \(p_i\) 上界是确定的，只能等于 \(r_i\)。而 \(i<n\) 的 \(p_i\) 上界可能为 \(l_i-1\) 或 \(r_i\)，取决于是否被钦定。但是注意到 \(i<n\) 时有 \(r_i \geq \lfloor \sqrt{3}n\rfloor \geq n\)，所以考虑对 \(i<n\) 的 \(i\) 令其权值为 \(l_i-1\)，\(i\geq n\) 的 \(i\) 权值为 \(r_i\)，将所有 \(i\) 按权值升序排序，权值相同按下标降序排序，尝试观察问题是否可以被刻画。

直接尝试从前往后 DP。\(f_{i,j}\) 表示 \([0,i]\) 钦定了 \(j\) 个的方案数，转移先对 \(i \geq n\) 是否成立分类讨论，进一步分类讨论 \(i\) 是否被钦定。推一下可以发现每一步都可以算出贡献。复杂度 \(O(n^3)\)。

47 联考模拟赛 T1

注意到 \(\varphi(\mathrm{lcm}(i,j))=\dfrac{\varphi(i)\varphi(j)}{\varphi(\gcd(i,j))}\)。然后枚举下面的 \(\gcd\) 做莫反即可。复杂度 \(O(n \log n)\)，足以通过。

48 联考模拟赛 T2

令 \(\sum a_i = S\)，则最大子段和 \(\geq S\)，接下来我们证明可以取到 \(S\)。直接的构造是在最前面加一个 \(S\)，然后每个 \(i\) 左边加一个 \(-a_i\)。

那么显然一个 \(b\) 合法当且仅当所有前缀和值在 \([0,S]\) 之间。注意到问题等价于在序列相邻两个之间插入至多一个，所以长度不超过 \(2n+1\)。先考虑关于值域的做法。\(f_{i,j}\) 表示 \([1,i]\) 中，最后前缀和为 \(j\) 的最小长度，同理记录方案数。转移先在末尾加入 \(a_{i+1}\)，相当于整体平移然后截取 \([0,S]\) 部分。然后在末尾加入任意一个数，形如 \(f'_{i,j} \gets \min \limits_{k} f_{i,k}+1\)。所以 \(f_{i,j}\) 的所有 DP 值只有至多两个本质不同结果，然后不难通过维护 DP 连续段或之类的方式做到 \(O(n)\)。

49 CF2061I

\(O(n^2)\) 的 DP 很显然，大概是 \(f_{i,j}\) 表示前 \(i\) 轮赢了 \(j\) 次的最小花费。注意到转移的复杂之处是二类时需要判断 \(j\geq i-j\) 是否成立。

考虑快速进行若干次转移。比如从 \(f_{l,*}\) 快速转移到 \(f_{r,*}\)。可以注意到如果 \(j-(l-j)\) 的绝对值足够大，具体来说大于 \(r-l\) 时，\((l,r]\) 区间内所有二类比赛的胜者唯一确定。

由于限制和区间长度有关，考虑分治。对于目前分治区间 \([l,r]\)，我们希望将 \(f_{l,*}\) 所有剩余决策全部转移给 \(r\)。先将 \(|j-(l-j)|>r-l\) 的直接转移，然后对于剩余部分考虑分别递归进 \([l,mid]\) 和 \((mid,r]\)。将 \(|j-(l-j)|>r-l\) 的直接转移需要一个一侧凸的 \((\min,+)\) 卷积状物，分治计算，总复杂度 \(O(n \log^2 n)\)。

50 P11695

将左闭右开区间改为左闭右闭区间，问题即判定区间内所有区间的并是否能覆盖所有位置。

考虑离线做猫树分治。对于分治区间 \([l,r]\) 和中点 \(mid\)，考虑所有横跨 \(mid\) 的询问区间。将每个插入删除的区间写成存活时间段的形式，即 \([l,r,tl,tr]\)，表示对应区间和对应存活时间段。每个询问也将其时间记下来。

对于询问 \([l',r',t]\)，其中 \(l' \leq mid < r'\)，考虑将贡献的区间也根据是否横跨 \(mid\) 分类讨论。

如果横跨 \(mid\)，以左侧为例，我们只关心左端点的最小值。也就是要求 \(L \in [l',mid]\)，\(R \in (mid, r']\)，\(t \in [tl,tr]\)。按照时间扫描线维护线段树即可。

如果不横跨 \(mid\)，按照序列维从左往右扫描线维护线段树即可。复杂度 \(O(m \log^2 n)\)。

51 联考模拟赛 T1

考虑记 \(f_{S,0/1}\) 表示剩下集合 \(S\)，现在到谁，最终答案。

直接转移会成环。不难猜到双方的策略是，对于先手，每次随机若最大值大于等于某定值 \(x\) 则取否则不取，对于后手则是最小值。对于 \(f_{S,0}\)，即现在到了原先手操作，枚举 \(x\)，我们假设后手已经知道 \(x\)，可以任意取 \(y\)。枚举所有 \(y\)，先手成功率 \(p\)，后手成功率 \(q\)，依次执行，先手成功的概率为 \(p(\sum \limits_{k \geq 0} (1-p)^k(1-q)^k) = p(-\dfrac{1}{(1-p)(1-q)-1})\)。直接计算然后转移即可。复杂度 \(O(2^nn^2)\)。

52 联考模拟赛 T2

\(x,y\) 独立。问题等价于若干区间，每个区间可以选其或其补集，最大化所有选择的交。暴力是枚举一个位置在交内，这样每个区间选择唯一确定。对着这个东西扫描线即可。复杂度 \(O(n \log n)\)。

53 AGC006D

二分答案将问题转为 \(01\) 序列。

不难说明只需要找到离中间最近的相邻相同的即为答案。

54 AGC007E

即找一个 DFS 序使得相邻叶子间距离最大值最小。

二分答案 \(m\)，考虑一个暴力 DP。每个 \(u\) 子树内存若干对 \((a,b)\)，表示存在一种方式从 \(u\) 开始 DFS 使得第一个叶子距其为 \(a\)，最后一个叶子距其为 \(b\)。转移考虑所有 \((a,b),(c,d)\) 使得 \(c+d+w_l+w_r \leq m\)，加入新的二元组 \((a,d)\)。

显然只需要保留 \(a\) 单调递增 \(b\) 单调递减的所有二元组。类似启发式合并容易分析得到状态数 \(O(n\log n)\)，总复杂度 \(O(n \log n \log V)\)。

55 CF2155F

对每种颜色拉出来构成若干连通块，询问 \((x,y)\) 即询问有多少连通块同时包含 \(x,y\)。

如果有 \(c\) 个连通块，我们可以对于每个点开个 bitset 记录包含其的所有连通块，查询复杂度 \(O(\dfrac{qc}{w})\)。

所以考虑对连通块根号分治。取阈值 \(B\)。大小大于等于 \(B\) 的连通块不超过 \(\dfrac{s}{B}\) 个，使用上述做法复杂度为 \(O(\dfrac{qs}{Bw})\)。大小为 \(w<B\) 的连通块每个连通块 \(O(w^2)\) 做，复杂度不超过 \(O(B\sum w)=O(Bs)\)。

综上得到了 \(O(\dfrac{qs}{Bw}+Bs)\) 的算法。取 \(B=\sqrt{\dfrac{q}{w}}\) 得总复杂度 \(O(s\sqrt{\dfrac{q}{w}})\)。

56 CF2156E

二分答案 \(x\)，判断先手是否存在策略使得结果小于等于 \(x\)。

考虑对于二元组 \(i<j\)，若 \(b_j-b_i > x\)，则连一条无向边 \((i,j)\)，问题变为在无向图上先手删点后手选点，后手胜利当且仅当某条边两端都被后手选了。注意到如果有至少两个点度数大于等于 \(3\)，那么先手无论如何都必败，其他的都是小情况，分类讨论或者搜一下就行。

57 P8145

考虑记 \(f_{i,j}\) 表示从点 \(i\) 出发走 \(j\) 步的方案数，然后按照字典序贪心选取。注意到 \(f_{i,j} \geq k\) 时其具体取值没有意义，并且由于每次有两个方向所以 \(j \geq 2\log_2 k\) 时必有 \(f_{i,j} \geq k\)，不需要算答案。更进一步，若 \(i > j\) 且 \(i+j \leq n\)，那么 \(f_{i,j} = 2^j\)。最终只有 \(O(\log^2 k)\) 个有效状态。复杂度 \(O(n + \log^2 k)\)。

58 P11111

令所有点权都取 \(l_i\) 得到最大权独立集 \(L\)，都取 \(r_i\) 得到最大权独立集 \(R\)。则存在最大权独立集为 \(x\) 的必要条件是 \(x \in [L,R]\)，事实上这也是充分条件。原因是考虑从 \((l_1,l_2,\cdots,l_n)\) 每次选取一个点权加 \(1\) 最终得到 \((r_1,r_2,\cdots,r_n)\) 的过程中，每一步最大权独立集最多增加 \(1\)，故其必能连续取到 \([L,R]\) 之间每个数。

进一步考虑怎么构造解。将询问离线从小到大考虑。根据上述证明我们知道可以以任意顺序执行每次选一个点权加 \(1\) 从而获得所有答案，一个想法是依次考虑每个点，二分出至少需要加多少才能得到目前询问的答案。需要支持单点修改全局最大权独立集，使用静态 Top Tree 可以 \(O(\log n)\) 解决单点修改，总复杂度 \(O(n \log^2 n)\)。进一步，考虑对这个点增加的过程，存在一个分界线 \(B\)，使得增加到 \(B\) 后这个点在最大权独立集内，之后每次增加都会导致最大权独立集增加 \(1\)。而之前则不变。\(B\) 的值只需要求强制选这个点时的最大权独立集，也就是把邻点的点权设为 \(-\infty\) 求最大权独立集。套用静态 Top Tree 可以直接在 \(O(n \log n)\) 的复杂度内解决之。

不过这个做法有点无脑。注意到其实可以以任意顺序增加每个点的权值，按照 DFS 序做可以直接维护换根状物。复杂度 \(O(cn + q\log n)\)。

59 P10656

注意到一个平凡解为只选第一个或第二个序列。设其答案为 \(s\)，则第一个序列和与第二个序列和至少有一个超过 \(\dfrac{s}{2}\)，不妨设是第一个。找到最小的前缀使得前缀和超过 \(\dfrac{s}{2}\)，设位置为 \(x\)，则必有 \(x \in [l_1,r_1]\)，证明显然。

当确定了第一个序列的任何一个必须选的位置后，对于第二个序列的每个 \(b_i\)，限制是若选了 \(i\) 则不能选 \(a_j=b_i\) 的 \(j\)，根据 \(j\) 关于 \(x\) 的大小关系可以把限制变为仅关于 \(l_1\) 或 \(r_1\) 的一元限制，如此一来只需要对 \(b\) 序列维扫描线维护单调栈与线段树即可。复杂度 \(O(n \log n)\)。

60 P11694

不妨假设 \(a_1<a_2<a_3<\cdots<a_n\)，显然存在一个解使得答案不超过 \(a_2\)，直接令 \(a_2\) 为 LCM 集合，其余都为 \(\gcd\)，则 \(\mathrm{lcm}\) 恰为 \(a_2\) 而 \(\gcd\) 不超过 \(a_1\)。故答案不超过 \(a_2\)。

进一步考虑分析性质。我们声称不存在 \(i<j<k\) 使得选的是 GLL，否则 \(\mathrm{lcm} \geq 2a_j\) 而 \(\gcd \leq a_i\)，答案必定大于 \(a_j\)，与答案不超过 \(a_2\) 不符。

故我们知道最优解形态必定形如以下两种：

1. L……LG……G。
2. L……LG……GLG……G。

第一类枚举前缀直接算，复杂度 \(O(n + \log V)\)。

第二类还有些说法，即 L 选一个前缀与之后的一个单点。

假设选的前缀为 \([1,i]\)，之后的单点为 \(j > i + 1\)。首先要求 \(\mathrm{lcm}(a_1,a_2,\cdots,a_i)\mid a_j\)，否则 \(\mathrm{lcm} \geq 2a_j\) 必然不是最优的。

对于一个 \(j\)，必定选取最大的这样的 \(i\) 使得上述条件成立。所以有用的 \(i\) 只有 \(O(\log V)\) 个。

进一步我们声称不存在 \(1<i<j<k\) 使得分配的为 GGL，否则结果至少为 \(a_k - \gcd(a_i,a_j)\)。\(x<y\) 时有 \(\gcd(x,y) \leq y - x\)，所以结果至少为 \(a_k - (a_j-a_i) = a_k-a_j+a_i \geq a_i \geq a_2\)，故只有可能 \(i=1\)。\(i=1\) 时相当于只选一个单点，这是简单的。另一方面，若确实不存在 GGL，只有每个前缀选之后第二个点才有可能是对的。这样只需要对 \(O(\log V)\) 个前缀算一下就行。复杂度 \(O(n + \log^2 V)\)。

61 P12704

考虑点 \(a\) 出发到不了 \(b\) 的原因是什么。必然存在一个矩形包含 \(b\) 使得外部无法进去内部。这个是矩形的原因是考虑若不是则必然有一个位置有相邻两个方向在矩形内，这样就倒闭了。

将原图边反向对于每个点 \(b\) 求出这个矩形。直接 Tarjan 缩点后跑个拓扑序就容易求出这个矩形。复杂度 \(O(nm+q)\)。

62 CF771E

直接 DP 是 \(f{i,j}\) 表示第一行前缀 \([1,i]\) 第二行前缀 \([1,j]\) 对应的答案。转移考虑跳过这个位置或者第一行选一个区间或者第二行选一个区间，或者 \(i=j\) 时可以选择一个宽为 \(2\) 的矩形。复杂度 \(O(n^2)\)。

进一步考虑优化转移过程。考虑按照顺序选取矩形。对于目前状态 \((i,j)\)，不妨考虑 \(i<j\)，我们的决策是选取第一行的下一个矩形，或者不选转移到 \((j,j)\)。注意到第二类得到的总是形如 \((j,j)\) 的转移，而第一类转移唯一确定。考虑 \((i,i)\) 向后转移，有选取第一行的一个矩形，第二行的一个矩形，或者选取一个宽为 \(2\) 的矩形，或者跳过转移到 \((i+1,i+1)\)。注意到所有状态都形如从 \((i,i)\) 出去然后其余的转移都是唯一的或者转移到另一个 \((j,j)\)，所以总状态数是线性的。精细实现总复杂度也为线性。

63 联考模拟赛 T1

根据期望线性性，枚举每一轮计算这一轮猜对的概率求和即为答案。

第 \(i\) 轮若每种颜色剩下的个数最大值为 \(c\)，则正确率为 \(\dfrac{c}{nk-(i-1)}\)。

注意到 \(\dfrac{c}{nk-(i-1)} = \sum \limits_{j=1}^c \dfrac{1}{nk-(i-1)}\)，将问题转化为枚举 \(j\) 后计算剩余最大值大于等于 \(j\) 的概率，乘以 \(\dfrac{1}{nk-(i-1)}\) 求和即为答案。

对于固定的 \(j\)，需要计算存在某种颜色剩余大于等于 \(j\) 的概率，其补集是每种颜色剩余严格小于 \(j\)，也就是被删去了至少 \(n-j+1\) 个数。

对所有球标号 \(1\) 到 \(nk\)，问题转化为求有多少长度为 \(i-1\) 的序列，每个数在 \([1,nk]\) 之间且最多出现一次，每种颜色的出现次数至少为 \(n-j+1\)。

直接对其 DP。\(f_{a,b}\) 表示长度为 \(a\) 的序列有 \(b\) 种不同颜色且每种都合法的方案数。考察序列末尾的数，要么是前 \(a-1\) 个某种颜色，从 \(f_{a-1,b} \times (bn-a+1)\) 转移。要么之前出现次数恰为 \(n-j\)，从 \(\dbinom{a-1}{n-j}\dbinom{n}{n-j+1}(n-j+1)!f_{a-1-(n-j),b-1}\)。总复杂度 \(O(n^2k^2)\)，比标算少一个 \(k\)。

64 联考模拟赛 T2

据说有解必定满足图有割边且唯一完美匹配必定包含至少一条割边，证明我还不会。

所以考虑递归地做，每次考虑图上的某条割边，若删去后两边连通块大小均为奇数则其一定处于唯一完美匹配内，将其删除后递归进两部分。复杂度 \(O(n^3)\)。

进一步，复杂度瓶颈在于每次跑 \(O(m)\) 的 Tarjan。因为 \(m=O(n^2)\) 所以完全过不去。考虑先求出一棵 DFS 生成树，这不难使用 bitset 在 \(O(\dfrac{n^2}{w})\) 的复杂度内求出。求出 DFS 生成树后，割边一定是树边，充要条件是不存在非树边跨过其。考虑利用切边等价结构中的异或哈希，对于每条边随机赋权，每个点的权值为邻边异或，一条树边是割边基本等价于较深的点子树内点权异或等于这条树边的边权。删边时可以直接维护所有点的点权，总复杂度 \(O(\dfrac{n^3}{w})\)。

65 联考模拟赛 T3

好题。

考虑策略是怎么样的。从 \(i\) 开始任意时刻扩展到的都是一个区间 \([l,r]\)，每次能直接扩展至两侧肯定直接扩展，而无法扩展时会从两侧选一个但具体是哪一个不一定确定。

考虑对区间分类：

1. 称所有 \(\sum \limits_{i=l}^r a_i \leq k\) 的区间为小鱼区间。
2. 称所有 \(\sum \limits_{i=l}^r a_i > k\) 的区间为大鱼区间。
3. 称所有无法仅通过一类吃法向左右进行任何扩展的区间为自闭区间。

尝试观察区间的性质。小鱼区间一定是自闭区间，其不可能使用一类操作向左或向右吃鱼，这是因为其和不超过 \(k\) 一定无法吃掉任何鱼。

大鱼区间如果是自闭区间，那么使用二类操作必然选择相邻两侧体型较大的鱼，吃掉后可以立即吃掉另一侧体型较小的鱼，这是因为本来区间和就大于 \(k\)，操作后吃掉了较大的，那么一定不小于较小的 \(+k\)。

观察从点 \(i\) 出发的整个流程，不失一般性假设开始区间 \([i,i]\) 是小鱼区间，那么过程是每次进行操作二直至到达某个极短大鱼区间 \([l,r]\)，然后到达包含其的某个大鱼自闭区间 \([L,R]\)，通过一次二类操作变为 \([L-1,R+1]\)，然后继续跳到包含其的大鱼自闭区间，然后进行操作二，不断重复上述过程直至得到 \([1,n]\)。

对于第一次跳到的某个极短大鱼区间 \([l,r]\)，答案为 \(f(l,r)+r-l\)，\(f(l,r)\) 是这个极短大鱼区间到达 \([1,n]\) 的最小次数，\(r-l\) 是从 \([i,i]\) 不断进行操作二到达 \([l,r]\) 花费的次数。

注意到极短大鱼区间只有 \(O(n)\) 个，按照右端点双指针即可在线性复杂度内求出所有极短大鱼区间。这些区间满足 \(l,r\) 分别单调递增。只需要能求出所有极短大鱼区间的 \(f(l,r)\)，从前往后扫描线即可求出每个点 \(i\) 的答案。现在问题转化为求这 \(O(n)\) 个 \(f(l,r)\)。

注意到在之后的跳跃过程中，我们真正关心的决策位置应该是所有大鱼自闭区间。对于这样的区间 \([l,r]\)，其需要从包含 \([l-1,r+1]\) 的另外一个大鱼自闭区间转移。

我们首先说明，大鱼自闭区间的个数是 \(O(n)\) 的。对于每个大鱼自闭区间 \([l,r]\)，将这个区间挂到 \(a_{l-1}\) 和 \(a_{r+1}\) 中较小的那个点，则每个点的一侧只会被挂一个区间，因为如果挂了多个区间显然较大的一定不是自闭区间。

另外我们说明，任意两个大鱼自闭区间若交非空，则交区间一定是小鱼区间。考虑将交部分和交左右两侧两个点拉出来，将两个区间都为大鱼区间的限制列为不等式即可推出中间必定为小鱼区间。进一步，对于每个大鱼区间，包含其的所有大鱼自闭区间两两包含。

我们希望解决两个问题：

1. 找到所有大鱼自闭区间。
2. 对于 \(O(n)\) 个大鱼区间找到包含其的最短大鱼自闭区间。

解决问题二后不难递推出所有大鱼自闭区间的答案，同时将所有极短大鱼区间 \([l,r]\) 加入询问就可以直接求出所有 \(f(l,r)\)，从而解决整个问题。

先考虑问题一，如何找到所有大鱼自闭区间。根据上述对大鱼区间数量线性的证明，考虑对于每个点求出挂在其上的至多两个大鱼自闭区间。不妨以求出其左侧挂的区间为例，右侧同理。即对于每个 \(i\)，尝试找出大鱼自闭区间 \([l,i-1]\) 使得 \(a_i \leq a_{l-1}\)，这样的 \(l\) 至多只有一个。

对序列维从左到右扫描线，扫到 \(i\) 时显然可以双指针出右端点为 \(i-1\) 的极短大鱼区间 \([x,i-1]\)，则显然有 \(l \leq x\)。考虑 \([1,x]\) 内所有位置是否可能成为 \(l-1\)，即大鱼自闭区间的右侧相邻点。这样的位置一定是 \([1,x-1]\) 的权值后缀最大值，否则右侧存在一个权值比其大必定可以扩展到。维护这样的一个单调栈，那么唯一可能成为 \(l-1\) 的位置就是单调栈第一个权值大于等于 \(a_i\) 的位置，因为如果还在之前那么权值和已经足够扩展到 \(i\) 了。直接在单调栈上二分可以做到 \(O(n \log n)\)，但实际上所有小于 \(a_i\) 的单调栈上的元素之后就不可能成为之后的 \(l-1\) 了，因为之后区间若包含 \(i\) 权值和已经足够大了。这样的话把单调栈里小于 \(a_i\) 的都直接弹出就是对的。这一部分复杂度 \(O(n)\)。

接下来考虑问题二，需要对 \(O(n)\) 个大鱼区间找到包含其的最短大鱼自闭区间。还是考虑对序列维左到右扫描线，对于每个询问区间 \([l,r]\) 在 \(l\) 处尝试统计答案，对于每个大鱼自闭区间在左端点加入右端点删除。扫到 \(l\) 时只需要考虑所有左端点小于等于 \(l\) 的大鱼自闭区间中右端点大于等于 \(r\) 的右端点最小的区间，容易做到 \(O(n \log n)\)。进一步，求右端点最小等价于左端点最大，而可能有若干左端点大的区间的右端点 \(<r\)，我们声称维护这样的单调栈，直接把右端点 \(<r\) 的弹出就行。因为这样的区间一定不会成为之后的询问区间的答案，否则这样的区间与目前询问区间 \([l,r]\) 会同时包含对应的询问区间，与上述结论矛盾。如此一来这个问题也在线性复杂度内得以解决。

综上，整个题在 \(O(n)\) 的复杂度内得以解决。

66 联考模拟赛 T1

注意到点 \(x\) 到路径 \(y,z\) 的距离为 \(\dfrac{d(x,y)+d(x,z)-d(y,z)}{2}\)，然后用脚做。

我注意不到怎么办？将询问差分成前缀相减，对集合序列维扫描线，建出虚树后分类讨论 \(x\) 距离路径上最近的点在哪里即可。很难写。

67 联考模拟赛 T2

68 P11648

从下向上合并维护一些信息，需要维护子树内每个点到目前的根包含的所有颜色构成的集合，需要查询 \(\sum \limits_{p\in S,q\in T} v_{p\cup q}\)，以及支持合并两个儿子集合。

设阈值 \(B\)，合并子树时分类讨论：

1. 两个集合大小均不超过 \(B\)。\(O(sz_1sz_2)\) 暴力合并。
2. 两个集合大小均超过 \(B\)。\(O(k2^k)\) 做 FWT。
3. 集合大小分别小于等于 \(B\) 与大于 \(B\)。做法有待商确。

一类的复杂度是 \(O(nB)\) 的，二类是 \(O(\dfrac{n}{B}k2^k)\)，对于第三类，所有对应的大子树是没有交的，所以只会有 \(O(\dfrac{n}{B})\) 次。我们希望能做到单次 \(O(k2^k)\)。

第三类问题等价于，给定 \(a_0,a_1,\cdots,a_{2^k-1}\) 与 \(b_0,b_1,\cdots,b_{2^k-1}\)，对于每个 \(S\) 试求 \(f_S = \sum \limits_{T} a_Tb_{S \cup T}\)。

考虑这个转化后的问题怎么做。

\(f_S = \sum \limits_{T} a_Tb_{S \cup T} = \sum \limits_{S \subseteq T} b_T \sum \limits_{p} [p \cup S = T] a_p\)。

进一步对其容斥，等于 \(\sum \limits_{S \subseteq T} b_T \sum \limits_{p \subseteq T} a_p \sum \limits_{p \cup S \subseteq I \subseteq T} (-1)^{|T|-|I|}\)。

先枚举 \(I\)，等于 \(\sum \limits_{S \subseteq I} (-1)^{|I|} \sum \limits_{P \subseteq I} a_p \sum \limits_{I \subseteq T} b_T(-1)^{|T|}\)。

至此容易做到 \(O(k2^k)\) 预处理。总复杂度 \(O(nB+\dfrac{n}{B}k2^k)\)，取 \(B=\sqrt{k2^k}\) 可得复杂度 \(O(n\sqrt{k2^k})\)。

69 联考模拟赛 T1

如果没有区间覆盖显然所有行之间不独立，直接对于每一列将所有行的数求和就变成了区间加区间 \(\max\) 问题，这容易使用线段树在 \(O(q \log n)\) 的复杂度内解决。

对于区间覆盖，考虑对每行进行颜色段均摊，初始时每一行只有一个颜色段，每次区间加最多增加两个颜色段，区间覆盖时暴力枚举区间内的所有颜色段并删除即可。对每一行使用动态开点线段树可以在 \(O(n+q\log n)\) 的复杂度内解决原问题。

std 怎么是 \(O(2^kn\log n)\) 的，这也太菜了。

70 联考模拟赛 T2

aka [ICPC 2025 Yokohama R] Minimizing Wildlife Damage。

模拟赛题几天前在杂题选讲中出现，太搞笑了。

显然最终一个前缀全是 \(0\)，枚举这个前缀，为了最小化删除所需轮数这个前缀应该选最大权独立集。

对于每组询问，合法的前缀个数只有 \(O(1)\) 个，然后在前缀后面的部分会选择一个单点删除，贡献是李超树结构，总复杂度 \(O(n \log n)\)。

71 联考模拟赛 T3

aka [AGC052F] Tree Vertices XOR。

72 P14719

对于固定的长度 \(i\)，不难通过哈希在 \(O(n)\) 的复杂度内求出最多覆盖多少个段。

记 \(f_i\) 表示上述答案。

注意到 \(f_i \leq \dfrac{n}{i}\)，我们希望求 \(\max \limits_{i=1}^k i \times f_i\)。

显然 \(f_i\) 单调不增。套用 Determine A Non-Increasing Integer Sequence of Length n with a[k]<=n/k in O(sqrt(n)) Steps 的方法，既直接整体二分，每次递归到的区间如果左右端点答案一样则直接确定区间内所有答案，否则求出中点答案向两侧递归。可以说明总复杂度是 \(O(n \sqrt n)\)。

73 QOJ4788

直接做过程很复杂，还可能有连通块互相包含镶嵌之类的神秘结构。考虑一些相对形式化的刻画方式。

为了方便在地面下方加一行。对于每个格子，其只会影响其上方的对应一个格子。连边 \(i \rightarrow j\)，权值为 \(d\)，表示连通块 \(j\) 的结束时间不超过连通块 \(i\) 的加 \(d\)，对此跑最短路，复杂度 \(O(n^2 \log n)\)。

注意到 \(d\) 其实是两点间距离。所以可以对整个网格每个点在图上看做一个点，就可以跑 01-BFS 了，总复杂度 \(O(n^2)\)。

74 QOJ833

考虑两条路径，一条能向下就向下否则向右，另一条能向右就向右否则向下。然后枚举一个点对另一个点分类讨论一下即可。复杂度 \(O(nm)\)。