25.09-LCA-Week1-4 模拟赛题解

· · 题解

09.25

T1 被前导零挂到 30 了，其他打得还行。

T4 的 DP 只保留有效状态，值得学习。T5 的数据结构可以练习码力，已严肃练习。

T4 学术竞赛

题意

有 n 名参赛者和 m 道题，每人每题的得分均在 [0,k] 内。给出所有得分情况 a_{i,j}，问最少保留多少个 a_{i,j} 能唯一确定出原来的排名，分数相同的按编号从小到大排序。n\le 2\times 10^4,m,k\le 100。

题解

先排出目标排名 p，之后设 f_{i,j} 表示考虑了排名前 i 的所有人，且 p_i 的分数下界 l_{p_i}=j 时，最多能删掉多少个数。状态数是 O(nmk) 的，转移时考虑枚举当前的左端点 l 和删的个数 c，若 p_i 删掉 c 个数后和可为 l，则可转移 f_{i,l}\leftarrow\max_{j=l+ck+[p_{i-1}>p_i]}^{mk} f_{i-1,j}，可预处理后缀最大值，转移复杂度为 O(nm^2k)。转移前还需求出 g_{c,l} 表示能否删掉 c 个数后恰为 l，这可以使用背包解决，总复杂度 O(nm^3k) 或 O(\frac{nm^3k}w)，难以通过。

接着发掘本题的性质，发现 l_i\le s_i\le r_i，即删数后的取值区间一定包含原来的和。那么一定有 s_{p_{i+1}}\le l_{p_i}\le s_{p_i}\le r_{p_i}\le s_{p_{i-1}}，否则一定不满足限制。设 t_i=s_{p_i}-s_{p_{i+1}}，有 l_{p_i}\in[s_{p_{i+1}},s_{p_i}],s_{p_i}-l_{p_i} \le t_i。于是以 t_i 为最大容量做背包，也只枚举 t_i 种 l，后缀最大值也只取 i-1 有意义的部分。这样单次背包复杂度为 O(m^2 t_i)，单次转移复杂度为 O(mkt_i)。由于 \sum t_i=O(mk)，总复杂度为 O(m^3k+m^2k^2)，可以通过。

原题

P13345。

T5 lunatic 难度佩洛洛斯拉

题意

有一个两维大小均为 n，初值均为 0 的数组 a，先进行 n 次矩形 checkmax，再求 m 次矩形和，保证修改的 xl=1 或 xr=n。v\le n\le 10^6,m\le 5\times 10^5，时间限制 16 秒。

题解

考虑保证全部 xl=1 怎么做，由于只有前缀操作，此时每一行元素均不降。因此从右往左扫描线，扫到修改右边界时区间 checkmax，查询差分成两个后缀，在对应时刻查询历史和。全部 xr=n 的情况是类似的，此时每行元素不增。

两种都存在时，设 A_{x,y},B_{x,y} 分别表示只考虑 xl=1,xr=n 的操作时 a_{x,y} 的最终值，则同一行内 A 不降 B 不增，\max(A_{x,y},B_{x,y}) 在一段前缀内取 A，剩下的后缀内取 B。设该位置为 p_y，若能求出所有 p_y 的值，可以拆分成两半分别进行上一段的扫描线，需要额外维护 v_y 表示目前第 y 行是否贡献，初始 v 全为 0，过程中加入 v 单点赋值为 1 的操作，查询同样是历史和。

考虑 p_y 怎么求，从下向上扫描线，则需要支持 A 前缀或 B 后缀 checkmax，两种均需支持撤销，查询最后一个 A_x\ge B_x 的位置 p_y。由于区间改的撤销是困难的，考虑转为单点改 A',B'，则 A 为 A' 的后缀 max，B 为 B' 的前缀 max，使用线段树维护 A',B'，并在上面二分求 p_y 即可，过程中需要记录目前后面的 \max A' 和前面的 \max B'，时间复杂度 O(n\log n)。

剩下的问题是左右两轮扫描线，需要维护初始全 0 的序列 t,v，支持 t 区间 checkmax，v 单点赋值为 1，查询区间 tv 历史和。使用吉司机线段树，只在 mn\lt v\le mn' 时打标记修改，同时使用一次函数维护历史和。注意这里懒标记也需要用一次函数，维护最小值变化过程中的贡献。时间复杂度不会分析，不知道是 O(n\log n) 还是 O(n\log^2 n)，反正不超过后者且能过。

09.27

这回 T1 没挂。T2 挂了，原因是 DP 上界没有对 m 取 min，理论上能卡到很低分但还有 80。

T3 是神秘调整贪心题，不会做。T4 是神秘 Hall 定理 + 数据结构，太困难。已严肃学习。

T2 在空无一物的时光深处

题意

有一个长为 m 的画板，可任取笔刷的初始位置 p，需要依次涂 n 种颜色，每次可选择终点 q 为 p-c_i+1 或 p+c_i-1，要求 1\le q\le m。之后将该区间内均涂成 i 并将 p 赋值为 q。求最终颜色不同的画板种类数。n,m\le 150。

题解

注意到顺着考虑时很容易记重，即一种画板形态对应多种最终位置。因此倒着考虑每次涂色，这时只能涂之前没涂过的位置，因此设 f_{i,l,r,0/1} 表示考虑了后 i 次涂色，当前有颜色的区间为 [l,r]，且笔刷最终位于左 / 右端点的方案数。注意到只有 n 一种颜色时还是会重，因此要枚举第二种颜色作为 DP 初始值。

转移时需要枚举下一次真正涂出颜色的操作 j，并要求 (i,j) 内的移动可以限制在 r-l+1 长度内，且最终停在某个位置，之后拓展出去若干格即可。在某长度内移动的限制可以使用背包，设 g_{i,j,lim,k} 表示考虑 [i,j] 内的操作，不能超出 [0,lim]，最终能否到达 k。转移是 O(1) 的，因此背包复杂度为 O(n^2m^2)。

