2025.5 神秘记录 最后更新于 2025-05-02 17:34:35

### 277 T318504（直径合并） > 给定 $n$ 个点的树，$q$ 次询问求区间中选 $k$ 个点构成的虚树，使得虚树的边权和最大。$n\leq 3\times 10^5,q\leq 10^4,k\leq 100$。 两个大小 $\mathcal O(k)$ 的虚树合并复杂度是 $\mathcal O(k)$ 的，按 dfs 序进行归并即可，合并完了之后我们得到一个大小 $\mathcal O(k)$ 的虚树，要求出保留 $1\sim k$ 个点对应的最大子虚树。 对于 $k=2$ 时，最大子虚树为原虚树的直径。对于 $k$ 个点的情况，最大子虚树为 $k-1$ 个点的最大子虚树，也就是说将已有的边缩在一起，然后再加上到这条路径的 $\max$ 对应的点，虚树有个结论是前 $k$ 小的子虚树可以递推出来，对于 $\mathcal O(k)$ 个点的虚树，求出 $1\sim k$ 个点的最大子虚树，时间复杂度是 $\mathcal O(k)$。 对序列按 $B$ 大小分块，块之间用二区间合并的分治，即 $\mathcal O(n\log n)-\mathcal O(1)$ 的区间分治信息维护算法。 每次询问的时候整块的 $k$ 个点的最大边权和虚树是可以 $\mathcal O(B)$ 得到的。然后加入零散部分的点，加入完之后虚树大小还是 $\mathcal O(B)$ 的，继续可以 $\mathcal O(B)$ 时间复杂度算出答案。 序列部分的预处理复杂度是 $\mathcal O(\frac{n}{B}\log\frac{n}{B}B)=\mathcal O(n\log n)$，因为有 $\frac{n}{B}$ 个块，每次合并复杂度是 $\mathcal O(B)$。时间复杂度 $\mathcal O(n\log n+qB)$，在阈值上只要求 $B\ge k_{\max}=100$。 ### 278 qoj6760（搜索，剪枝，合并变分裂） 考虑建立一棵决策树，令 $w$ 为重量，$c$ 为磨损值，合并的规则为 $w_u=w_{ls}+w_{rs},c_u=2\max(c_{ls},c_{rs})+1$。首先计算合并过程中 $c$ 的贡献，因为这是确定的，并且只与子树 height 有关，即 $c_u=2^{h_u}-1$。其次考虑 $u$ 在 $w$ 的贡献是 $\min(w_{ls},w_{rs})$，显然你可以钦定一个儿子产生贡献。从另一个角度，你发现树高与 $w$ 的总贡献是此消彼长的。我们直接声称，存在一个最优解使得任意 $u$，$h_u$ 的来源与 $\max(w_{ls},w_{rs})$ 相同，即长链剖分与轻重链剖分的形态完全一致，否则可以调整变得不劣。此时确定长链剖分后，求出每个叶子节点从根下来作为轻边的次数 $coef_u$，我们希望填入 $w$ 最小化 $\sum coef_iw_i$，按照 $coef$ 从小到大排序后，再按照 $w$ 从大到小排序填入即可。这样我们需要求出所有可能的 $\{coef\}$ 序列，这个题 $n$ 很小，考虑直接搜索所有有效状态。在特殊性质构造完全二叉树的提示下，我们发现答案的上界大约是 $L=4\times 10^{11}$。 因此有一个大胆的设计：$f_{n,k,S}$ 表示 $n$ 个叶子的决策树，$coef$ 序列从小到大排序后形成的是序列 $S$，子树高度为 $k$ 时 $\sum 2^{h_v}-1$ 贡献的最小值，$f>L$ 时是无用的。找到这些状态中无用的状态并删除，满足 $coef$ 被全面偏序，$k,f$ 被偏序那么就是无用的。另一方面，你需要从 $i,n-i$ 的所有状态做归并合并，还要枚举 $k_1,k_2$，这非常劣（其实已经有 $65\sim 80$ 分了）。我们希望去掉 $k$ 的记录，考虑自上往下分裂，从一个根还是拓展，每次将一个叶子节点 split。分裂顺序就是考虑所有 $h=k$，其中 $k=n,n-1,\cdots,1$ 的所有点进行分裂。代价容易计算。注意到每次分裂出的叶子数是单调不减的，这样再记录一个 $lim$ 即可。这样 $n=100$ 只有 $1745$ 个状态，这样还避免了合并，就很神人。 ### 279 qoj2279（树的直径） 找一点合法方案的性质，我们希望推导出判定条件。 显然 $\text{dis}(u,v)=k$ 的两个点 $u,v$ 颜色相同。链的做法是比较简单的，也启示我们考虑树的直径。判掉树的直径过于短的平凡情况，那么这个直径单独拉出来一定满足链的性质，即一定是关于 $k$ 同模的等价类中选且只选一个全染黑。接下来我们考虑与直径有关的方案，对于与直径完全无关的，长度为 $k-1$ 的路径，那么直径上的染色方案 那么在这个阶段，我们只需要关心与直径有关的路径。进一步考虑，发现不需要考虑经过直径，但端点都不在直径的方案（证明就是使用另外 $3$ 条符合条件的路径来进行差分）。所以对于与这条直径有关的方案而言，我们只需要关心至少一个端点在直径上的所有路径。设直径两个端点为 $x,y$，显然一个点不会被长度 $k-1$ 路径经过就可以不管它，在最终计数过程可以直接乘 $2$，处理出每个点除去到直径距离，剩余部分以 $u$ 开始的最长路径 $h_u$ 然后判定 $h_u+\max(\text{dis}(u,x),\text{dis}(u,y))<k-1$ 即可。找到 $x\to y$ 路径上选取的等价类，即可对剩余有用点染色。进一步考虑通过直径染色方案来确定的方案，一个点 $u$ 是可确定的当且仅当 $\max(\text{dis}(u,x),\text{dis}(u,y))\ge k-1$。那么我们已经可以确认很多的等价类，但是离的比较近的点可能是未被确定的。提出来 $x\to y$ 的路径，求出每个点到这个路径的第一个接入点 $top_u$，定义新的 $dep_u$ 表示到直径的距离。 存在某些点不在直径上，等价类未被确定，但是仍然有用，这是本题的关键。如果 $h_u+\text{dis}(u,x)\ge k-1$，称为 A 类点，类似定义 B 类点以及 AB 类点，其中仅为 A/B 类点称为单侧点。容易发现 AB 类点是一堆连通块，单侧点是若干个子树。进一步考虑某个 $u$，如果有 $\min(\text{dis}(x,u),\text{dis}(u,y))\ge k-1$，并且 $dep_u\leq \lfloor\frac{k-1}{2}\rfloor$，那么必须有 $col_u=0$，否则会出现直径上连续 $\ge k$ 个点全是 $0$；进一步考虑一个 AB 类点 $u$，深度大于 $\lfloor\frac{k-1}{2}\rfloor$ 一定是确定等价类了，否则不难推出这样的 $u$ 一定是 $col_u=0$。简而言之，对于一个 AB 类点 $u$ 而言，要么等价类是确定的，要么 $col_u=0$。 接下来考虑单侧点的染色，这些是若干个子树，找到这些子树的根 $u$。$fa_u$ 要么是 AB 类点要么在直径上，不妨设 $u$ 是 A 类点，即距离 $x$ 是更远的。若 $x\to fa_u$ 的路径上已经存在 $1$ 那整个子树就可以递推确定；否则染 $1$ 的节点 $v$ 必须满足 $\text{dis}(v,x)\leq k-1$，并且所有叶子 $v$ 到 $u$ 的路径上都恰好只有一个 $1$。另一方面，对于一个 $u,v$ 使得路径 $u\to v$ 与直径无交并且 $\text{dis}(u,v)\leq k-1$，那么这样的 $u\to v$ 路径上的所有点都是 AB 类点。 枚举 $k$ 个等价类中哪个染色，容易得到一个 $n^2$ 的做法。AB 点会 ban 掉 $\mathcal O(1)$ 个区间，所有单侧点 $u$ 的子树会给一个区间的等价类的方案数乘上方案数。代码实现是十分复杂的。 时间复杂度 $\mathcal O(n)$。 ### 280 模拟赛 #14B（博弈，01 转具体值） 考虑最终的状态是什么样的：若首尾字符一样则胜负情况确定，对于其他情况无论如何操作，首尾字符不变，不妨设剩下的串首字符为 $1$，末字符为 $0$。剩下串的形式一定是一段 $1$，一段原串的区间，一段 $0$。若此时为先手操作，删除开区间的左端点必定是剩余字符串第一个 $1$ 连通块的最后一个 $1$ 的位置，若为后手操作则右端点为最后一个 $0$ 连通块的第一个 $0$。最终结果一定是两段连续段，且由剩余 $1$ 和 $0$ 的个数决定胜负。 将相同的 $0/1$ 连续段缩在一起，由前面的分析可将原问题转为：初始时先后手分别拥有第一个或 最后一个连续段长度的分数。随后两人轮流选择一个自己对应的连续段，把自己分数加上此连续段长度，并将中间的所有连续段删去，两人均想最大化自己分数，问最后谁赢。设计 dp，$f_{l,r,0/1}$ 表示当前为先手或后手取数，剩下了 $[l,r]$ 区间，在此区间内先后手获得的分数之差，转移时枚举当前操作的人选择哪个连续段。转移实际上是要求一个前缀/后缀的最大/最小值，容易优化，时间复杂度 $\mathcal O(n^2)$。 ### 281 cjy 宝宝作业 #5（上） #### A（gym104819F，无向图三元环） 考虑枚举最中间的三元环，求出 $c_i$ 表示边 $i$ 被多少个 $K_3$ 所包括。对于每个三元环求 $(c_x-1)(c_y-1)(c_z-1)$，然后考虑去重，那么需要找出的是所有 $K_4$，要容斥掉 $K_4$ 的贡献以及 $K_4$ 再加一个三元环的情况。那么只需要求出 $d_i$ 表示 $i$ 边在多少个 $K_4$ 上。$K_4$ 个数就是 $\frac{\sum d_i}{6}$，$K_4,K_3$ 共享某边的情况就是 $(c_i-2)d_i$。 而 $K_3$ 的统计是经典的，按照度数排序并对无向边定向，枚举 $u\to v,v\to w$，预先标记 $u$ 的所有出边，如果 $w$ 被标记，那么找到一个三元环，复杂度 $\mathcal O(m\sqrt m)$，因为每个点的出度是 $\leq \mathcal O(\sqrt m)$ 的。对于 $K_4$ 的统计，继承 $K_3$ 的定向，枚举度数最小的点 $u$，需要考虑其所有出边之间的三元环个数。根据三元环计数的复杂度分析，这之间的所有边是可以被暴力枚举的。然后手写一个 bitset，求出每个与 $u$ 相邻的位置 $v$，与剩余的哪些 $v'$ 相邻，记这样的集合是 $S_v$。然后枚举一个三元环 $(u,x,y)$，求 $|S_x\cap S_y|$，显然是 bitset 可以做到的，而 bitset 的大小是 $\sqrt m$，会执行 $m\sqrt m$ 次这样的操作，因此复杂度 $\mathcal O(m\sqrt m+\frac{m^2}{\omega})$。 #### B（uoj218） 用可持久化线段树维护当前每个栈的栈顶及区间和，区间压入一个数直接对可持久化线段树做区间赋值即可。单点弹出时，我们可以通过查询当前栈顶的数 $x$ 在压入之前的那个版本的栈顶的数 $y$，做一次单点赋值即可。时空复杂度 $\mathcal O(m\log n)$。 #### D（P9257，搜索） 智商题。 将贤者看作点，每条咒语的 $(a,b)$ 连边，形成一个图。定义 $f(G)$ 表示在上帝视角下，有贤者没来聚会的最早时刻。注意若此时 $G$ 中边集为空集，则 $f(G)$ 未定义。若 $f(G) = 1$ ，此时 $G$ 为菊花图；若 $f(G) > 1$，即 $G$ 不为菊花图。考虑某个贤者 $x$，他认为的图 $G_x$ 是在 $G$ 中删掉了 $x$ 和与 $x$ 相邻的边后形成的图。若第 $f(G_x)$ 次聚会时仍未有人离开，则 $x$ 会在第 $f(G_x) + 1$ 次聚会时离开。所以 $f(G) = 1 + \min f(G_x) $。 注意到这个转移式子很像一般图最小点覆盖的转移。考虑令边集为空集时 $f(G) = 0$，则 $f(G)$ 即为图 $G$ 的最小点覆盖。而在 $f(G)$ 时刻离开的贤者 $x$ 满足 $f(G) = f(G_x) + 1$，即存在某个最小点覆盖的点集 $S$ 包含 $x$。此时 $\mathcal O(2^n \text{poly}(n))$ 计算即可。 一般图最小点覆盖是图灵奖问题。 注意到 $k$ 较小，考虑以下算法：选出图中度数最大的结点 $x$。枚举 $x$ 是否在覆盖集里。若在，$k \leftarrow k-1$，若不在，$k \leftarrow k - deg_x$。当 $deg_x \leq 2$ 时，图中仅有孤立点或环或链。计算最小点覆盖和覆盖集的并是容易的。所以仅需要在在 $deg_x > 2$ 时递归进两个子问题。总的递归次数大约是 $T(k) = T(k-1) + T(k-3)$。$T(30)$ 是 $4 \times 10 ^{4}$ 级别。总复杂度是 $\mathcal O(T(k)m)$。 #### E（IOI2021 P2） 模仿 boruvka 算法做 $\log n$ 轮集合合并。 #### F（P6789） 拆贡献，只考虑在他前面的边，那么一个边不产生贡献分为不连通或者已经连通并且未成环。成环是不好处理的，但是可以计算连通的方案数以及生成树的方案数。容易做到 $\mathcal O(3^nm)$。 #### G（P5811，图的 dfs 生成树分析） 不妨设 $a\leq b\leq c$，那么我们需要找出两个大小分别为 $a,b$ 的连通块。无向图是不好分析的，考虑取出 dfs 生成树分析，我们希望他变成一个树上问题。首先考虑 $G$ 构成的树的做法。取出树的重心 $R$，如果可以不包含 $R$ 而是在两个子树各自放那么是平凡的，否则考虑包含 $R$ 的连通块，注意到 $b\leq c,a+2b\leq n\to b\leq\frac{n}{2}$，那么将最大的子树分配给 $a$ 即可，剩下从 $R$ 开始找大小为 $b$ 的子树即可，如果 $a$ 是放不下的，那么是无解的，感受一下很对。上述做法的本质是枚举一条边被断开。 接下来考虑一般无向图的做法，我们加入了返祖边的限制，任意找出这个生成树，并且求出它的重心 $R$。与一般情况不同的是，$R$ 下面的子树有可能与 $fa_R$ 方向的子树连通，因此对于最大子树 $<a$ 时依然可能有解，因为它可能通过上方的连通块来跳过 $R$。直接大胆猜测，将这样的连通块与 $fa_R$ 对应的连通块合并，如果这些的和 $\ge a$，那么整体就是有解的。原因是 $b\leq n/2$ 以及最大子树不超过一半的限制是比较强的。 ### 282 sd 二轮集训 - 试机 **A（qoj5437）**：首先缩点然后建树，那么连 $(x,y)$ 的方案数是 $2^{siz_xsiz_y}-1$，我们需要覆盖所有的树边。容斥某些树边不被覆盖，对于一个割掉树边的方案，对于每个连通块内部任意连即可。那么在 dp 的同时记录一下包含 $u$ 的连通块大小。树上背包复杂度 $\mathcal O(n^2)$。 **B（qoj5458）**：值域 $[1,n]\times[1,n]$ 的凸包数上界是 $\mathcal O(n^{2/3})$，因此可以直接暴力维护每个点的凸包，询问可以直接暴力，也可以二分。时间复杂度 $\mathcal O(mn^{2/3})$。 **C**：考虑固定最大值后两边独立。那么求出移动的代价即可，均摊一下逆序对的贡献，维护最小后缀和以及最大前缀和即可。时间复杂度 $\mathcal O(n\log n)$。 ### 283 cjy 宝宝作业 #5（下） #### H（uoj772） 首先将所有 $s$ 插入 ACAM，建立出 fail 树，那么就是在 ACAM 上游走，每走到一个点就对 fail 树上对应节点到根的链进行考虑，如果存在一个 $v$ 有标记并且标号为 $k$，那么令 $c_k\to c_k+1$。问题在于这个权值没有很好的合并方法。 由于 UNR#8 D1T2 太原神了，我们猜测这是一个原神题。从模数入手。考虑 $3^P$ 对 $2^{32}$ 取模，可以写成 $3^P=(2+1)^P=\sum_{k=0}^P\binom{P}{k}2^k$。对 $2^{32}$ 取模说明可以忽视所有 $k\ge 32$ 的子项，那么需要维护 $\sum_{k=0}^{\min(ic_i,31)}\binom{ic_i}{k}2^k$。可以暴力，每次用 $\log \text{mod}$ 的时间因子来更新。模仿链离散化出每一段，每一段逐个处理的操作，对于每个 $t$ 建立一个虚树然后这些编号是可以统一维护的，处理 $k$ 次方前缀和，然后暴力，就赢了。时间复杂度 $\mathcal O(L\log L\log \text{mod})$。 上面那个不是正解。所有文本串匹配到不同模式串个数之和，暴力可以证明是 $\mathcal O(L^{4/3})$。 #### I（gym102803E） 数据范围：$n\leq 10^6$。首先使用若干 $h_i\ne -1$ 的位置信息来用并查集维护出若干个等价类。$s_{sa_i+j}=s_{sa_{i-1}+j}$ 得到的信息是 $[rk_{sa_i+j},rk_{sa_{i-1}+j}]$ 都是相等的，因此直接做暴力，合并次数是 $\mathcal O(n)$。另一方面，尽管 $h_i=-1$，我们也可以得出两个点的关系是 $\leq $ 还是 $<$。然后你从前往后对于每个等价类的第一个元素扫一遍就赢了。 #### J（P4156） 同余最短路，利用 border 可以拆分为 $\log$ 段等差数列来优化。 ### 284 sd 二轮集训 day1 出题人：唐绍轩。 #### A 显然，答案只能在 $\{1,2,3,-1\}$ 中取。在非无解情况的构造就是走到直径 $p,q$ 上，路径形如 $x\to p\to q\to y$。$ans=1$ 是平凡的，重点在于判定 $ans=2$。有一个有道理的做法是取出 $x\to y$ 的直径中点 $mid$，如果有两个就都判。然后查询 $mid$ 子树与 $mid$ 子树补各自部分点集的直径端点是否符合 $\min(\text{dis}(x,u),\text{dis}(y,u))\ge k$，树根是其中一个直径端点。使用四毛子维护 $\text{lca}$，可以做到 $\mathcal O(n)$。正经做法是取出来直径，转化成序列问题，使用线段树维护是 $\mathcal O(n\log n)$。 #### B（主席树优化建图，dag trick：删末端节点） 浅谈稠密有向无环图上最小等价 dag 的求法。 求出 $f(G)$ 的限制相当强，需要有明确的可达关系刻画。对于 $f(G)$ 的构造，显然一个 scc 保留一个极大环即可。由于需要刻画连通性，在一般的 dag 做最小化上只能做到 $\mathcal O(\frac{|V||E|}{\omega})$，按照拓扑序递增，维护一个 bitset，对于后继反序并贪心并上这个后继可以到达的点，如果已经完成了就结束，原因是 $E=\{(1,2),(2,3),(1,3)\}$ 中 $(1,3)$ 是无用的，拓展到一条路径同理。$f(G)$ 本身并不是很好做，我们需要先刻画出可达关系，然后利用可达关系来做 $f(G)$。求出来的最终图是相当稠密的，在 $m=0$ 的竞赛图上拓扑序前面的一定可以到达后面的，由于保证了 $m,f(G)$ 较小，考虑转而记录拓扑序前面不可以到达后面的所有信息。因此，我们需要做完缩点并刻画出可达关系，才能做 $f(G)$。 考虑 $m=0$ 怎么做，由经典结论，竞赛图缩点后构成一条链，这条链的顺序可以由每个点的出度从大到小得到，每个 scc 是一段区间。一个前缀构成 scc 的最后一个位置当且仅当出度和是 $\binom{n-i}{2}$，进而，考虑先求出最终的 scc 集合。将求出度，二维偏序的步骤直接改成从前往后连边，使用主席树优化建图，这是因为对于一个位置 $u$，考虑后面被 ban 掉的点集进行排序，拆成了若干个区间，正反跑一遍即可。这样求出所有的 scc 以及求对应拓扑序这一步是 $\mathcal O((n+m)\log n)$ 的。 接下来考虑给定若干不可达关系时（要求两个 scc 之间的边被全部删除，看数量是否正确即可），$f(G)$ 的求法。按照拓扑序倒序考虑 $u$，我们希望找到 $u$ 在 $f(G)$ 的所有出边，拿 bitset 暴力模拟第一段所述过程，求出传递闭包后做是 $\mathcal O(\frac{n|f(G)|}{\omega})$ 的，具体来说你需要进行 $f(G)$ 次 $\text{xor,findfirst}$ 操作。考虑基于 $m$ 的做法，令 $G'$ 表示拓扑序更大的点，在 $f(G)$ 上的导出子图。维护一个关于 $0$ 入度点的队列 $q$。我们先考虑所有在 $G'$ 中的零入度的点 $v$，如果存在边 $u\to v$，那么显然应该连上，那么此时所有能被 $v$ 指向的点的可达性就也解决了；如果不存在边 $u\to v$，那么我们就在 $f(G)$ 中把 $v$ 这个点给删除了，然后这样 $v$ 指向的点的入度就会 $-1$；不断这样找零入度的点，直到没有需要继续处理的零入度的点了。这样就加入了 $u$。 分析一下复杂度，对于删除并对后继的 $deg\to deg-1$ 的操作，对于单个 $x$ 的后继点集 $S_x$ 内部是两两无交的，否则就会出现第一段所述的结构，而在递推的过程中这并不存在，这就说明 $S_x^2\leq\mathcal O(m)$，因此 $S_x\leq \mathcal O(\sqrt m)$。综上，复杂度 $\mathcal O(m\sqrt m+(n+m)\log n)$。 #### C（atcoder jsc2022_final_f，延迟钦定，压缩有效状态） 首先考虑 $a$ 全部相等的情况，不妨设加点顺序是 $2\sim n$，最终乘上 $(n-1)!$ 即可。你发现记录已经使用的是没什么性质的，考虑记录没有使用的。暴力是 $f_{i,S}$ 表示剩余 $S$ 集合的操作没有用，当前连通块是 $[1,i]$。$S$ 中有三类元素：$A:[1,i]\times[1,i],B:[1,i]\times[i+1,n],C:(i,n]\times(i,n]$。不难发现，我们只关心 $|A|,|C|$，显然对于 $|C_1|=|C_2|,f_{i,A\cup B\cup C_1}=f_{i,A\cup B\cup C_2}$。与此同时，我们希望减少 $B$ 的数量。注意到在接下来的过程中 $[1,i]$ 都是等价的，并且 $[i+1,n]$ 具体是谁可以延迟钦定，因此只关心：$b_i$ 表示有多少 $(i,*)$，此时 $b$ 构成的可重集，那么在所有的 $i$ 求和，记总数就是 $2^n$ 的。转移的过程可以分步转移，加之轮廓线 dp 的优化。另一方面，考虑 $a$ 不同的话，显然此时的 $i$ 就是记录的可重集大小。复杂度看上去是 $\mathcal O(2^nn^5)$。代码写起来很 trivial，先摆了。本题的重点在于压缩 $B$。 ### 285 sd 二轮 day1/2 - 杂题选讲 #### loj6669 增量维护，求出所有点到 $1$ 的距离然后从小到大排序，动态挂叶子。然后维护重链剖分，插入叶子时求出它到 $1$ 所在重链底端距离，求出 lca 后沿着轻边往下走即可。可以用 $\log n$ 的代价求出每个点的父亲。 #### uoj33 有根树点分树是好文明。考虑首先求出数组 $g_i$，表示 $f(u,v)$ 是 $i$ 的倍数的数对数量，最后莫比乌斯反演回来即可。 然后点分治，求出$(u,v)$ 不是祖先关系的情况。$(u,v)$ 是祖先关系的最后差分维护一下即可。对于分治中心 $x$，我们分开求出一下两种情况：$u,v$ 都在 $x$ 的子树中，且 $lca(u,v)=x$；$u,v$ 一个在 $x$ 的子树中，另一个不在。第二种情况，我们定义一个阈值 $s$。 预处理出 $num_{i,j}$ 表示 $x$ 子树中到 $x$ 的距离 $\bmod i=j$ 的点的数量， $cnt_i$ 表示到 $x$ 的距离为 $i$ 的点的数量。 那么对于子树外的情况，$i≤s$ 的部分可以在递归子树的时候通过 $num$ 快速的求出来，该部分时间复杂度 $\mathcal O(ns)$。 对于 $i>s$ 的部分，我们直接暴力枚举距离，用 $cnt$ 统计总点数， 时间复杂度 $n^2/s$。 故一个分治中心的时间复杂度是 $\mathcal O(n^{1.5})$。伟大的主定理告诉我们总复杂度 $\mathcal O(n^{1.5})$。 #### CF1514E 首先利用增量法找出一条哈密顿链，具体来说每次二分找插入的位置。接下来，我们需要把强连通分量缩点，从前往后遍历哈密顿链上的点 $k$，然后询问点 $k$ 到所有 $k$ 之前的点是否有出边，如果有出边，那么 $k$ 与 $k$ 的前驱一定处在一个强连通分量中，把它们合并即可。总共 $n\log n$ 次询问 $1$，$2n$ 次询问 $2$。 #### CF1508D 如果整个排列是一个置换环，那么可以选一个中心点，不断走环进行 swap。考虑两个置换环的合并就是交换来自两个环的元素，由于我们的这些线段不能与和 $s$ 相连的线段冲突，所以我们将它们限制在，关于 $s$ 极角排序后，相邻的点之间。那么并查集维护一下置换环，选取左下角的点进行极角排序，复杂度 $\mathcal O(n\log n)$。 #### CF1535F 不妨设所有串的字符集相同，显然答案 $\leq 2$。那么枚举 $\text{lcp}$，将这些插入 trie 树。你发现如果这个串是不动的，那么第一个 diff 的位置一定是贪心选取最长不降的段。那么只需要对所有后缀哈希一下就可以做到 $\mathcal O(n|\Sigma|)$。另一个做法是对于每个等价类按照字典序排序，那么 $\text{lcp}$ 可以表示成邻项的 $\text{lcp}$ 的区间 $\min$，那么维护单调栈，反串插入一个 trie，在对应的节点二分有多少个即可。时间复杂度 $\mathcal O(L\log L)$，空间复杂度 $\mathcal O(L|\Sigma|)$。 #### CF1603D 注意到 $w(l,r)$ 具有决策单调性，可以整除分块计算。当 $2^k>n$ 时答案为 $n$，所以可以预处理所有询问的答案。 ### 286 sd 二轮集训 day2 出题人：唐绍轩。 #### A > 给定长度为 $n$ 的序列 $b$，求所有 $0\leq b_i\leq a_i$ 的 $\text{mex}(b)$ 求和。$n\leq 5000$。 考虑容斥，将 $0\sim k$ 必须出现转化为钦定某些数不能出现。设 $f_{i,j}$ 表示 $0\sim i$ 必须出现，现在钦定其中 $j$ 个数不能出现，所有 $B_k\le i$ 的 $A_k$ 的方案数乘容斥系数之和。 转移时，先令 $f_{i,j}\gets f_{i-1,j}-f_{i-1,j-1}$。若有 $C$ 个 $k$ 满足 $B_k=i$，则再令 $f_{i,j}\gets f_{i,j}\times (i+1-j)^C$。设 $g_{i,j}$ 表示 $\text{mex}(A)\le i$，且钦定 $0\sim i$ 中有 $j$ 个数不能出现，所有 $B_k\le i$ 的 $A_k$ 的 $\text{mex}(A)$ 乘容斥系数之和。转移时，先令 $g_{i,j}\gets i\times f_{i-1,j-1}+g_{i-1,j}$。若有 $C$ 个 $k$ 满足 $B_k=i$，则再令 $g_{i,j}\gets g_{i,j}\times (i+1-j)^C$。注意到 $\text{mex}(A)$ 一定不超过 $n$，因此两个 dp 数组只需计算到第 $n$ 行，其余数的贡献容易计算。时间复杂度为 $\mathcal O(n^2)$。 #### B（异或线性基计数） > 给定 $n,m,X$，以及 $k$ 个正整数 $b$。对长度为 $m$，值域 $[0,2^n-1]$ 的序列 $a$ 计数，使得 $a$ 的异或空间可以表示出所有 $b$，并且子集最大异或和 $\ge X$。$n\leq 5000,k\leq 1000,m\leq 10^9,1\leq b_i\leq 2^n-1$。 考虑生成一张 $k$ 行 $n$ 列的矩阵，第 $i$ 行填上 $b_i$，把它消元成一个简化阶梯形矩阵，去掉全 $0$ 行后即为 $b_1,b_2,\cdots,b_k$ 张成的线性空间对应的简化阶梯形矩阵，该线性空间的秩即为矩阵的行数。接下来只需对于所有包含该线性空间且最大值 $\ge X$ 的线性空间，计算恰好张成它的序列个数之和。 先考虑对于给定的一个线性空间，计算有多少序列 $a_1,a_2,\cdots,a_m$ 的恰好张成它，显然我们对线性空间消到最简时，我们只关心 rank。设该线性空间的秩为 $r$，所求即为有多少 $m$ 行 $r$ 列的矩阵满秩，即要求这 $r$ 列线性无关。所以考虑一列一列地填，第 $k$ 列的方案数为 $2^m-2^{k-1}$，减去的是由前面线性表示出的情况。因此方案数为 $\prod\limits_{i=0}^{r-1}\left(2^m-2^i\right)$。 用 $a$ 表示 $b$，而 $a$ 是未知的，这个比较困难。因而考虑用 $b$ 作为 $a$ 的基底，在接下来的过程中，只关心这些 $b$ 全部加起来的结果，这样就有一个 $01$ 序列表示 $b$ 的和是否包含了这一位。回到原问题，可以看成在原矩阵中新增一些主元列，并添加对应的行，这一行在其他主元列的位置上全为 $0$，用这些基底必须构造出 $\ge X$ 的。另一方面，在计数上我们只需要考虑行最简形的基底组合，相当于是作为一个等价类的代表元出现。这样就是好统计的。考虑新增一行对最大值的贡献，如果原本的最大值在这一列上已经是 $1$，则该行对最大值没有贡献，否则最大值需异或上该行的值。 现在考虑 dp 方案数，对于这个最大值而言从高往低进行数位 dp 就好了。需要记录的状态有：现在考虑了 $i\sim n-1$ 列，新增了 $j$ 行，当前是否有新增的行对最大值有贡献，当前最大值与 $X$ 的 $i\sim n-1$ 位是否一致。转移时分类讨论即可，细节较多。需要注意到如果一列不是主元列，那么如果有新增的行对最大值有贡献，则各有 $2^{j-1}$ 种方案使得最大值在该列的取值为 $0$ 或 $1$，否则 $2^j$ 种方案中，最大值在该列的取值是固定的。 时间复杂度为 $\mathcal O\left(\frac{nk^2}{\omega}+n^2\right)$。 有时间重修一下洛谷 P10707。 #### C（转置原理转化问题，单侧递归） [一类用转置原理优化算法的 Trick - 洛谷专栏](https://www.luogu.com.cn/article/nb084syd) > 给定 $n$，给定一个列数为 $n$ 的矩阵的第一行 $a$，每次拓展一行，其中 $[l,r]$ 的 $a$ 需要在上一行基础上 $+x$；给定 $k$，查询当前矩阵中，每行的 $[1,k]$ 列的元素的最大值，这些取最小值的结果。强制在线，$n,q\leq5\times10^5$。 直接分块然后 $\mathcal O(n\sqrt{n\log n})$ 是平凡的。 考虑 $(\min,+)$ 矩阵的转置原理，设询问的答案为 $ans_1,ans_2,\cdots,ans_q$，令矩阵 $M=\begin{pmatrix}ans_1\\ans_2\\\vdots\\ans_q\end{pmatrix}$。那么所求即为 $M\cdot\begin{pmatrix}0\end{pmatrix}$。转置后变为计算 $ \begin{aligned} &~~~~~M^T\cdot\begin{pmatrix}w_1\\w_2\\\vdots\\w_q\end{pmatrix} &=\min(ans_1+w_1,\cdots,ans_q+w_q) \end{aligned} $。设 $a_{t,i}$ 表示 $t$ 次操作后 $a_i$ 的值，则上式为 $$ \begin{aligned} &~~~~~\min_{1\le k\le q}\left(\left(\min_{0\le i\le t_k}\max_{1\le j\le x_k}a_{i,j}\right)+w_k\right) &=\min_{0\le i\le m}\left(\min_{1\le x\le n}\left(\min_{k~:~i\le t_k,x_k=x}w_k+\max_{1\le j\le x}a_{i,j}\right)\right) \end{aligned} $$ 按 $i$ 从 $m$ 到 $0$ 扫描，记 $y_x=\min\limits_{k~:~i\le t_k,x_k=x}w_k$，查询的式子为 $\min\limits_{1\le x\le n}\left(y_x+\max\limits_{1\le j\le x}a_{i,j}\right)$，即序列 $a_{i,*}$ 的前缀最大值的每项加上 $y_*$ 后的最小值。需要支持的操作为对 $a$ 区间加，以及对 $y$ 单点修改。可以使用单侧递归线段树来实现，时间复杂度为 $\mathcal O\left((n+m)\log^2n\right)$。将该算法转置后可以在线地处理所有操作。 ### 287 sd 二轮集训 day3 出题人：焦思源。 #### A 不妨设边 $(1,n)$ 的方向是 $1\to n$，那么 $s_i>t_i$ 的任务一定不可能从外部走，那么将 $s_i<t_i$ 的区间 $[s,t]$ 来考虑，一定是一个区间 $[L,R]$ 满足在 $[L,R]$ 之中的区间必须从内部走，外面的必须从外部走，$[L,R]$ 本身可以任选，要求不存在与 $[L,R]$ 相交却不包含的，直接扫描线加线段树维护这个可以得到 $m\log m$ 的做法，但是常数太大。考虑最终从内部走的 $s_i>t_i$ 的任务，它一定是把区间按照长度从小到大排序后的一个前缀。 证明很简单，一个从外部走的任务最多只能提供长度大小条可以被反向定向的空间。 判断一个前缀是否合法也很简单，求出后缀的所有区间的交，维护一下前缀内 $l_i$ 的最小值和 $r_i$ 的最大值，判断一下是否包含即可。 只需要对所有区间排序，复杂度也是 $\mathcal O(m\log m)$。 #### B（atcoder ddcc2019_final_e，构造，压缩/合并信息） 注意到 $0$ 边权是非常有用的，那么我们可以利用 $0$ 边来通过增加点数的方式来构造重边，那么可以构造出 $2\sqrt k+\mathcal O(1)$ 的答案，这样就有 $n=92$，即将源汇分别拆掉。接下来使用二进制拆分类似的思路来优化源汇的构造，目标是降低完全二分图连边的边数，边数为 $e$ 时就需要 $2\sqrt e$ 的点数。将源点拆为 $1,2$，中间边权是 $1$。这样你需要构造 $(2x,2x+1)$ 时，根据是否在 $a$ 中，向对应的源汇进行连边。这样两个信息就只需要一条边来描述，可以做到 $n=69$。 进而将连续 $4$ 个数分为一组，实际有用的状态其实只有 $8$ 个，这是因为如果某一组的第一个数是 $0$，我们可以直接跳过这个位置从下一个非零位置开始划分，这样只有 $2^3$ 种状态。此时是 $4+22+8+22+1=57$。把汇点删了，用最后一层的最后一个作为汇点即可做到 $56$。事实上 $1,2,3,4$ 四个点也可以删成一个。 把 $2^3$ 个组里每个组的第一个作为这个组的代表元素，然后代表元素向同组内的其他元素连 $0$ 的边，这样的话只需要使得代表元素之间符合要求即可。而这是简单的，从 $1$ 向第 $0,1,2,4$ 组的代表元分别连 $0,1,2,3$ 的边，然后每个代表元向其超集代表元连 $0$ 边即可。即使某个组是空的也无所谓，直接新建就行，这个地方不影响点数。 最后是 $n=53$。 #### C（qoj10322） 考虑一组针对边的流量序列是否合法，我们只需要考虑用前 $x$ 个去匹配下一个颜色的最后 $x$ 个，这个的最后 $y$ 个去接受前一个颜色的最前 $y$ 个，那么维护 $a_i$ 表示 $i$ 与 $i\bmod m+1$ 组的最大匹配数，这相当于维护一个括号匹配，这样类似于 CTT2024 D1T2，每次暴力在左右波动一下判定是否合法，动态开点线段树维护 $1,-1$ 折线的最小前缀和，每次只影响 $\mathcal O(1)$ 对匹配，容易维护。另一方面，令 $b_i$ 表示有多少个数颜色为 $i$。那么我们需要选取一个序列 $x$ 满足 $0\leq x_i\leq a_i,0\leq x_i+x_{i\bmod m+1}\leq b_i$。然后直接枚举 $x_1$，然后每次贪心地令$x_{i+1}=\min(b_i−x_i,a_{i+1})$，这样是 $\mathcal O(nmq)$ 的。 直接优化这个过程，观察到前侧传入的 $x$ 传出的值是一个分段一次函数，而分段函数复合是很好用线段树维护的。设 $f_i(X)$ 表示 $x_i =X$ 时 $x_m$ 等于什么，$g_i(X)$ 表示 $\sum_{j\geq i} x_j$，可以证明 $f,g$ 都是 $\mathcal O(1)$ 段分段一次函数，直接用线段树维护即可，时间复杂度 $\mathcal O((n+q)\log n)$。另一种方法是对 $x$ 做线性规划对偶然后线段树维护矩阵乘法。 ### to do [20250426 训练赛 - Virtual Judge](https://vjudge.net/contest/712564#overview)