2023 年牛客多校第一场题解（上）_rmson

A Almost Correct

题意：给定长度为 $n$ 的 $01$ 串 $s$，构造一个排序网络，使得能够将除 $s$ 之外的任意 $01$ 序列正确排序，且 $s$ 无法被正确排序。$T$ 组测试，$1\le T\le 10^4$，$2\le n\le 16$。

解法：记 $01$ 串 $s$ 中 $0$ 所在位置的下标集合为 $S_0$，$1$ 所在位置的下标集合为 $S_1$（下标从 $1$ 开始）。令 $S_0$ 中最大值为 $r$，$S_1$ 中最小值为 $l$（显然 $l\le |S_0|<r$，因为 $s$ 没被排好序）。下简写一次操作为 $(x,y)$ 表示对 $a_x$ 与 $a_y$ 的比较与交换。对 $01$ 序列 $t$ 排序方法如下：

• 将 $S_0$ 中最大值挪到最右边，$S_1$ 中最小值挪到最左边，即执行 $\forall x\in S_0,(x,r)$ 和 $\forall x\in S_1,(l,x)$。
• 对 { 1 , 2 , 3 , ⋯   , n } − { l , r } = { 1 , 2 , ⋯ l − 1 , l + 1 , ⋯   , r − 1 , r + 1 , ⋯   , n } \{1,2,3,\cdots,n\}-\{l,r\}=\{1,2,\cdots l-1,l+1,\cdots,r-1,r+1,\cdots,n\} {1,2,3,⋯,n}−{l,r}={1,2,⋯l−1,l+1,⋯,r−1,r+1,⋯,n} 正常排序，即去掉下标 $l,r$ 对其他元素排序。
• 依次执行 $(r,|S_0|+1),(r,|S_0|+2),\dots ,(r,r-1),(r,n),(r,n-1),\dots ,(r,r+1)$ ，$(l,|S_0|),(l,|S_0|-1),\cdots ,(l,l+1),(l,1),(l,2),\cdots ,(l,l-1)$。

记 $t$ 中 $0$ 所在位置的下标集合为 $T_0$，$1$ 所在位置的下标集合为 $T_1$。上面的算法满足题目要求，证明如下：

• 当 $t=s$，第一步结束后 $t_l=1$ 且 $t_r=0$，显然第一步无效。第二步中 $t_l$ 和 $t_r$ 显然不变，其他元素已经排好序了。第三步只能将 $t_l$ 交换到 $t_{|S_0|}$，将 $t_r$ 交换到 $t_{|S_0|+1}$，因此排序后 $t$ 形如 $0\dots 001011\dots 1$，在零一分界线 $|S_0|$ 处恰有一对 $10$，因而未被正确排序；
• 当 $|T_0|\ge |S_0|$ 且 $t\ne s$，$S_1$ 中一定存在一个 $0$，因此经过第一步操作后 $t_l=0$，第二步操作后 $|S_0|$ 及其左边全为 $0$。第三步操作中，若 $t_r=0$，则 $t_r$ 会被交换到 $t_{|S_0|+1}$；若 $t_r=1$，则会被交换到 $t_n$。由于 $t_{|S_0|+1:r-1}{t}_{r+1:n}$ 在第二步时已经排好序，因此交换后 $t_{|S_0|+1:n}$ 有序，于是整个序列 $t$ 有序；
• 当 $|T_0|<|S_0|$ 时同理。

B Anticomplementary Triangle

题意：平面上给一个 $n$ 个点的凸多边形 $P_1{P}_2\dots ,P_n$，要求找到 $3$ 个点，使得这三个点构成的三角形的反互补三角形包含所有点（可以在边界上）。$1\le n\le 10^6$。

解法：乱搞题，目标是找到一个三角形使得面积极大。有很多不知道对不对但是能过的搞法，一种能证明的做法如下：

• 固定 $r=1$，找到两个点 $P_s,P_t(1<s<t\le n)$ 使得 $S_{△P_r{P}_s{P}_t}$ 最大；
• 尝试向左或者向右挪动 $P_r$，哪边能让 $S_{△P_r{P}_s{P}_t}$ 变大就往哪边挪。$P_r$ 挪到极大值后挪 $P_t$，$P_t$ 挪到极大值后挪 $P_s$，$P_s$ 挪到极大值后挪 $P_r$，直到没有一个点能动。

