25.07-MX 模拟赛题解

· · 题解

风物长宜放眼量，心胸要开阔。

D1T1 琥峪枫

题意

交互。有一棵高度为 h 的完全二叉树和一个长为 n=2^h-1 的排列 p，点有点权 f_i。可询问 (u,d)，得到 \sum_{dis(p_u,v)=d}f_v，其中 dis(i,j) 表示 i,j 两点间路径边数，求 \sum f_i。多组数据，\sum n\le 10^6,1\le f_i\le 10^9，满分要求 q\le 2n+3，且同一个 u 询问不超过 4 次。

题解

设 A(u,d) 表示询问 (u,d) 的答案。考虑求出 \sum A(i,1)，其中根节点贡献两次，叶子节点贡献一次，其余节点均贡献三次，只需再求出根节点权值和叶子节点权值和即可求答案。考虑找到根节点 r，注意到由于权值为正，只有根节点的 A(r,h) 为 0，同理只有前两层 A(i,h+1) 为 0。因此只需询问一轮即可得到前两层的三个点。

之后对这三个点分别询问 A(i,h)，从而确定根节点 r 和另外两个第二层节点 x,y。同时叶子节点之和即 A(x,h)+A(y,h)，正好能用上。至于根节点权值，可以使用 \frac{A(x,1)+A(y,1)-A(r,2)}2 求出，其中前两项已经在开头求过了。

分析一下操作次数，A(i,1),A(i,h+1) 共 2n 次，A(i,h) 三次，加上 A(rt,2) 共 (2n+4) 次。然而注意到 A(i,h+1) 只用于筛选出三个点，因此只求 (n-1) 次就行，总次数降到 2n+3，可以通过。赛后好像被爆标到 2n-3 了，恐怖。

D1T2 篱莘龙

题意

在序列中选元素，能同时选 i,j 当且仅当 a_i<b_j。给出长为 n 的序列，对每个前缀求其中最多能选的元素个数。n\le 10^6，a_i,b_i 两两不同。

题解

注意到若 a_i>b_i 且 a_j>b_j，则一定有 a_i>b_j 或 a_j>b_i，因此 a>b 的最多选一个。若只选 a<b 的，则要求 \max a<\min b，可以枚举分界点 p，统计 a\le p<b 的个数求解。把这个扔上线段树可以做到 O(n\log n)。

再考虑选一个 A>B 的 (A,B)，以下称这种元素为询问，其余为贡献点，此时要求其余 a<B 且 b>A。将其放到 a,b 的坐标系上，则有且仅有 (B,A) 左上角的点能选。注意到询问间若有包含关系则可以删掉，剩余 B,A 一定均单调递增。

此时若新加一个贡献点 (x,y)，则 B>x 且 A<y 的询问答案加一。由于 B,A 均单增，贡献到的一定是一段区间，可以以 B 为下标建线段树维护。若新加一个询问 (B,A)，先判断是否存在 B'>B,A'<A 将其包含，有则无法加入，再删掉 B'<B,A'>A 的被包含询问即可。

这里求区间可对 A,B 各开一个 set 维护，同时维护增删，删除时线段树赋值 -\infin，现在还需求加入时被包含的贡献点数，即已存在的 x<B,y>A 数量。考虑差分思想，用总点数分别减掉 x>B 和 y<A 的点数，再加回两者均满足的点数。然而在坐标系中画图可以发现，若存在两者均满足的点，则一定存在只选贡献点的方案不劣于选该询问。因此可以忽略加回点的操作，这样若答案选择该询问则不受影响，反之也不会导致答案增大，是正确的。

因此二维偏序转化为了两个一维偏序，开两棵树状数组即可维护 x>B 和 y<A 的点数。前面还使用了两棵线段树和两个 set，可以以大常数 O(n\log n) 的时间复杂度通过本题。另外计算加入询问时的初值还有其他巧妙方法，也是在坐标系中分析某块没有点。还有先求出只用 a<b 的答案再分析能否加一的做法，只听了个大概，没有细想。

D2T1 流（谒醨溪）

题意

序列 a 需要满足 l_i\le a_i\le r_i，还有 m 条 a_{x_i}\oplus a_{y_i}=z_i 的限制，求字典序最小的合法序列。多组数据，n,m\le 2\times 10^5,\sum n,\sum m\le 4\times 10^5,0\le l_i,r_i,z_i<2^{30}。

题解

