本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-29 23:00:58

:::::info[题目基本信息] 考察：倍增（省选/NOI-）。
题目简介：
你有 $n$ 个点，它们有点权，初始时它们间没有连边。
你需要进行 $m$ 次操作或查询：

• 操作：给两个不联通的点连边。
• 查询：询问两个连通的点间的路径的点权的最大子段和。

数据范围：

• $1\le n,m\le 3\times 10^6$。
• $-2^{31}\le a_i<2^{31}$。
• 数据强制在线。

时间限制：4s。
空间限制：512MB。
::::: 斜二进制倍增模板题（出题人题解）。
先引入斜二进制是什么。
:::::success[斜二进制] 斜二进制是第 $i$ 位表示的数是 $2^i-1$ 的一种进制（当然了尽可能用高位表示）。
容易发现一些性质：

• 每一位只可能出现 $0,1$ 或 $2$。
• 最多出现 $1$ 个 $2$。
• 若出现了 $2$，那么比 $2$ 所在位低的位都为 $0$。

设函数 $\text{skewlowbit}(x)$ 表示 $x$ 的最低的不为 $0$ 的位。
::::: 下面引入斜二进制倍增：
:::::success[斜二进制倍增] 定义一棵树是通过线段树偏移得到的，每个点都只作为一个区间的右端点，类似 BIT，每个点的区间为 $[x-\text{skewlowbit}(x)+1,x]$。
令 $lb_x=x-\text{skewlowbit}(x)$，这样方便我们跳区间，这样我们就可以倍增了。
类似 BIT 一样倍增即可。
::::: 在这个题中，斜二进制倍增要上树，每次新增点的时候选择较小的一个子树进行重构，时间复杂度是启发式合并的 $\Theta(n\log n)$。
讲的好像有点草率了。细节见代码吧。

时间复杂度为 $\Theta(n\log n)$。

code