在第一步结束后，只有 $r$ 能够移动。假设 $r$ 逆时针移动，这之后 $r,s,t$ 就只能逆时针移动，并且 $r,s,t$ 中任何一个点无法重新移动到 $P_1$，因为 $S_{△P_r{P}_s{P}_t}$ 在移动过程中递增，并且第一步得到的 $S_{△P_1{P}_s{P}_t}$ 已经是最大的。因此时间复杂度不超过 $O(n)$。

C Carrot Trees

题意：给一个长为 $n$ 的序列，初始状态全为 $0$。有两种操作，第一种将区间 $[l,r]$ 内的数均增加 $x$，第二种对区间 $[l,r]$ 内的每个数如果大于或等于 $k$ 就减去 $k$（$k$ 在所有操作中相等）。你需要执行 $m$ 次操作，输出执行完所有操作后所有数一共被减了多少次。$1\le n\le 10^6$，$1\le m\le 2\times 10^5$，$1\le x,k\le 10^9$。

解法：考虑某个位置上的数。将第 $i$ 次操作后的数表示成 $a_i=c_i+k\cdot b_i$ 的形式（$b_0=c_0=0$），其中 $b_i$ 代表了借位操作次数。考虑如下的一个暴力算法：对于操作一，直接令 $c_{i+1}=c_i+x$。对于操作二，若 $a_i\ge k$（即 $c_i+k{b}_i\ge k\Rightarrow c_i-k\ge -k{b}_i$），则令 $c_{i+1}=c_i-k$；否则令 $c_{i+1}=c_i-k$ 且 $b_{i+1}=b_i+1$。

引理：使用上述算法计算，所有操作后 $b_m=\lceil -\frac{{\min }_i{c}_i}{k}\rceil$。

证明：经过一次操作一，$c_{i+1}\ge c_i$，则 ${\min }_{1\le j\le i}{c}_j={\min }_{1\le j\le i+1}{c}_j$，因而 $b_i=b_{i+1}$，与上述算法执行过程相同。考虑操作二的两种情况：

1. 当 $a_i\ge k$ 时，有 $c_{i+1}=c_i-k\ge -k{b}_i$，因而 $b_{i+1}=b_i\ge -\frac{c_i}{k}+1\ge \lceil -\frac{c_i}{k}\rceil$。显然 $c_{i+1}<c_i$，由数学归纳法可得若 $b_i=\lceil \frac{{\max }_{0\le j\le i}(-c_j)}{k}\rceil$ 成立则 $b_{i+1}=\lceil \frac{{\max }_{0\le j\le i+1}(-c_j)}{k}\rceil$ 成立，即 $b_{i+1}=\lceil -\frac{{\min }_j{c}_j}{k}\rceil$。
2. 当 $a_i<k$ 时，$0\le c_i+k{b}_i<k$ 可得 $c_i\ge -k{b}_i$。由此时的操作 $b_{i+1}=b_i+1$ 可得 $c_i\ge -k-k{b}_{i+1}$，则与第一种情况证明方法相同。

由该引理可知，因此 $a_i$ 减少的次数一共为 $t-b_m=t+{\min }_i\lfloor \frac{c_i}{k}\rfloor$（其中 $t$ 为操作二的次数）。

因而本题转化为转化为区间加、单点查询历史最小值，可以参看https://oi-wiki.org/ds/seg-beats/的处理方法，或者使用线段树分治的思想。总时间复杂度 $O(n\log m)$。

D Chocolate

题意：有一个 $n\times m$ 的网格，每格放了块巧克力。Walk Alone（懵哥）和 Kelin 轮流吃巧克力，Kelin 先吃。每轮一个人能选择一个左下角为 $(1,1)$ 的子矩形，把里面的巧克力吃光，且至少要吃一个。吃到最后一个巧克力的人输。问懵哥和 Kelin 谁赢。$T$ 组测试数据，$1\le T\le 10^5$，$1\le n,m\le 10^9$。

解法：当 $n=m=1$ 显然懵哥赢。当 $n>1$ 或 $m>1$，假设 Kelin 第一步吃 $(1,1)$ 并且懵哥赢了，那么 Kelin 可以抢先走懵哥的必胜态且不改变局面（因为 $(1,1)$ 被任意子矩形包含），因此 Kelin 必胜。

E Heap