把限制看成边，连通块内的取值互相影响，即确定一个就确定了整个连通块，此时一定最小化最靠前的那个；而连通块间是独立的，可以分开计算。具体地，以最靠前的位置为根，DFS 一遍得到所有点与根的异或值 d_i，出现冲突则无解。设根节点值为 x，则每个点存在限制 l_i\le x\oplus d_i\le r_i，c 个点共 c 条限制。

现在需要求出 c 条限制下的最小合法 x，把每个限制拆成两个，这里以 x\oplus d_i\le r_i 为例。可以找出 Trie 树上 d_i\oplus r_i 到根的路径，再枚举两者 LCP，若该位可以满足条件，则该路径相邻的一棵子树均合法，对其打标记即可，另一种限制同理。建出访问过的 O(c\log V) 个点，最后遍历一遍，找到满足所有限制，即打了 2c 个标记的最小 x 作为根节点的值，其他点的值即为 x\oplus d_i，若不存在合法 x 则无解。时间复杂度 O(n\log V)。

D2T2 芳权多

题意

给出一个长为 n 的字符串，每次修改同时将其所有 "he" 子串改为 "she"，"his" 子串改为 "her"。q 次询问给出 k,x，求原串修改 k 次后的第 x 个字符。多组数据，T\le 5,n,q\le 2\times 10^5,k,x\le 10^9。

题解

先将查询按 k 排序，尝试维护操作后的串。注意到 "he" 只会每轮向前生成一个 's'，且本身不会消失；而 "hi" 碰到 's' 后会变为 "her"，该 's' 可能是原序列中的，也可能是后面的 "he" 生成的，且其改变后自身也可以向前生成 's'。因此比较重要的是 "hi" 变为 "he" 的操作，这里设 t_i 表示 i,i+1 位置的两个字符在第 t_i 轮变成 "he"，之后每轮产生一个 's'。若这两个字符不为 "he" 或 "hi"，则 t_i=\infin。"he" 的 t_i=0，"his" 的 t_i=1，其余 "hi" 需要后面给出 's'，即 t_i=t_{i+2}+2。

再按照 "he" 和 "hi" 将串划分成若干段，除第一段外每段都以 "he" 或 "hi" 开头。这样之后每段均形如若干 's' 加上一个串，后面的串总长为 O(n)。考虑直接记录下后面的串，并用线段树维护每个段的长度。令每个叶子节点代表一个段，c_u=1 表示该段已经可以产生 's'。每轮先给全局 c_u=1 的加一，再将 t_{L_i}=T 的单点 c 值改为 1，并修改 i 的串为 "her"。还要给后一个段单点减一，表示有一个 's' 放到前面凑成了 "his"，并变成了前一段内的 'r'。这是 "hi" 且不为 "his" 的修改方式，而其他 t_i\le 1，可以在开始前预处理。

这些操作均可使用线段树实现，维护一下区间 c 的和即可。询问时线段树上二分找到所在段，判断一下该字符是否为前缀 's'，不是则去记录的段里找字符。另外 "hi" 一定会在 n 轮内被激活，之后 c 轮操作可以直接全局加 c，这样操作次数降为 O(n+q)，时间复杂度 O(T(n+q)\log n)。还有用线段树维护一次函数的做法，感觉也是差不多的。

D2T3 染色

题意

二维平面上有 n 个黑点 (x_i,y_i)，其余点为白点。每次操作可任选两个整数 x,y，将 (x,y),(x,y+1),(x+1,y) 三个点的颜色取反。要求最后只剩一个黑点，求该黑点坐标，保证有解。1\le n\le 10^4,-10^{17}\le x_i,y_i\le 10^{17}。

题解

先考虑值域较小的情况。尝试将点转化到同一条线上，取 Y \le \min y_i 并选择 y=Y 这条横线。观察转化过程，发现点 (x_i,y_i) 会贡献到所有满足 {y_i-Y\choose t} 为奇数的点 (x_i+t,Y)。根据 Lucas 定理的结论，该限制等价于二进制下 t\subseteq (y_i-Y)。

若将答案 (x_0,y_0) 贡献到直线 y=Y 上，最靠边的贡献点分别满足 t=0 和 t=y_0-Y，即横坐标分别为 x_0,x_0+y_0-Y。于是将初始点暴力贡献到该横线上，再找到最靠边的黑点横坐标 L,R，答案即为 (L,R-L+Y)。时间复杂度 \mathcal O(nV)。