然而此时 DP 需要枚举 i,j,l,r，还要枚举新染出去的长度 d，复杂度为 O(n^2m^3)，无法通过。然而注意到长度 r-l 相等的 f_{i,l,r} 均相同，因此这两维可以压成 len 一维，状态数变成 f_{i,len,0,1} 的 O(nm)，总复杂度降为 O(n^2m^2)，可以通过。

T3 烟花

题意

有 n 种烟花，第 i 种有 c_i 个且点燃成功率为 p_i。要求从中选出 k 个依次点燃，最小化某一个点燃失败且上一个点燃成功的期望次数。多组数据，T\le 10,n\le 10^5,k\le 10^9,\sum c\ge k。

题解

感觉非常不可做，需要挖掘其性质。令选择的烟花编号为 a_i，烟花总数为 m=\sum c。先考虑确定了选出的 k 个烟花后如何排列，从而最小化 \sum_{i=1}^{k-1} p_{a_i}(1-p_{a_{i+1}})=\sum_{i=1}^{k-1} p_{a_i}-p_{a_i}p_{a_{i+1}}。首先最大化后一项，根据排序不等式或调整法可知升序或降序时最大，又由于 p_{a_k} 不贡献，整个序列不降时取到最小值。

此时可以先把 n 种烟花按 p 升序排序，然而还是不好做，需要更深入的性质。若有 x<y<z 三个值，贡献为 x+y-xy-yz=y(1-x-z)+x，于是有 x+z\ge 1 时 y 越大越好，x+z\lt 1 时 y 越小越好，因此 y 一定会取到原序列中 x 后一个或 z 前一个。

这可以说明选择大概是比较集中的，下面尝试证明选的是一个前缀加一个后缀。首先有 p_1(1-p_{a_2})\le p_{a_1}(1-p_{a_2}) 且 p_{a_{k-1}}(1-p_m)\le p_{a_{k-1}}(1-p_{a_k})，因此 1 和 m 必选。之后设目前选的最长前缀为 l，最长后缀直到 m-r+1，并试图将离二者最近的元素调整进来。

具体地，若将 a_{l+1} 调整为 l+1，则变化量为 p_l(1-p_{l+1})+p_{l+1}(1-p_{a_{l+2}})-p_l(1-p_{a_{l+1}})-p_{a_{l+1}}(1-p_{a_{l+2}})，整理可得 (p_{a_{l+1}}-p_{l+1})(p_l+p_{a_{l+2}}-1)，在 p_l+p_{a_{l+2}}\le 1 时调整不劣；同理可得将 a_{k-r} 调整为 m-r 的变化量为 (p_{m-r}-p_{a_{k-r}})(1-p_r-p_{a_{k-r-1}})，在 p_{a_{k-r-1}}+p_r\ge 1 时调整不劣。

这时若 p_l+p_r\le 1，由于 p_{a_{l+2}}\le p_r，可将 a_{l+1} 调整为 l+1；否则 p_l+p_r\ge 1，由于 p_{a_{k-r-1}}\ge p_l，可将 a_{k-r} 调整为 m-r，这就证明了最终一定能调整成一段前缀加一段后缀。

这也引出了做法：维护目前的 l 和 r，若 p_l+p_r\le 1 则加入 l+1，否则加入 m-r，重复该过程直到选出 k 个。由于同种烟花的 p 相等，可令 l,r 一直为某种的端点，每次将 l,r 不变的一段全放进来，可以做到关于 n 线性。时间复杂度 O(n\log n)，在初始按 p 进行排序。

原题

P4110。

T4 归风

题意

定义序列 b 权值为初始 x=0，每次操作可将 x 增加 1，或让某个 b_i 异或上 x，将 b 全变为 0 的最小操作次数即其权值。给出长为 n 的序列 a，q 次询问其 [l,r] 区间内序列的权值。强制在线，n,q\le 2\times 10^5,a_i\lt 2^{60}。

题解