题意：给定一个以 $1$ 为根的有根树，点个数为 $n$，每个点有点权 $a_i$。现要求给每个点重新赋点权 $b_i$，且要求 $b_{p_i}\le b_i$，其中 $p_i$ 为 $i$ 的父亲。输出最小的 $\sum _{i=1}^n(a_i-b_i{)}^2$。$1\le n\le 2\times 10^5$，$0\le a_i\le 10^9$。

解法：本题主要使用到了 Slope Trick 的方法。

首先我们研究一个简单一些的题目，并从该弱化版的题目中得到本题真正的做法。

弱化版题目：给定一个以 $1$ 为根的有根树，点个数为 $n$，每个点有点权 $a_i$。现要求给每个点重新赋点权 $b_i$，且要求 $b_{p_i}\le b_i$，其中 $p_i$ 为 $i$ 的父亲。输出最小的 $\sum _{i=1}^n|a_i-b_i|$。$1\le n\le 2\times 10^5$，$0\le a_i\le 10^9$。

用 $g_u(x)$ 表示保证以 $u$ 为根的子树满足所有父节点权值小于等于子节点，并且使得 $u$ 的权值恰好为 $x$ 的最小代价；$f_u(x)$ 表示使得 $u$ 的权值至少为 $x$ 的最小代价，即 $f_u(x)={\min }_{y\ge x}{g}_u(y)$。可以得到以下转移：
$$g_u(x)=|x-a_u|+\sum _{v\in {\text{son}}_u}{f}_v(x)$$
首先需要证明引理 1：

$f_u(x)$ 是一个可导且单调递增的函数，且形如 $f_u(x)=c_u+\sum _{i\in S_u}r(x-i)$，其中：

1. $r(x-a_u)=\mathrm{ReLU}(x-a_u)=(x-a_u)[x\ge a_u]$，其中 $[x\ge a_u]$ 为艾弗森括号，表示当 $x\ge a_u$ 时值为 $1$，反之为 $0$。
2. $S_u$ 为 $u$ 节点子树中全部 $a_u$ 构成的可重集合。
3. $c_u$ 为一确定常数。

证明：递增性显然成立，下面使用数学归纳法证明该结论。

首先我们考虑叶节点 $g_u(x)$ 与 $f_u(x)$ 的形式——$g_u(x)=|x-a_u|$，$f_u(x)=r(x-a_u)=(x-a_u)[x\ge a_u]$，因而 $f_u(x)$ 是一个单调递增且可导的函数，且符合归纳形式。
注：$\mathrm{ReLU}$ 函数在 $x=0$ 处严格意义上不可导，但是为方便后文的表述，不妨定义 $r^{\prime }(0^{+})=1$。

对其余非叶节点，$g_u(x)=|x-a_u|+\sum _{v\in {\text{son}}_u}{f}_v(x)$。由可导函数相加还是可导函数，$g_u(x)$ 也同样可导，且 $c_u+\sum _{i\in S_u}r(x-i)$ 形式具有可加性。对其做后缀 $\min$ 操作，则 $|x-a_u|\to r(x-a_u)$，因而 $f_u(x)$ 同样符合原形式。归纳得证。

考虑将 $f_u(x)=c_u+\sum _{i\in S_u}r(x-i)$ 带入原转移式：
g u ( x ) = ∣ x − a u ∣ + ∑ v ∈ s o n u c v + ∑ v ∈ s o n u ∑ i ∈ S v r ( x − i ) = ( − x + a u + 2 r ( x − a u ) ) + ∑ v ∈ s o n u c v + ∑ v ∈ s o n u ∑ i ∈ S v r ( x − i ) = − x + a u + ∑ v ∈ s o n u c v + ∑ i ∈ S u ′ r ( x − i )