以上做法告诉我们，找到 y=Y 上最靠边的黑点横坐标 L,R 即可求出答案。由于所求 L,R 分别对应 t=0 和 t=y_0-Y，只需求出任意一个黑点横坐标 X，即可从高位到低位倍增求出 L,R。

具体地，对每个二进制位 2^k，若 (X-2^k,Y) 仍为黑点，则 y_0-Y 和当前 t 该位均为 1，需要更新 X\leftarrow X-2^k，最终得到的值即为 L。对 R 的求解是类似的，只需变减为加即可。判断某个点的颜色可以枚举所有初始点计算贡献，单次复杂度 \mathcal O(n)，总复杂度 \mathcal O(n\log V)。

于是目标变为找到横线上任意一个黑点。类似上题做法，对所有点按 (x-y)\bmod 3 划分等价类。每次操作三个等价类内各取反一个点，三者的黑点数奇偶性均改变。又因为最终状态只有一个黑点，每个状态下都存在黑点数为奇数的等价类。

在该横线上同样划分等价类，找到奇数个黑点的等价类 c，再对其不断二分，每次向奇数个黑点的一侧递归，即可找到一个黑点。

二分中需求解的问题为：给定 l,r,c，求初始点贡献到横线上后，[l,r] 区间内横坐标模 3 为 c 的黑点个数奇偶性。由于不关心具体个数，可对每个初始点分别求出贡献点数奇偶性。由于贡献点异或只会导致点数减少 2，这些奇偶性异或起来即为最终黑点数奇偶性。

于是分别对初始点 (x_i,y_i) 求 [l,r] 内有多少模 3 为 c 的 X 满足 (X-x_i)\subseteq (y_i-Y)。对 t=X-x_i 考虑，设 f_{k,liml,limr,c} 表示填了 2^k 及更高位，这些位上满足包含限制，是否仍然等于上下边界，当前值模 3 为 c 的数字个数奇偶性，直接数位 DP 即可，单次复杂度 \mathcal O(\log V)。

令 V=10^{17}，由于坐标绝对值不超过 V，可取 Y=-V。此时贡献点在 [-V,3V] 内，答案 x_0,y_0 满足 x_0\ge -V,x_0+y_0\le 2V，可推出 y_0\le 3V。若贡献到竖线 x=-V 同样可得 x_0\le 3V,y_0\ge-V，于是答案坐标在 [-V,3V] 之间，倍增和数位 DP 从 2^{58} 开始即可。

关于复杂度，瓶颈在于二分找任意黑点的 \mathcal O(n\log^2 V)，倍增求 L,R 的 \mathcal O(n\log V) 不在瓶颈上。提交记录。

D3T1 迷宫

题意

给出一棵树，边有边权 w_i。q 次询问给出 x,y，求 x 到 y 路径上边权的最长不下降子序列。n\le 10^5,q\le 3\times10^{6},w_i\le k\le10。

题解

暴力可以树剖，将路径剖成 O(\log n) 条重链，并用线段树之类的东西硬维护一下，可能需要至少 O(qk^3\log n)，难以通过，需要减少段数来消掉这个 \log n。然而在 LCA 处断开很不好做，考虑点分治并在分治中心处断开，这样总共要处理的点数降到 O(n\log n)，看起来比较能做。

因此先建出点分树，把每个询问挂到点分树上 LCA 处，在以其为分治中心时处理。点分治时只需要 DP 求出中心到各点开头为 i 的最长不上升 / 不下降子序列，之后枚举断点拼起来即可。这里实现有优劣，若枚举开头结尾是 O(sk^2) 的，总时间复杂度为 O(nk^2\log n+q(k+\log n))，据说有能消掉一个 k 的做法，没想。

D3T2 排列计数

题意

定义排列 P 中下标 i 是好的当且仅当 P_i>P_{i+1} 且 P_i 为前缀最大值，排列 P 的权值 f(P) 为其冒泡排序每一轮前好的下标数量之和。给出 m 条限制 p_{x}=y，求所有满足限制的排列权值之和，取模。0\le m\le n\le 10^6。

题解

考虑求给定排列的权值，注意到一轮冒泡排序会将每个前缀最大值移到下一个之前，而实际上会移动的只有好的下标上的数，因此可转化为求总移动次数。考虑计算每个数 p_i 会向后移动多少次，设 f_j=[p_j\ge p_i]，则 p_i 每次实际移动会跳过 f 上的一个 0 连续段。再考虑 i 前面元素的影响，显然 0 不会跳到 p_i 之后，1 也不会拆开原来的 0 连续段，因此跳的次数即为其后 0 连续段的个数，答案也是连续段个数之和。