Hall 定理告诉我们，二分图最大匹配中左部失配点数为 $\max_S(\left|S\right|-\left|N(S)\right|)$。试图将上面的式子与其对应起来，则 $\left|N(S)\right|=x$，需要有 $x$ 个右部点，同时对应的左部点应该表示 $\sum_{i=1}^c[b_i\le x]$。考虑以每个 $b_i$ 为一个左部点，以每个整数值为一个右部点，左部 $b_i$ 向所有满足 $x\le b_i$ 的右部点 $x$ 连边，显然这是一个前缀。因此 $N(S)$ 也总是一个前缀，当其为 $[1,x]$ 时会选择所有 $b_i\le x$ 的 $b_i$，这是合法的最大 $S$，容易发现其他情况不会得到比原式更大的结果，因此这样构造是对的。 这样在该图上求出最大匹配数，即为所求的 $c-\max(\sum_{i=1}^c[b_i\le x]-x)$。由于左部点向右边前缀连边，以任意顺序枚举左部点并找最大右部点与其匹配是对的，不妨钦定顺序从右到左将 $[l,r]$ 内的点尽量匹配。对整个序列从左到右扫描，并实时维护 $[1,r]$ 从后往前依次匹配的结果。 由于后面的优先级更高，新加入 $r$ 时会强制匹配 $r$，这可能导致整个匹配不合法。仍然使用 Hall 定理，不合法也就是存在 $x$ 使得 $\sum_{i\in S}[b_i\le x]-x\gt0$。使用线段树维护每个 $x$ 的这个值，加入 $r$ 时对 $b_r$ 的后缀加 $1$，此时若存在 $x=1\gt0$，就找到最小的 $x$，再从 $x$ 前面找到编号最小的 $t$，将其从匹配中删去，从而保证 Hall 定理的条件仍然成立。容易发现某元素删去后一定不会再加回来，因此这是对的。 综上，线段树需要维护区间最大值及第一个最大值的位置，还要支持在每个点上维护一个集合，查询前缀集合内最小元素，这都是不难实现的。由于每个询问最高位 $2^p$ 唯一，且此时只关心 $(2^p,2^{p+1})$ 内的数，对所有这样的集合分别预处理该过程即可。由于区间无交，总复杂度是 $O(n\log n)$ 的。 此时得到了每个点在 $r\in[i,lim_i]$ 时在匹配中，同时还有 $l\le i$ 的限制，大概是平面内矩形加，每个询问相当于单点查询。对每个 $2^p$ 分别开一棵主席树，从而可以支持在线回答询问。同样由于区间无交，总复杂度也是 $O((n+q)\log n)$ 的。另外为了快速查询区间最高位，可能需要用 ST 表维护区间最大值，做到 $O(n\log n+q)$。 然后仔细看了一眼我代码，猛然发现理论复杂度瓶颈在查询单个值最高位的 $O(n\log V)$，抽象。使用 __builtin_clzll 做到 $O(1)$ 之后总时间复杂度为 $O((n+q)\log n)$。 #### 原题 [P12559](https://www.luogu.com.cn/problem/P12559)。 ## 09.29 单打 ACM 了说是，自己过了四个题。C 太唐了，G 我唐了，其他还行，发挥正常。 ### A 酒吧 #### 题意 给出 $n$ 个位置，每个位置有值 $a_i$，现需选择一部分位置标记，之后每个位置两边最近的标记位置值均会贡献到总和一次，求最大总贡献。多组数据，$n\le 5\times 10^5,\sum n\le 3\times 10^6$。 #### 题解 首先 $1$ 和 $m$ 必选，否则选上答案一定不降，之后发现答案是 $\sum_{i=1}^{k-1} (p_{i+1}-p_i)(a_{p_{i+1}}+a_{p_i})$。考虑寻找其意义，将 $(i,a_i)$ 标在坐标系上，发现该贡献即两点连线与 $x$ 轴围成直角梯形面积的两倍。因此要最大化所有梯形面积的和，显然选上凸包上所有点最优，维护出凸包后计算答案即可。时间复杂度 $O(n)$。 #### 原题 [QOJ5500](https://qoj.ac/problem/5500)。 ### E 数论方程 #### 题意 给定 $n,p$，求一组满足 $1\le x\lt y\lt z\lt p$ 且 $(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n})\equiv x^{3n}+y^{3n}+z^{3n} \pmod p$ 的整数 $(x,y,z)$。多组数据，$T\le 10^5,n\le 10^9,5\le p\le 10^9$ 且 $p$ 为质数。 #### 题解 三个未知数却只有一个方程，只需要求出任意解即可。考虑只找出一个主元，将其表示出来再由此构造解。令 $x=at,y=bt,z=ct$，代入并化简可得 $t=\frac{a^{3n}+b^{3n}+c^{3n}}{(a+b+c)(a^n+b^n+c^n)(a^{2n}+b^{2n}+c^{2n})}$。 这时只需找到 $(a,b,c)$ 使得 $a,b,c$ 两两不相等，且分数中四项均非零即可。可以证明若在值域内随机选择 $a,b,c$，单个式子为零的概率不超过 $\frac 14$，于是随常数次就可以找到答案。时间复杂度 $O(T\log n)$，来自计算过程中的快速幂。 #### 原题 [ARC158D](https://www.luogu.com.cn/problem/AT_arc158_d)。 ### F 野蛮 5 #### 题意 给出一个森林，两人轮流操作，每次删掉一条边或一个点及其邻边，无法操作者负，问先手是否必胜。$n\le 2\times 10^5$。 #### 题解 手玩一下感觉很有性质，这里直接给出结论：当且仅当 $n,m$ 均为偶数时后手必胜。证明考虑终止状态显然满足条件，接下来证明其他情况均可一步操作到 $n,m$ 均为偶数，而这种情况无法在操作一次后保持。分讨： - $n,m$ 均为奇数：删掉一个叶子节点，$n,m$ 均减小 $1$。 - $n$ 为奇数，$m$ 为偶数：删掉一个度数为偶数的点，$n$ 减小 $1$。由于度数总和为偶数，点数为奇数，这样的点一定存在。 - $n$ 为偶数，$m$ 为奇数：删掉一条边，$m$ 减小 $1$。 - $n,m$ 均为偶数：删点和删边后 $n,m$ 分别为奇数，无法保持。 因此，操作时若 $n,m$ 不均为偶数，不断将其变成均为偶数即可取胜，结论得证。只读入 $n,m$ 即可输出答案，时间复杂度 $O(1)$。 ~~第一次见不用读完输入的题~~。话说 LCA 还有 SG 函数做法，是本质相同的，只是推导过程略有不同，此处略去。 #### 原题 [QOJ2323](https://qoj.ac/problem/2323)。 ### H 醉晓生成树 #### 题意 有一个 $n$ 个点的完全无向图，每条边有 $p_0$ 的概率不存在，有 $p_i$ 的概率边权为 $i$。对所有 $t\in[n-1,k(n-1)]$，求图的最小生成树边权和为 $t$ 的概率。多组数据，$T\le 200,n\le 40,k\le 4$，且 $n\gt 20$ 的数据不超过 $2$ 组。 #### 题解 考虑类似最小生成树的求解过程，按边权从小到大依次加边。暂且抛开计算边权和不谈，求 $f_{t,i}$ 表示 $i$ 个点被不超过 $t$ 的边连通的概率。考虑从节点 $1$ 开始，考虑连通块拓展的过程，初始为 $1$ 点由不超过 $t-1$ 的边形成的连通块，再通过 $t$ 边接上一些由不超过 $t$ 的边形成的连通块。 考虑再维护一个转移系数 $g_{i,j}$，表示目前 $i$ 个点的连通块新加入 $j$ 个点的概率。按点数从小到大考虑，考虑到大小 $s$ 先用 $g$ 中小于 $s$ 的部分求出 $f_{t,s}$，再用 $f_{t,s}$ 更新 $g$。这正确是因为初始连通块至少包含 $1$ 点，因此接上的总大小不超过 $s$。 $f$ 的转移显然为 $f_{t,s}=\sum_{i=1}^s f_{t-1,i}\times g_{i,s-i}\times {s-1\choose i-1}$，即枚举初始连通块大小为 $i$。$g$ 转移时需要所有新连通块间边权大于 $t$，新连通块与初始连通块间边权不小于 $t$，且存在至少一条 $t$。同时由于大小相同的连通块无法区分，加入 $k$ 个 $s$ 时还要额外除以 $k!$，防止算重。具体转移式此处略去，容易发现该 DP 的总复杂度为 $O(kn^3\log n)$，瓶颈在求 $g$ 时每个 $(i,j)$ 枚举所有 $(s,k)$，而 $(s,k)$ 的数量为调和级数的 $O(n\log n)$。 考虑将最小生成树的边权和考虑进来，比较暴力的方式是在 $f,g$ 中加维，加入 $S$ 表示总边权和，转移只需要在 $g$ 内加入新连通块时额外加 $t$ 即可，其余转移会加上一个背包状物，答案为 $f_{k,n}$。由于 $S$ 为 $O(nk)$ 级别，这样总复杂度要乘上 $n^2k^2$，为 $O(k^3n^5\log n)$，比较爆炸。 对于这种转移复杂度较高的背包，可以考虑使用插值优化。具体地，不再在状态中维护 $S$，转而直接维护一个多项式 $F(x)=\sum_{S=0}^{nk} p_S\cdot x^s$，其中 $p_S$ 表示边权和为 $S$ 的概率。然而直接用多项式乘法转移还是慢，即使上科技也得多带 log。由于多项式次数为 $O(nk)$，直接取 $x\in[0,nk]$ 分别代入求出最终 $F_{k,n}(x)$ 的值，这样转移时只有数字的转移，单轮复杂度仍为 $O(kn^3\log n)$。最后对 $F_{k,n}(x)$ 插值求出系数即为答案，这里复杂度为 $O(n^2k^2)$，于是总复杂度优化到了 $O(k^2n^4\log n)$，可以通过。 ### J 开拓 #### 题意 交互。有一棵 $n$ 个点的树，每次可询问一个点集，得到其虚树叶子节点的编号和及其中之一的编号，还原整棵树。$n\le 1000$，询问次数不超过 $10^4$。 #### 题解 $10^4$ 大概是 $O(n\log n)$ 级别，这启发我们使用二分状物。首先第一次询问整棵树 $S$，可得到 $u$ 节点为叶子，以及目前叶子节点编号和 $x$。将 $u$ 放入待连边集合 $T$ 并从 $S$ 中删除得到 $S'$，同时更新 $x$ 为 $x-u$。 之后查询 $S'$ 得到新的叶子节点编号和 $y$。若 $x\ne y$ 则说明删去 $u$ 后产生了新的叶子 $v=y-x$，这时可从 $T$ 中找到若干 $v$ 的儿子，方式是二分出最短前缀使得 $S'$ 加上这个前缀后 $v$ 不为叶子，这可以通过一次询问判断。不断寻找直到不存在 $v$ 的儿子即可。由于每个点只会从 $T$ 中被找出一次，总次数是 $O(n\log n)$ 的，可能会由于中止寻找的那轮二分带点常数，然而还是能过的。 ## 10.02 时间分配有些问题，也不好说，反正由于水平等各种原因没时间做 T4 了。 ### T4 魔法相机 #### 题意 给出若干个区间 $[l,r]$，可选若干非负整数点 $p$，要求任意两点之间距离不小于 $s$，求最多能覆盖的区间个数。$n\le 2\times 10^5,s,r_i\le 10^9$。 #### 题解 考虑暴力 DP，设 $f_{x,i}$ 表示考虑了所有 $r\le x$ 的区间，此时最后一个点为 $i$ 最多能覆盖的区间个数。当从 $f_{x-1}$ 转移到 $f_x$ 时，有 $f_{x,x}=\max_{j=0}^{x-s}f_{x-1,j}$，之后枚举所有 $r=x$ 的区间，并对 $[l,x]$ 内的 $f_{x,i}$ 加一。 $n$ 次后缀容易使用线段树维护，然而前缀查最大值 $V$ 次太多了，无法接受。考虑寻找关键点，并只在这些点上转移。显然区间左端点 $l$ 均可能成为最值，然而这还不够，$l+m$ 处可能继承 $l$ 的信息，因此 $l+m$ 应该作为辅助点进行转移。然而辅助点也可能产生新的辅助点，数量还可能很多，还要优化。 考虑一个辅助点 $x$，若上个转移点为 $y$ 且 $f_x\le f_y$，则 $x$ 被 $y$ 支配，即之后 $f_y$ 一直不小于 $f_x$。证明考虑存在 $y\lt l\le x$ 的区间加时，$f_x$ 才可能变得比 $f_y$ 大，然而此时上个关键点变为 $l$，因此这种情况不存在。于是用堆维护所有转移点和区间，根据上述条件 $f_x\gt f_y$ 加入新点即可。 该做法正确性没有问题，然而关于时间复杂度，可以证明转移点的个数是 $O(n)$ 的，但我不太会证，感性理解是每 $O(1)$ 个点 $f$ 值就会增加，同时答案不超过 $n$。题解区有一些不太完整的证明，没看明白，不管了，总之用动态开点线段树可以做到 $O(n\log n)$。 #### 原题 [CF542B](https://www.luogu.com.cn/problem/CF542B)。 ### T5 小小的希望 #### 题意 给定一棵树，父亲数组 $f$ 满足 $f_{i-1}\le f_i\lt i$，$q$ 次询问区间 $[l,r]$ 内 LCA 仍在区间内的点对点权乘积之和，即 $\sum_{x=l}^{r}\sum_{y=l}^r [l\le L(x,y)\le r] a_xa_y$，强制在线。$n,q\le 2.5\times 10^5$。 #### 题解 由于 $f_i\lt i$，所以当 LCA 在区间内时，路径上的所有点均在区间内。因此区间内的点构成若干个连通块，每个连通块内两两选点均合法，贡献为 $(\sum a_i)^2$，所有连通块贡献和即为答案。另外还有 $f_{i-1}\le f_i$ 的限制，这说明树的节点编号形成 BFS 序。 考虑设 $t_i$ 表示 $i$ 点当前块的 LCA，$s_i$ 表示以 $i$ 为 LCA 的块 $a$ 的和。类似莫队移动端点，右端点改变时容易找到其对应 $t_i$ 并更新，复杂度 $O(1)$。然而左端点改变时需要合并新点的所有儿子，复杂度为 $O(d_i)$，其中 $d_i$ 为 $i$ 点度数。因此分块时除了要保证每块点数不超过 $B$，还需要保证 $\sum_{i=L+1}^r d_i\le B$。于是从后往前分块，每当某个限制爆掉就分成一个块。由于点数和 $\sum d$ 都是 $O(n)$ 的，总块数仍是 $O(\frac nB)$，可能要带上两倍常数。、 这时使用回滚莫队，每次先拓展右端点更新，再拓展左端点合并，实时维护当前 $\sum(\sum a_i)^2$ 即可。然而本题强制在线，考虑预处理全部 $O((\frac nB)^2)$ 对块间信息，每次取出信息再移动端点。需要知道的信息有右边块每个点的 $t_i$ 及 $s_{t_i}$，左边块每个点所有儿子的 $s_v$，共需要 $O(B)$ 的空间，可能有三四倍常数。取 $B=\sqrt n$ 可得理论最优时空复杂度 $O(n\sqrt n)$。然而空间常数过大炸掉了，卡不过去，于是开到 $B=1.55\sqrt n$ 后时空都极限过了，不管了。 ## 10.03 T3 应该想到括号树的，最大败笔。然而这两场都没挂分，爽了。 ### T3 数括号 #### 题意 有一个长为 $2n$ 的括号串 $s$，每次新增一条限制 $l,r$，表示最终括号序列中 $s_l,s_r$ 匹配，求每次增加限制后的合法括号序列数，保证有解。$n\le 5\times 10^5$。 #### 题解 考虑所有匹配的括号对，若其内部无匹配括号，则内部一定是合法括号序列，用卡特兰数即可计算。之后可删掉这些位置，又会产生新的极小括号对。这样一直做下去就能求出答案。 考虑该过程实际上在干啥，发现将所有已知配对建成括号树，之后每个点内所有不在其子树内的位置形成一个合法括号序列，可以用卡特兰数直接计算。然而正着向括号数中加匹配比较困难，考虑用最终括号序列建树，之后倒着删树上的点，每次需要找到其当前父亲并修改其位置数。用树上并查集即可实现该操作，时间复杂度 $O(n\alpha(n))$。 ### T4 异或数组 #### 题意 给定数组 $a$，保证 $0\le a_i\lt 2^m$。每次询问给出 $l,r$，求 $\max_{x=0}^{2^m-1}\min_{i=l}^r(x\oplus a_i)$。$n\le 10^5,q\le 5\times 10^5,m\le 50$。 #### 题解 考虑单次询问怎么做，可以建出 Trie 树并在上面 DP，若当前点只有一个子树，则该位可为 $1$，再递归进该子树求解；否则该位必为 $0$，可选择一个子树作为后面位的贡献。实现上类似树形 DP，时间复杂度 $O(nmq)$。然而这告诉我们最终答案一定在 Trie 树上（虽然事实上所选的 $x$ 应该恰好是该节点的补集），启发我们改为对每个 $a_i$ 考虑。 具体地，对每个 $a_i$ 统计答案，则需关注 Trie 中其到根的路径上所有点，若没有兄弟节点则该位可产生贡献。于是找出 $l_{i,k},r_{i,k}$ 表示 $i$ 两边最近的 Trie 树上第 $k$ 位邻居，当且仅当 $L\le l_{i,k}\le i\le r_{i,k}\le R$ 时选择 $a_i$ 会产生 $2^k$ 贡献。注意到若 $i$ 不在区间内则贡献一定不优，于是与 $i$ 有关的限制可以删去，只剩 $L\le l_{i,k}\le r_{i,k}\le R$。 $l,r$ 各有 $m$ 个限制，两边共有 $O(m^2)$ 种可能的限制情况，也就是 $O(m^2)$ 个 2-Side 矩形 checkmax，单点查询。这可以使用扫描线维护前缀修改并单点查，用树状数组可以做到 $O(nm^2\log n+q\log n)$。然而发现前一项很大而后一项不大，使用 $O(1)$ 修改 $O(\sqrt n)$ 查询的分块可以平衡到 $O(nm^2+q\sqrt n)$，可以通过。 ## 10.06 打得最好的一集。没挂而且暴力怎么过 $85$？反正 rk1，爽了。 ### T4 神谕 #### 题意 给出一棵广义线段树，对其进行区间加操作，询问某个点目前的标记值。$n,q\le 2\times 10^5$。 #### 题解 考虑用更简洁的方式刻画标记的加入和下传，关注 $l-1$ 和 $r+1$ 两条链，求出其 LCA，则 $l-1$ 到 LCA 路径上的点不在路径上的右儿子会被打标记，$r+1$ 同理。同时这些点到根的路径要下传标记，这可以找到两条链上有对应儿子的最深点，改为这两个点到根的路径清空标记，这会导致对其邻域打标记。 暂且放下实现不表，先分析一下标记下传的总次数。若 $u$ 点存在一个标记 $x$，则不管是直接加还是下传下来的，一定是某次在其兄弟子树内的操作导致的；同理若要下传 $u$ 点的标记，一定是某次在其子树内的操作导致的。因此下传的总标记数不超过 $2 \sum_{u}\min(s_{lc_u},s_{rc_u})$，其中 $s_u$ 表示 $u$ 子树内的操作次数。根据启发式合并的复杂度分析，这是 $O(q\log n)$ 级别的。 再来考虑实现，先对其树剖，再开两棵线段树分别维护链的左右儿子加。操作时直接在对应线段树上对某点到根的路径加，则**符合儿子限制**的点标记为 $w_{fa_u}-w_u$，这可以保证真正被打上标记的点在链外。 某个点到根的路径清空标记时，依次处理从根到该点的链。注意不能每次将标记下传给儿子，这会使复杂度退化到暴力，~~还比暴力多个 log~~。需要按带标记的点将链分成若干段，每段都对邻域加上比其深度小的标记和。所以线段树需要维护标记点位置，我的实现可能还需要维护前两个标记点，还要注意跨过轻边的处理。单次复杂度为 $O(\log n(\log n+c))$，其中 $c$ 为标记点个数。于是总复杂度为 $O(q\log ^2n)$，可以通过。~~细节一车，5k 代码写了一天~~。 ## 10.09 最大败笔是会 T4 但 MLE 了，之后还是要注意时空限制，避免失误。 ### T3 日历 #### 题意 有 $n$ 个 $m$ 位十进制数满足 $a_i=a_{i-1}+1\bmod 10^m$，存在若干已知位，构造一个合法的 $a_1$。$nm\le 10%^5$。 #### 题解 注意到从后往前第 $i$ 位每 $10^{i-1}$ 行会加一，于是超过 $\log_{10}n$ 的位最多只会加一次。考虑对后 $5$ 位暴力枚举所有合法的 $a_1$，则这些位上每个限制形如 $a_1\bmod 10^j$ 在一个区间内，差分即可判断合法性。 枚举合法 $x$ 后可算出在第 $h$ 行向前进位。这时再枚举进位到第 $w$ 列，要求 $(h,w)$ 右上角全为 $9$，右下角全为 $0$，第 $w$ 列在 $h$ 上方为 $x$，下方为 $x+1\bmod 10$，且所有行的前 $(w-1)$ 列均相同。一个角全为某数可以用前缀和预处理，其余可预处理每列的限制情况。时间复杂度 $O(P+nm)$，其中 $P=10^5$。 ### T4 奶龙哞叫 原题：[P11459](https://www.luogu.com.cn/problem/P11459)，题解见[【学习记录】凸优化](https://www.luogu.com.cn/article/gaqmmr3c)。 注意这种分治结构不用 $O(n\log n)$ 的空间，可以每层只分配两个 vector，在 $u$ 点处分别将下层的空间分给两个儿子使用，合并到 $u$ 后就用不到了。由于第 $i$ 层单个节点所用空间为 $O(\frac n {2^{i-1}})$，总空间复杂度只有 $O(n)$，在本题中为 $O(nL)$。 ## 10.11 整体还行，但 T3 犯唐写麻烦了，不然可能还能多冲点 T4 的。 ### T4 冒泡排序二合一 #### 题意 给定排列 $a$，$q$ 次询问对 $[l,r]$ 区间进行 $k$ 轮冒泡排序后，$x$ 值的位置或 $a_x$ 的值。$n,q\le 6\times 10^5$。 #### 题解 对于求 $x$ 值的位置，考虑转为两个 $01$ 序列，分别为 $b_i=[a_i\ge x]$ 和 $c_i=[a_i\gt x]$，对 $b,c$ 分别做 $k$ 轮冒泡排序后，两者不同的位置即最终 $x$ 的位置。此时若 $x$ 为 $b$ 中前 $k$ 个 $1$，则 $b$ 的第 $(k+1)$ 个 $1$ 不动，而 $c$ 的该位置作为第 $k$ 个 $1$ 移走了，于是有且仅有 $c$ 序列该位置前的 $0$ 最终在 $x$ 之前。 若 $x$ 不为 $b$ 中前 $k$ 个 $1$，则两序列该位置均不动，因此 $x$ 只会向左移动 $k$ 位。综上需要求区间内第 $k$ 个 $1$ 的位置，离线后按值从大到小扫描线，用树状数组维护 $01$ 序列并在上面二分即可，复杂度 $O((n+q)\log n)$。 对于求 $a_x$ 的值，显然若其在后 $k$ 个位置内，则一定是对应排名的数，即区间第 $r-k+1$ 大值。否则有 $x+k\le r$，考虑用 $[l,x]$ 的区间和减去 $[l,x-1]$ 的区间和。不难发现 $[l,x]$ 的区间和为 $[l,x+k]$ 区间内除前 $k$ 大外的和，证明可按 $[l,x+k]$ 区间第 $k$ 大转为 $01$ 序列，最终 $[l,x]$ 内一定没有 $1$，因此一定是所有 $0$ 的和。 实现上可以使用主席树查询区间第 $k$ 大以及对应的和，可以在线回答询问。时间复杂度也是 $O((n+q)\log n)$ 的。 ## 10.13 T4 太难了，拼尽全力无法战胜多项式做法/ll。结果两个 Div 都没人过，确实太难了。前边打得还行，没有挂分。 ### T4 圆周距离问题 #### 题意 $n$ 个点的环，相邻两点距离为 $1$。一种选点方式的代价定义为两两之间最短距离的最大值，求所有选 $k$ 个点的方式代价之和。$2\le k\le n\le 10^6$。 #### 题解 枚举代价 $x$，设 $f_x$ 表示代价不低于 $x$ 的方案数，则答案为 $\sum_{x=1}^{\lfloor \frac n2\rfloor } f_x$，每种方案的贡献拆成了多段。然而这个难求，考虑求出 $g_x$ 表示代价不超过 $x$ 的方案数，则有 $f_x={n\choose k}-g_{x-1}$，于是求 $g$ 即可。 环上比较难考虑，需要断环为链。考虑任取一个被选点放在 $0$ 处，之后将环放到 $[0,n-1]$ 上，求此时合法方案数。这样求出方案数后放回环中有 $n$ 种位置，然而每种方案还会被 $k$ 个点各计算一次，于是最后还要乘上 $\frac nk$。 当计算距离不超过 $x$ 的答案时，显然只能在 $[1,x],[n-x,n-1]$ 内选点，且两部分内部不会非法，只需考虑两部分之间的限制。若选了 $p\in[n-x,n-1]$ 点，则 $[p+x+1-n,p-x-1]$ 内无法选点。注意到左端点 $x+(p+1-n)$ 一定在 $[1,x]$ 内，且长度均为 $d=n-2x-2$。于是将 $[n-x,n-1]$ 整体向后平移 $x+1$ 格到与 $[1,x]$ 重合，之后考虑长为 $x$ 的选择。 将移过来的点看成黑点，本来在 $[1,x]$ 内的点看成白点。现要从 $x$ 个点中选 $(k-1)$ 个并染成黑白两色，要求黑点之后 $d$ 个不能是白点。于是枚举黑色变为白色的次数 $i$，一定有 $id\le x$。在开头放一个白点，结尾放一个黑点，强制分成 $(2i+2)$ 段，于是分段方案可用隔板法计算为 $k\choose 2i+1$。之后先从 $x$ 个点中删掉 $id$ 个分隔符，从剩下的位置里选出 $k-1$ 个位置，再将分隔符插回分界位置即可，方案数 $x-id\choose k-1$。 于是有 $g_x=\sum_{i=0}^{\min(\lfloor \frac xd\rfloor,\lfloor \frac {k-1}2\rfloor)} {x-id\choose k-1}{k\choose 2i+1}$，预处理阶乘即可单次 $O(1)$ 计算，枚举量是调和级数的 $O(n\log n)$，可以通过。 #### 原题 [AGC068A](https://www.luogu.com.cn/problem/AT_agc068_a)。 ## 10.16 T4 太难了，无法战胜，史哥太强了。整体还行，T5 看起来可补，~~之后有时间再说吧~~。有时间了，已补。 ### T4 放球程序 #### 题意 有 $n$ 个球和 $n$ 个盒，编号均为 $1$ 到 $n$，初始可任意将球放到盒内。要求对 $i$ 从 $1$ 到 $n$ 依次操作，每次拿出 $i$ 盒内的球并任意排列成 $p_k$，之后同时将所有 $p_j$ 球放到 $p_{j+1\bmod k}$ 盒中。给出最终每个球所在盒的编号 $a_i$，判断是否可能出现该最终局面。多组数据，$\sum n\le 2.5\times 10^5$。 #### 题解 发现顺序操作时自由度太高了，初值和过程中的排列顺序均难以确定，于是考虑倒着做，这样初始状态确定了。将状态用图表示，即球编号 $i$ 向所在盒编号 $a_i$ 连边，形成基环树森林。则对 $i$ 操作时**所有**指向 $i$ 的点均断开，再以任意顺序连成一个环；倒过来考虑时即找到一个环，将其断开并全部指向 $i$。 注意到上述两操作并不等价，原因是前者要求取**所有**指向 $i$ 的点，而后者没有限制这一点。仔细思考后发现只有两种情况合法，分别是 $i$ 点入度为 $0$ 或 $i$ 点在环上且入度为 $1$。前者可任意选环操作，后者必须选 $i$ 点所在的环，这对应操作前 $a_i=i$ 形成自环，会将其操作后环上前驱代表的球留在 $i$ 盒内。 于是出现了新的自由度：$i$ 点不在环上时可任意选环。猜想选 $i$ 所在连通块的环最优，手推发现选其他环时，除 $i$ 点外所有点的可操作性均不变；选所在连通块的环时，$i$ 点到环路径上入度只比限制多 $1$ 的点由不可操作变为可操作，其余点仍不变，于是这可能使局面变得更可操作，一定是最优的。 于是有了一个确定过程：从初始 $(i,a_i)$ 形成的图开始，倒序操作所有 $i$。每次先检查入度是否合法，不合法则无解；否则找到该连通块内的环，将其断开并全部指向 $i$，过程中修改入度。若能进行完 $n$ 次操作则有解。直接模拟该过程，暴力跳后继找环，复杂度可证明不超过 $O(n\sqrt n)$，~~事实上跑得[特别快](https://atcoder.jp/contests/agc068/submissions/70187813)~~，证明如下（By [Kevin090228](https://atcoder.jp/contests/agc068/editorial/11093)）： 每次操作遍历操作点到环路径上和环上的所有点。由于路径上的点在操作后会变到环上，只分析每次操作环长 $L$ 的总和即可，即复杂度为 $O(\sum L)$。设局面 $S$ 的势能 $V(S)=\sum r_i^2$，即所有点入度的平方和。操作会使环上点的入度减 $1$，势能减小 $\sum_{t\in C} r_t^2-(r_t-1)^2=\sum_{t\in C} 2r_t-1$，由于全局入度和为 $n$，这是不超过 $2n$ 的；同时操作点 $x$ 入度增加环长 $L$，势能增加 $(r_x+L)^2-r_x^2=2Lr_x+L^2$，这是不低于 $L^2$ 的。 由于势能 $V(S)$ 上界为 $n^2$ 且 $n$ 次操作总减小量不超过 $2n^2$，总增加量一定不超过 $3n^2$。忽略 $2Lr_x$ 这一项，有 $\sum L^2\le 3n^2$，根据柯西不等式可得 $\sum L$ 至多是 $n\sqrt n$ 级别的，于是复杂度 $O(\sum L)$ 不超过 $O(n\sqrt n)$。 还有另一种做法，考虑进一步刻画合法局面，注意到操作点 $i$ 时要求 $i$ 没有环外入度，因此对于 $i$ 点不在环上的前子树 $u$，若其所有点编号均小于 $i$，则 $i$ 点操作前该子树不变，$i$ 点会由于 $(u,i)$ 存在而无法操作，必然无解。于是对于每个点 $i$，其每个子树 $u$ 最大值 $w_u$ 均需满足 $w_u\gt i$，才有可能有解，这是一个必要条件。 至于充分性，感性理解若满足条件，则每个子树内都有点操作过，从而 $(u,i)$ 这条边曾被纳入环中，不再构成限制，因此 $i$ 点此时可以操作，不太会严格证明。总之这个条件是充要的，据此可判断合法性，DFS 即可找出环并求出所有 $w_u$，时间复杂度 $O(n)$，~~然而[没跑过](https://atcoder.jp/contests/agc068/submissions/70188270)上种做法~~。 #### 原题 [AGC068C](https://www.luogu.com.cn/problem/AT_agc068_c)。 ### T5 树上经典 #### 题意 给定一棵树，每个点有点权 $a_i$，$q$ 次询问树上 $x,y$ 两点间路径的所有点权中，取 $k$ 个可得的最大按位与值。$n\le 10^6,q\le 10^5,k\le 10,0\le a_i\lt 2^{62}$。 #### 题解 考虑给定若干数求最大值怎么做。对这些数建 01Trie，然后从高到低依次确定。每次若该位为 $1$ 的个数不低于 $k$ 个，则该位可取 $1$，进入 $1$ 子树；否则将 $1$ 子树中至多 $(k-1)$ 个元素去掉 $1$ 插入 $0$ 子树后进入 $0$ 子树，单次复杂度 $\mathcal O(n\log v+k\log ^2v)$，直接套上可持久化 01Trie 似乎也能做，没试。 事实上这个过程可以简化。具体地，我们只关心当前第 $k$ 大数当前位的情况，为 $1$ 则删掉所有该位为 $0$ 的数，否则将至多 $(k-1)$ 个当前位为 $1$ 的数当前位变为 $0$，使用 set 即可维护该过程，单次复杂度 $\mathcal O(k\log v\log c)$，其中 $c$ 为数字个数。 注意到过程中取 $0$ 时最大的至多 $(k-1)$ 个数被减小，于是只考虑前 $(k-1)\log v$ 大的数不会影响答案，因此求出链上这些值后套用上述做法即可做到单次 $\mathcal O(k\log v\log(k\log v))$。 至于如何求链上前 $c$ 大值，考虑维护一个链集合，初始只有 $(x,y)$。每次取出当前集合内链上最大值最大的链，并从最大值处将链分成两条新链放回集合。需要支持求链最大值，以及给出 $x,y$ 求链 $(x,y)$ 上 $y$ 的邻居。 两种查询使用树剖 + ST 表 / 倍增容易做到单次 $\mathcal O(\log n)$，这样总复杂度是 $\mathcal O(n\log n+qk\log v(\log n+\log (k\log v)))$ 的，瓶颈也在这个 $\log n$ 上。考虑将两种查询优化到单次 $\mathcal O(1)$，前者可以对原树建 Kruskal 生成树 / 笛卡尔树状物，之后用 DFS 序实现 $\mathcal O(1)$ LCA 即可。后者主要需要在 $y$ 为 $x$ 祖先时求 $x$ 在 $y$ 的哪个子树内，可重链剖分后对所有点与其轻子树内的点之间的询问预处理出答案，这样的对数为 $\mathcal O(n\log n)$。 于是两种查询都做到了时空 $\mathcal O(n\log n)$ 预处理 $\mathcal O(1)$ 查询，最终总复杂度是 $\mathcal O(n\log n+qk\log v\log (k\log v))$ 的。然而可能是由于 set 过慢，这个跑不过去。读了某题解后得知可以暴力遍历，理论复杂度为 $\mathcal O(n\log n+qk\log v(\log v+\log (k\log v)))$ 了，但只要初始不把 $(k-1)\log v$ 个数全求出来，而是用到时再去求，常数很小，可以通过。 #### 原题 [QOJ4909](https://qoj.ac/problem/4909)。 ## 10.18 T4 太难了，无法战胜。整体还行，T5 没看而且似乎比较思维，于是弃了。 ### T4 优美子数组 #### 题意 定义数组 $b$ 划分的优美值为每段和的绝对值最小值。给定数组 $a$，要求支持单点修改，查询区间最大优美值。$n,q\le 10^6$。 #### 题解 考虑优美值如何计算，分段方案的每一段均有正或负的权值，显然相邻段同号一定不优，可以将其合并，于是首先调整为正负交替。再注意到每相邻四段 $a,b,c,d$ 一定能将 $b,c$ 中绝对值较小的一个与两边合并，这也是不劣的。于是最终不超过三段。还能注意到此时若中间段绝对值不严格最大，则合成一整段更优。 综上，只能分一段（区间和），分两段（从前缀和最大最小值分开）或分三段且中间段绝对值严格最大。前两种均容易使用线段树维护，问题在于第三种的求解。考虑枚举分界线，钦定两个分界点在线两侧，则一定会选择从外侧起前 / 后缀和最值位置断开。 更具体地，对数组 $b_m$，其分三段正负正的最大优美值为 $\max_{i=0}^n(\min(p_i,s_{i+1}))$，其中 $p,s$ 分别表示前 / 后缀内前 / 后缀和的最大值，负正负同理。这显然能取到最优解，同时由于中间一段绝对值不最大时不优，这也不会比实际最优解大，于是这样求是对的。 根据定义，$p,s$ 分别不降和不增，于是最大值一定在两者图像交点处取到。具体地，若在序列上可对 $i$ 二分，找到第一个大小关系变化的位置。在线段树上可取出所有节点，先对这些位置二分出交点所在的段，再在线段树上进入该段二分，应该也能递归写，没试。总复杂度 $O(n+q\log n)$。 #### 原题 [P12554](https://www.luogu.com.cn/problem/P12554)。 ## 10.20 怎么四个全会，怎么挂了两个，被 corner case 爆了。离 AK 最近的一次，不过这也是为什么我们要认真处理细节，之后需要注意。