$$\begin{aligned} g_u(x)&=|x-a_u|+\sum_{v\in{\rm son}_u}c_v+\sum_{v\in{\rm son}_u}\sum_{i\in S_v}r(x-i) \\[3pt] &=(-x+a_u+2r(x-a_u))+\sum_{v\in{\rm son}_u}c_v+\sum_{v\in{\rm son}_u}\sum_{i\in S_v}r(x-i) \\[3pt] &=-x+a_u+\sum_{v\in{\rm son}_u}c_v+\sum_{i\in S_u'}r(x-i) \end{aligned}$$ gu​(x)​=∣x−au​∣+v∈sonu​∑​cv​+v∈sonu​∑​i∈Sv​∑​r(x−i)=(−x+au​+2r(x−au​))+v∈sonu​∑​cv​+v∈sonu​∑​i∈Sv​∑​r(x−i)=−x+au​+v∈sonu​∑​cv​+i∈Su′​∑​r(x−i)​
其中 S u ′ = ⋃ v ∈ s o n u S v ∪ { a u , a u } S_u'=\bigcup_{v\in{\rm son}_u}S_v\cup\{a_u,a_u\} Su′​=⋃v∈sonu​​Sv​∪{au​,au​}。不妨对 $g_u(x)$ 求导，当导函数第一次大于等于 $0$ 时，$x=\min S_u^{\prime }$。令 $x_0=\min S_u^{\prime }$，当 $x=x_0$ 时 $g_u(x)$ 取到最小值 $a_u-x_0+\sum _{v\in {\mathrm{son}}_u}{c}_v$，因此令
S u = S u ′ − { x 0 } c u = a u − x 0 + ∑ v ∈ s o n u c v $$\begin{aligned} S_u &= S_u'-\{x_0\} \\[3pt] c_u &= a_u-x_0+\sum_{v\in{\rm son}_u}c_v \end{aligned}$$ Su​cu​​=Su′​−{x0​}=au​−x0​+v∈sonu​∑​cv​​
当 $x\ge x_0$ 时有
$$\begin{array}{rl}{f}_u(x)& =g_u(x)\\ & =-x+x_0+c_u+\sum _{i\in S_u^{\prime }}r(x-i)\\ & =r(x-x_0)-x+x_0+c_u+\sum _{i\in S_u}r(x-i)\\ & =c_u+\sum _{i\in S_u}r(x-i)\end{array}$$
当 $x<x_0$ 时，由于 $f_u(x)$ 是 $g_u(x)$ 的后缀 $\min$，因而
$$f_u(x)\equiv c_u+\sum _{i\in S_u}r(x-i)=c_u$$
用优先队列维护 $S_u$ 做启发式合并可以做到 $O(n{\log }^{2}n)$。

接下来我们回到原问题，即目标函数为平方代价。

用 $g_u(x)$ 表示保证以 $u$ 为根的子树满足所有父节点权值小于等于子节点，并且使得 $u$ 的权值恰好为 $x$ 的最小代价；$f_u(x)$ 表示使得 $u$ 的权值至少为 $x$ 的最小代价，即 $f_u(x)={\min }_{y\ge x}{g}_u(y)$。可以得到以下转移：
$$g_u(x)=(x-a_u{)}^2+\sum _{v\in {\text{son}}_u}{f}_v(x)$$

用上面同样的方法，可以得到

$$f_u(x)=c_u+\sum _{i\in S_u}(x-i{)}^2[x\ge i]$$

其中 $S_u$ 仅为关于 $u$ 的集合。这时形式较为复杂，对其做后缀 $\min$ 操作难度较大。但是我们可以研究它的导函数以研究它的极小值情况。对转移式两边求导有
$$g_u^{\prime }(x)=2(x-a_u)+\sum _{v\in {\mathrm{son}}_u}{f}_v^{\prime }(x)$$
其中 ${\text{son}}_u$ 表示 $u$ 的儿子集合。根据上面同样的方法，显然 $f_u(x)$ 是一个连续、递增、下凸的分段函数，因此 $f_u^{\prime }(x)\ge 0$，且由 $f_u(x)={\min }_{y\ge x}{g}_u(y)$ 可得

f u ′ ( x ) = max ⁡ { g u ′ ( x ) , 0 } f'_u(x)=\max\{g'_u(x),0\} fu′​(x)=max{gu′​(x),0}
用可重集合 $S_u\subseteq \mathbb{R}\times \mathbb{N}$ 维护 $f_u^{\prime }(x)$ 的所有拐点以及拐点两侧的斜率差。下用同样的方法证明 $f_u^{\prime }(x)=\sum _{(i,\delta )\in S_u}\delta \cdot \mathrm{ReLU}(x-i)$。

证明：同样引入 $r(x)=x\cdot [x>0]$，假设 $u$ 的所有儿子节点 $f_v^{\prime }(x)$ 都能表示成以下形式：

$$f_v^{\prime }(x)=\sum _{(i,\delta )\in S_v}\delta \cdot r(x-i)$$
代入 $g_u^{\prime }(x)$ 的转移式可得
g u ′ ( x ) = 2 ( x − a u ) + ∑ v ∈ s o n u ∑ ( i , δ ) ∈ S v δ ⋅ r ( x − i ) = − 2 a u + 2 x + ∑ ( i , δ ) ∈ S u ′ δ ⋅ r ( x − i )