考虑如何统计答案，先转化为计算 i 及之后 "10" 的出现次数，这里要求 i\le j<n,p_j\ge p_i,p_{j+1}<p_i，可以直接枚举 i,p_i=x,j，计算 p_j,p_{j+1} 的方案数，复杂度 O(n^3)。注意到很多东西只与 x 及合法位置 j 的个数有关，因此倒序枚举 i，并维护各种 j 的个数，复杂度降为 O(n^2)。再注意到位置 j 总是贡献到 x 的一段区间，且 p_i 给定时 x 取值唯一，否则可以任取没有给定的数，也即只有单点和全局查询。因此用树状数组维护单点的合法 j 个数，同时维护全局系数和即可，时间复杂度 O(n\log n)。本题关键在于注意到连续段性质，优化细节此处略去。

D3T3 白井黑子

题意

有一棵 n 个点的树，两个数组 f,a，f_i 初值为 i 的父亲节点。求该树的任意 DFS 序并存到 a 中，除两个数组外只有 0.75Mib 可用空间。n\le 10^7。

题解

注意到需要找到一种顺序遍历整棵树，使用左儿子右兄弟表示法，即维护每个点第一个儿子 a_i 和下一个兄弟 t_i。若有这两个辅助数组，可从 p=1 开始遍历，若当前 a_p=0 则说明 p 子树已遍历完，需要记录遍历完的顺序，可以直接记录在空的 a_p 中，之后跳到其下一个兄弟 t_p，若无则返回父亲 f_p；若 a_p 存在就直接跳到 a_p，并将 a_p 清空为 0。这样得到的 a 是树的后序遍历，倒过来即可得到一个 DFS 序。

这样需要 O(n) 的额外空间开数组，无法接受。注意到过程中只有每个点的最后一个儿子会跳到父亲，其 t_i 一定为空，同时其余节点遍历时用不到父亲，因此可将两个数组合并，只记录遍历过程中的下一个节点，即可满足空间限制。具体实现时直接用 f 数组作为 t，类似链式前向星，枚举每个点 i 和其父亲 x，若父亲已有儿子 a_x 则先以其为下一个兄弟，即令 f_i=a_x，并将 x 的第一个儿子改为 a_x；否则直接令 a_x=i，且保留其父亲信息。跑一遍后先用 a 中的排名还原出后序遍历存到 f，再翻转整个序列存到 a 即为答案。

总之这种题还是挺巧妙的，思维含量很高，代码也很好写，感觉和 D1T1 是差不多类型的题。

D4T1 弱

题意

在原点有一枚棋子，每次按照 w_u:w_d:w_l:w_r 的概率随机向上下左右中某个方向移动 1，共移动 n 次，求经过不同整点个数的方差。方差定义为 \sum p_i(i-E)^2，其中 p_i 表示经过 i 个不同点的概率，E 表示个数期望。n,w\le 100。

题解

以下设 S=\sum w。先推一推方差的式子，得到 \sum p_ii^2-2p_iiE+E^2=\sum p_ii^2-E^2，因此只需要求出个数期望和个数平方的期望即可。个数期望容易拆贡献，即对每一步走到新点的概率求和。这里先计算路径数，设 g_i 表示走 i 步后第一次到某个点的路径数，则有 g_i=S^i-\sum_{j=0}^{i-1}g_j\times A(i-j,0,0)，其中 A(i,x,y) 表示走 i 步到达 (x,y) 的路径数，该式在第一次到某点时统计或容斥。有 E=\sum_{i=0}^n \frac{g_i}{s^i}。

考虑同样把平方的期望拆贡献，则每条路径的贡献为 \sum_{0\le i\le j\le n}2t_it_j，其中 t_i=1 表示 i 在路径上，t_i=0 表示不在路径上。因此求出 C 表示所有不同点对均被经过的路径条数和，则 \sum p_ii^2=\frac {2C}{S^n}+E，其中 E 即 i=j 产生的贡献。 考虑设 f(i,x,y) 表示所有三元组 (j,u,v) 使得 j<i，且 j 步时首次到 (u,v)，i 步时首次到 (u+x,v+y) 的路径数总和。 所求即 C=\sum_{i=0}^n\sum_x\sum_y f(i,x,y)\times S^{n-i}。

