本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-04 19:59:48

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

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