$$\begin{aligned} g'_u(x)&= 2(x-a_u)+\sum_{v\in{\rm son}_u}\sum_{(i,\delta)\in S_v}\delta\cdot r(x-i) \\[3pt] &= -2a_u+2x+\sum_{(i,\delta)\in S'_u}\delta\cdot r(x-i) \end{aligned}$$ gu′​(x)​=2(x−au​)+v∈sonu​∑​(i,δ)∈Sv​∑​δ⋅r(x−i)=−2au​+2x+(i,δ)∈Su′​∑​δ⋅r(x−i)​
其中 $S_u^{\prime }={\bigcup }_{v\in {\mathrm{son}}_u}{S}_v$。显然 $g_u^{\prime }(x)$ 单调递增，且存在唯一零点 $x_0$。考虑由于求后缀 $\min$ 使得 $x_0$ 处增加的拐点 $(x_0,g_u^{\prime \prime }(x_0^{+}))$，令
$$S_u=\{(i,\delta )\in S_u^{\prime }\mid i>x_0\}\cup (x_0,g_u^{\prime \prime }(x_0^{+}))$$
则 $f_u^{\prime }(x)=\sum _{(i,\delta )\in S_u}\delta \cdot r(x-i)$，归纳假设成立。

记 $f_u(x)$ 与 $g_u(x)$ 的最小值为 $C_u$。不难注意到，当子树中存在拐点 $(i,\delta )$ 有 $i\le x_0$ 时，由于已经在 $x_0$ 极其左侧取得最小值，因而 $x_0$ 左侧的全部拐点都可以删去。在寻找这样的 $x_0$ 时，可以依次枚举 $S_u^{\prime }$ 中相邻的拐点，找到零点存在的区间然后求出 $x_0$，再删去左侧的拐点。

由于 $g(x)$ 的极小值在 $x_0$ 处取到，代入 $g_u(x)$ 的转移式可得
C u = ( x 0 − a u ) 2 + ∑ v ∈ son u f v ( x 0 ) = ( x 0 − a u ) 2 + ∑ v ∈ son u C v + ∑ v ∈ son u ∫ − ∞ x 0 f v ′ ( x )   d x

$$\begin{aligned} C_u&= (x_0-a_u)^2+\sum_{v\in \text{son}_u}f_v(x_0) \\[3pt] &= (x_0-a_u)^2+\sum_{v\in \text{son}_u}C_v+\sum_{v\in \text{son}_u}\int_{-\infty}^{x_0} f'_v(x)\,\text{d}x \end{aligned}$$ Cu​​=(x0​−au​)2+v∈sonu​∑​fv​(x0​)=(x0​−au​)2+v∈sonu​∑​Cv​+v∈sonu​∑​∫−∞x0​​fv′​(x)dx​
通过启发式合并可以在 $O(n{\log }^{2}n)$ 的时间内求出所有集合 $S_u$ 与每个函数对应的最小值 $C_u$。总时间复杂度 $O(n{\log }^{2}n)$。

F Intersection

题意：平面上有 $n$ 个圆 $C_1,C_2,\dots ,C_n$，要求画一个圆 $O$（或直线）经过尽可能多的圆。$1\le n\le 150$，坐标范围 $0\le |x|,|y|\le 10^3$。

解法：当 $n\le 3$ 时答案为 $n$。当 $n>3$ 时，最优解一定能通过调整使得与至少两个圆外切。枚举 $i,j(i\ne j)$，假设圆 $O$ 与 $C_i,C_j$ 外切，求 $O$ 最多能与多少 $C_k$ 相交。

记 $C_i,C_j$ 的半径分别为 $r_i,r_j$，圆心分别为 $o_i,o_j$（用复数表示）。假设对复平面进行反演映射 $f(z)=1/(z-o)$，则反演后 $C_i$ 的圆心和半径分别变为

o i ′ = 1 2 ( 1 o i − r i e − o + 1 o i + r i e − o ) = o i − o ( o i − o ) 2 − ( r i e ) 2 r i ′ = 1 2 ∣ 1 o i − r i e − o − 1 o i + r i e − o ∣ = r i ( o i − o ) 2 − ( r i e ) 2