考虑 f 的计算方式，首先赋值 f(i,x,y)=\sum_{j=0}^{i-1} g_j\times A(i-j,x,y)，但显然会多算一些东西，先减去多次访问 (u+x,v+y) 的重复贡献，即减去 \sum_{j=0}^{i-1}f(j,x,y)\times A(i-j,0,0)。再减去第 j 步到 (u,v) 前到过 (u+x,v+y) 的路径数，即减去 \sum_{j=0}^{i-1}g_j\times S(i-j,-x,-y)，其中 S(i,x,y) 表示走 i 步经过 (x,y) 后回到原点方案路径数。然而其中存在 j 步前到过 (u,v) 的路径，然而开始时保证了首次到 (u,v)，因此这些并不存在却被减了一次，需要加回 \sum_{j=0}^{i-1} f(j,x,y)\times S(i-j,-x,-y)，这样就计算完了。

最后需要解决 A,S 的计算，A(i,x,y) 可以枚举向上的步数 k，即可推出四个方向的步数，再用多重集排列算一下方案数，乘上对应的 w 次幂求和即可。而 S(i,x,y)=\sum_{j=0}^i R(j,x,y)\times A(i-j,-x,-y)，其中 R(i,x,y) 表示走 i 步首次到 (x,y) 的路径数，这样即在首次经过处统计。有 R(i,x,y)=A(i,x,y)-\sum_{j=0}^{i-1}R(j,x,y)\times A(i-j,0,0)，即在首次到 (x,y) 处容斥。最终所有转移均只枚举 j 一个值，且状态数为 O(n^3)，总复杂度 O(n^4)。

D5T1 最大公约数

题意

给出长为 n 的序列 a，每次操作可将相邻两数变为两者 gcd。q 次询问给出区间 [l,r]，求对该区间最少操作多少次能把数变为全相同，询问独立。n,V\le 10^5,q\le3\times 10^5。

题解

对于询问先求出区间 gcd 为 g，显然过程中的所有数一定均为 g 的倍数。设最终剩余数均为 kg，则若 k\ne 1，区间内一定存在一个数不为 kg 倍数，无法满足，因此最终一定得到若干个 g。考虑从左端点开始找到最小的 p，使得 [l,p] 的 gcd 为 g，将答案加一再更新 l\leftarrow p+1。如此直到 p>r，此时把 [l,r] 均划分进上一段即可。这样可求出最大段数，用区间长度减一下就是答案。

考虑如何快速求出该段数。[l,i] 的 gcd 形成至多 \log V 个连续段，因此记录三元组 (l,g,p) 表示 [l,p] 的 gcd 为 g，且 p 为该段开头。三元组共有 O(n\log V) 个，将其按照 g 分类，同时将询问也离线下来按照区间 gcd 分类。之后枚举 g，使用所有三元组建出倍增数组 f_{i,j}，表示从 i 开始往后接 j 个连续段的右端点，每个询问倍增跳一下即可。时间复杂度 O(n\log n\log V+q\log n)。

D5T2 杏酥桐

题意

维护一棵树，初始只有根节点 1。修改会增加一个新点，并将其插入到 u 点的子节点序列，作为其第 k 个儿子。查询时给出 u,x，询问对当前树进行 x 次左儿子右兄弟变换后 u 的父亲。询问独立，保证修改合法。多组数据，T\le 3,q\le 10^6,u\le n,x\le 10^9。

题解

先只考虑单次变换，此时若 u 为其父亲的第一个儿子则不变，否则父亲变为原父亲的上一个儿子。可以注意到之后每次变换时前者仍不变，后者会变成原父亲 DFS 序的后继，直到后继为 u 自身时不再改变。因此需要实时维护 DFS 序和每个点目前的子节点序列，从而求出某个点在其父亲的子节点序列中的前驱，以及 DFS 序上某个点之后第 k 个点。

实现时可以先记录下所有操作并建出树，在上面跑出 DFS 序，之后倒序确定每个点的位置，方式即对每个点维护目前还没被占的子节点位置，在上面找到对应位置并分配即可。最后正序处理每个询问，在 DFS 序上维护目前已产生的点，即可查询出某点后第 k 个点。以上均可以使用线段树维护区间点数，并使用线段树二分求解。另外查前驱只需要对每个点用 set 维护其目前存在的子节点即可，时间复杂度 O(Tq\log q)。