$$\begin{aligned} o_i'&=\frac{1}{2}\Big(\frac{1}{o_i-r_ie-o}+\frac{1}{o_i+r_ie-o}\Big) \\ &=\frac{o_i-o}{(o_i-o)^2-(r_ie)^2} \\[6pt] r_i'&=\frac{1}{2}\bigg|\frac{1}{o_i-r_ie-o}-\frac{1}{o_i+r_ie-o}\bigg| \\ &=\frac{r_i}{(o_i-o)^2-(r_ie)^2} \\ \end{aligned}$$ oi′​ri′​​=21​(oi​−ri​e−o1​+oi​+ri​e−o1​)=(oi​−o)2−(ri​e)2oi​−o​=21​ ​oi​−ri​e−o1​−oi​+ri​e−o1​ ​=(oi​−o)2−(ri​e)2ri​​​

其中 $e=(o_i-o)/|o_i-o|$。类似地可以计算 $C_j$ 的圆心和半径。令反演后 $C_i^{\prime }$ 与 $C_j^{\prime }$ 圆心位置相同，可以得到

$$\frac{o_i-o}{(o_i-o{)}^2-(r_{i}e{)}^2}=\frac{o_j-o}{(o_j-o{)}^2-(r_{j}e{)}^2}$$

解得 $A{o}^2+Bo+C=0$，其中
A = o i − o j B = ( r i 2 − r j 2 )   e 2 − ( o i 2 − o j 2 ) C = ( o i r j 2 − o j r i 2 )   e 2 + o i o j ( o i − o j )

$$\begin{aligned} A&= o_i-o_j \\ B&= (r_i^2-r_j^2)\,e^2-(o_i^2-o_j^2) \\ C&= (o_ir_j^2-o_jr_i^2)\,e^2+o_io_j(o_i-o_j) \end{aligned}$$ ABC​=oi​−oj​=(ri2​−rj2​)e2−(oi2​−oj2​)=(oi​rj2​−oj​ri2​)e2+oi​oj​(oi​−oj​)​
取圆 $C_i$ 内部的点 $o$，则反演后除 $C_i,C_j$ 外的所有圆都在 $C_i$ 内部、$C_j$ 外部，且 $O$ 与 $C_i$ 内切，与 $C_j$ 外切。对于每个圆 $C_k$，可以计算出 $O$ 与 $C_k$ 相交时 $C_{i}O$ 的辐角取值区间，通过扫描线可以求出最多相交的圆的数量。总复杂度 $O(n^3\log n)$。

G LCRS Transform

题意：给出一种对 $n$ 个点的二叉树有根树（树根在 $1$）的操作：

• 由深到浅的遍历树上的每个节点 $u$，将 $u$ 的右儿子 $r_u$ 变为 $u$ 的左儿子 ${\ell }_u$ 的右儿子。
• 然后对于所有只有右儿子没有左儿子的节点，将其右儿子变为左儿子。

问进行 $k$ 次操作后有多少棵树能变成给定的树。$1\le n\le 10^5$，$0\le k\le 10^5$。

解法：注意到每次操作后树的前序遍历不变，因此可以用前序遍历对所有点重新标号。这样标号后点 $u$ 的左儿子 ${\ell }_u$ 满足 ${\ell }_u=u+1$，且每次操作后边 $(u,r_u)$ 会变为 ( min ⁡ { u + 1 , r u − 1 } , r u ) (\min\{u+1,r_u-1\},r_u) (min{u+1,ru​−1},ru​)——$u+1$ 对应第一个操作，$r_u-1$ 对应第二个操作（若执行第二个操作此时满足 $r_u-1=u$）。$k$ 次操作后变为 ( min ⁡ { u + k , r u − 1 } , r u ) (\min\{u+k,r_u-1\},r_u) (min{u+k,ru​−1},ru​)。

考虑 $k$ 次操作后的树最开始的样子。考虑两种边：

1. 对于操作完成之后的树上的每条满足 $r_u>u+1$ 的边 $(u,r_u)$，最开始的树中一定存在边 $(u-k,r_u)$——每一次变化都是执行了 $u\leftarrow u+1$。因而需要保证此时的 $u>k$ 且这些边对应的“区间”不相交（这里定义两条边 $(x,y)$ 与 $(\ell ,r)$ 相交为 $\ell \le x<r<y$ 或 $x<\ell <y\le r$），否则答案为 $0$，因为这样就无法建立一条 $u\to r_u$ 的边。
2. 对于满足 ${\ell }_u=u+1$ 条件的边 $(u,{\ell }_u)$，最开始的边可以为 $(u-i,{\ell }_u)(0\le i\le k)$，表示这条边在第 $i$ 步开始就从连接右儿子变成连接左儿子，然后相对关系不再变化。

于是这道题等价于：一个长度为 $n$ 的线段中给定一些长度大于 $k$ 的区间，要求在其中添加一些长度不超过 $k$ 的区间，使得所有区间互不相交，问一共有多少种方案。

显然新添加的区间不可能跨过给定的区间，因此可以认为这些给定的区间把整个线段划分为了若干段，单独考虑每一段的贡献。令 $f_i$ 表示长度为 $i$ 的区间的方案数，其中 $f_0=f_1=1$。对于 $i\ge 2$ 有
f i = f i − 1 + ∑ l = 2 min ⁡ { k + 1 , i } f i − l ⋅ f l − 2 f_i=f_{i-1}+\sum_{l=2}^{\min\{k+1,i\}}f_{i-l}\cdot f_{l-2} fi​=fi−1​+l=2∑min{k+1,i}​fi−l​⋅fl−2​
令 $g=\sum _{i=0}^{k+1}{f}_i{x}^i$。当 $i\le k+1$ 时 $g$ 有生成函数等式：
$$g=xg+x^2{g}^2+1$$
解得
$$g=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}$$
此时通过多项式求逆求出 $f$ 数组的前 $k+1$ 项，即得到了递推的系数项。考虑对于 $i>k+1$ 时递推式可化简为 $f_i=f_{i-1}+\sum _{l=2}^{k+1}{f}_{i-l}\cdot f_{l-2}$，转写成多项式形式为：
$$f=fx+fg{x}^2+1$$
即 $f=\frac{1}{1-x-g{x}^2}$。可以用多项式求逆和多项式开方在 $O(n\log n)$ 时间内求解。

H Matches

题意：给定两个长度为 $n$ 的序列 { a } i = 1 n \{a\}_{i=1}^n {a}i=1n​ 和 { b } i = 1 n \{b\}_{i=1}^n {b}i=1n​，现在可以选择其中一个序列交换其中的两个数字，问经过至多一次操作后最小的 $\sum _{i=1}^n|a_i-b_i|$。$1\le n\le 2\times 10^5$，$0\le |a_i|,|b_i|\le 10^{12}$。

解法：考虑交换 $a_i,a_j$ ，不妨设 $a_i<a_j$ ，则交换前后的贡献差 $\Delta =|a_i-b_i|+|a_j-b_j|-|a_j-b_i|-|a_i-b_j|$ ，即最大化 $\Delta$ 。

下面使用一张图来给出最大化 $\Delta$ 的条件。首先定义：

1. 对于一对 $(a_x,b_x)$ 和 $(a_y,b_y)$，不妨设 $a_x<b_x$，若 $b_y<a_y$ 则称他们成反序关系，若 $a_y<b_y$ 则为正序。
2. 若一对 $(a_x,b_x)$ 与 $(a_y,b_y)$ 在数轴上覆盖范围有重叠，且存在独占一段的情况，称为相交。
3. 若一对 $(a_x,b_x)$ 与 $(a_y,b_y)$ 在数轴上覆盖范围有重叠，一段完全包络另一段，称为包络。
4. 若一对 $(a_x,b_x)$ 与 $(a_y,b_y)$ 在数轴上覆盖范围没有重叠，称为不交。

不难注意到：

1. 正序相交=正序包络
2. 正序不交<反序包络
3. 反序不交<反序相交

即将反序相交、反序包络进行交换即可。

不难注意到，我们经过一次交换不同种类（正序和反序）的区间，可以消除两倍的重叠（包络）长度。

具体到做法，首先考虑将所有区间一起按右端点（$\max (a_i,b_i)$）排序，按右端点递减的顺序依次枚举每个区间。假设当前枚举的区间满足 $a_i<b_i$，这个时候用一个变量 $l_T$ 维护已经枚举过的区间里面所有满足 $a_j>b_j$ 的区间中最小的左端点 $b_j$，不难发现如果 $b_j<a_i$，则现在的重叠区间长度为 $b_i-\max (a_i,b_j)$；对于 $a_i>b_i$ 的同理可以维护 $l_S$。

最后答案即为原始答案减去二倍的最大重叠区间长度。总时间复杂度为 $\mathcal{O}(n\log n+n)$。