残卷再启新劫数，线段树中破查询

第一章：残卷天书藏玄机

《算法导论》残卷到手后，我依然没能从那六个字里参透更多东西——“考虑边界条件”。任码行说这是因为我拿到的是目录页，但我宁愿相信这是掌门的考验。

考验来得比想象中快。

子时三刻，腰间令牌再次嗡嗡作响。我心头一紧——上次这个点收到消息，差点要去扫厕所三年。点开一看，果然是掌门：

“令码冲，昨日你以白嫖剑法破解逆天改命之术，吾甚欣慰。然，如今丹炉已积攒百万颗仙丹，品阶参差不齐。现有十万次查询，每次指定一个子区间，你只能在该区间内施展一次逆天改命之术，并给出区间操作后整个丹炉的最大极品丹总数。十万次查询，十万个结果，限时一炷香。若成，赏《数据结构真解》全卷；若败……去灵兽谷铲屎十年。”

我手一抖，差点把昨天的《算法导论》残卷撕了。十万次查询！每个查询独立处理！这哪是炼丹，这是要把整个青云门的丹药数据库都洗一遍啊！

任码行凑过来，幸灾乐祸地笑道：“令师弟，昨天你那 O(n) 遍历心法，今天得跑 O(q*n) 次吧？n = 10^5, q = 10^5，总共 10^10 次操作……啧啧，等你算完，灵兽谷的屎都发酵成有机肥了。”

“闭嘴。”

“不过话说回来，“他突然正经起来，“十万个区间查询，每个区间大小不一，你得在眨眼之间算出任意一段丹药序列的最优白嫖数——这不就是在考验你对边界的理解吗？”

我愣住了。边界。残卷上的六个字再次浮现在脑海。

昨天，我处理的是整条丹药序列，边界是确定的——第一堆废丹没有前任，用负无穷兜底。但今天，每个查询区间都是一条独立的序列，区间边界可能切在任意位置：切在废丹堆中间、切在极品堆中间、或者刚好卡在组与组的交界处。每次切法不同，边界就不同。

“考虑边界条件。“我喃喃自语，“掌门不是让我背这六个字，而是让我学会应对动态边界。”

昨天我只需要处理“第一堆废丹没有前任”这一种边界。今天我需要处理的是：**十万个不同区间，每个区间都有自己独特的边界截断方式。**左边界可能砍掉一堆废丹的前半截，右边界可能削去一堆废丹的后半截，首尾废丹堆的实际长度全看区间边界切在哪。

换句话说，昨天的边界是死的，今天的边界是活的。而我，需要一个能在眨眼之间回答任意区间查询的方案。

第二章：线段树中寻破局

想通这一点之后，我整个人反而冷静下来了。

核心没变——答案依然是“整个丹炉的极品丹总数 + 查询区间内能白嫖的最大废丹数”。整个丹炉的极品丹总数是死的，一个 total1_all 全局变量搞定。真正的难点全在那句“查询区间内能白嫖的最大废丹数”。

昨天的任务，本质上是处理一个查询——查询区间就是整个序列。一条 O(n) 遍历，相邻废丹堆两两配对，取长度之和的最大值，干净利落。但今天，十万个查询。每个查询的操作区间都不一样，我不可能每次从头遍历一遍。

“得用空间换时间。”我盯着丹炉屏幕上长长的查询序列，自言自语，“提前算好存起来，查的时候直接用。”

问题是——存什么？

我摊开草稿纸，开始列清单。首先，废丹堆的位置和长度肯定要存。查询区间一来，我得知道区间里有哪些废丹堆，它们的起止位置在哪，长度多少。这个好办，把所有废丹堆的信息扔进数组就行，到时候二分查找定位。

其次，光存单个废丹堆不够。白嫖剑法的核心是"相邻废丹堆配对”——查询区间内任意两个被极品丹隔开的相邻废丹堆，长度之和的最大值。这个值才是真正的白嫖上限。

如果我把所有可能的相邻对都存下来……等等，查询区间会怎么覆盖这些相邻对？我在草稿纸上画成了三块：

操作区间: [l, r]

  首堆(可能截断) |  中间完整废丹堆们  | 尾堆(可能截断)
       ↓                ↓                ↓
   动态，单独算     它们之间的相邻对      动态，单独算
                   长度和是固定的
                        ↓
                 可以提前算好存起来

中间那些完整的废丹堆，它们的相邻对长度之和是不变的——因为既没被左边界砍头，也没被右边界削尾，原封不动。这部分完全可以提前算好，存进一个数组。查询的时候，只要定位到区间内第一个和最后一个废丹堆，中间那些完整相邻对的最大值，就是这个数组在某个范围内的最大值。

“区间最大值……”

我脑子里叮的一声，像炼丹炉的定时器响了。区间最大值，快速查询——这不是线段树的老本行吗？

“施主，你终于走到这一步了。”

身后突然传来一个声音，不高不低，不急不缓，像是从数据库底层慢慢浮上来的一条查询结果——整座青云门，能用这种语调说话的，只有一个人。

扫地僧站在我身后，手里还是那把扫帚。

“前辈！“我连忙起身，“您来得正好，我在想——”

“你在想，存什么、怎么存、查什么、怎么查。“他打断我，语气平淡得像在念一条单行注释。“答案你已经画在纸上了。”

他用扫帚柄指向我草稿纸上的三块分区图。

“第一步，存废丹堆。把所有废丹堆的起始位置、结束位置、长度，打包进三个数组。查询时二分定位首尾。”

“第二步，存相邻对。把原序列里所有’被至少一堆极品丹隔开的相邻废丹堆对’的长度之和，按顺序存进一个数组。这个数组是静态的，不会因为查询区间变化而改变。”

“第三步，建线段树。在这个相邻对数组上建一棵线段树，维护区间最大值。查询时，二分定位到区间内第一个和最后一个废丹堆，中间那些完整相邻对的最大值，直接丢给线段树 O(log n) 返回。”

他顿了顿，扫帚柄在"首堆"和"尾堆"两个区域各点了一下。“首尾两个废丹堆可能被截断，长度是动态的，必须当场算。首堆和它后面的完整堆配对，尾堆和它前面的完整堆配对，再加上线段树查出来的中间最大值——三种候选取最大，完事。”

我的大脑飞速运转，每个查询只需要两次二分加一次线段树查询，O(log n)，这不正是我需要的能眨眼间回答任意区间查询的方案吗！

扫地僧拎起扫帚，眼神深邃如井：“想清楚哪些是静态的、可以预处理的——交给数据结构。哪些是动态的、必须当场算的——留给自己。这也是一种架构设计。”

他走了几步，又停下来，没回头。“对了。你画的三个候选，首、尾、中间——覆盖了所有情况吗？”

我重新扫了眼草稿纸，确实，还有边界情况，如果区间内恰好只有两个废丹堆呢？那就没有"中间完整废丹堆”，线段树查不了。不过这反而更简单——两个废丹堆直接配对，候选就一个。

“刚好两个的情况，直接配对。“我答道，“如果只有一个或者一个都没有，无法配对，白嫖收益为零。”

扫地僧没说话，继续拖地。扫帚在地上拖出一道长长的水痕，像极了一条没写注释的遗留代码。

我重新坐回丹炉前，思路已然明了：分组、存废丹堆、算相邻对、建线段树、二分定位、三种候选取最大。每一步都在脑子里排好了队，就差动手实现了。

不过炼丹之前，我先在心里把那句话默念了三遍——

静态的交给数据结构，动态的留给自己。

掌门残卷上那六个字是“考虑边界条件”。扫地僧这句，像是它的扩展版。

第三章：乾坤挪移查询术

扫地僧的扫帚声远去，我重新坐回丹炉前。在正式开打之前，得先搭好一个关键组件——线段树。

这玩意儿在青云门的炼丹体系里属于“高级数据结构”，据说是百年前一位扫地僧级别的架构师发明的。思想非常炫酷：把数组像折纸一样不断对折，每个折痕处存左右两半的最大值。查的时候把查询区间也折几折，O(log n) 出结果。听起来玄乎，写出来就是一棵递归定义的二叉树，每个节点管一段区间，叶子管单个元素。

我默写下模板。这段代码和业务逻辑无关，纯粹的“炼丹炉基础设施”——就像你炼丹之前得先通电。

class SegmentTree:
    """线段树，维护区间最大值"""
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)

    def _build(self, arr, node, l, r):
        if l == r:
            self.tree[node] = arr[l]
            return
        mid = (l + r) // 2
        self._build(arr, node * 2, l, mid)
        self._build(arr, node * 2 + 1, mid + 1, r)
        self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])

    def query(self, ql, qr):
        """查询区间 [ql, qr] 最大值，包含边界"""
        return self._query(1, 0, self.n - 1, ql, qr)

    def _query(self, node, l, r, ql, qr):
        if ql > r or qr < l:
            return -10**9  # 足够小的值，相当于“此路不通”
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        left = self._query(node * 2, l, mid, ql, qr)
        right = self._query(node * 2 + 1, mid + 1, r, ql, qr)
        return max(left, right)

-10**9 是炼丹界的"负无穷”。查区间时，如果当前节点完全在查询区间外，返回这个极小值，保证 max 永远不会选它。和昨天 pre0 用 float('-inf') 一个套路——用极小值兜底，专治各种查不着的边界情况。

模板搭好了。接下来是真正的剑法——我把这套心法命名为乾坤挪移查询术。任码行不在，就没人吐槽我中二。

from itertools import groupby
from bisect import bisect_left, bisect_right

def maxActiveSectionsAfterTrade(s: str, queries: List[List[int]]) -> List[int]:
    n = len(s)
    total1_all = s.count('1')

    # 第一式·分组入库
    groups = []
    start = 0
    for char, g in groupby(s):
        length = sum(1 for _ in g)
        groups.append((char, start, start + length - 1))
        start += length

起手式照旧——groupby 分拣术。丹药序列按连续同类打包，每包记录品类、起始位置、结束位置，相当于给丹药序列建了个“聚簇索引”。

    # 第二式·废丹堆建档
    zero_groups = [(st, ed, ed - st + 1) for ch, st, ed in groups if ch == '0']
    m = len(zero_groups)

    if m < 2:
        return [total1_all] * len(queries)

少于两个废丹堆，配对无从谈起，白嫖数为零。所有查询直接返回全局极品丹总数。这是边界条件的第一道防线——与其在循环里反复判断，不如一开始就拦在外面。师兄管这叫"尽早返回”，我管这叫"早死早超生”。

    # 提取索引数组，供二分查找用
    zero_starts = [zg[0] for zg in zero_groups]
    zero_ends   = [zg[1] for zg in zero_groups]
    zero_len    = [zg[2] for zg in zero_groups]

三个平行数组，分别存每个废丹堆的起始位置、结束位置、长度，后面二分查找需要单独的起始和结束数组——bisect_left 只认裸列表。

    # 第三式·相邻对建线段树
    adj = [zero_len[i] + zero_len[i + 1] for i in range(m - 1)]
    seg = SegmentTree(adj)

adj[i] 表示第 i 个和第 i+1 个废丹堆的长度之和。提前全算好，装进线段树。这就是扫地僧说的“空间换时间”——静态的、能预处理的，全交给数据结构。

    # 第四式·逐个查询，分情况处理
    ans = []
    for l, r in queries:
        left_idx = bisect_left(zero_ends, l)
        right_idx = bisect_right(zero_starts, r) - 1        

查询入口，先直接两行二分定位。bisect_left(zero_ends, l) 找第一个右边界碰到 l 的废丹堆——区间首个废丹堆。bisect_right(zero_starts, r) - 1 找最后一个左边界碰到 r 的废丹堆——区间末个废丹堆。

用二分在静态数据上定位动态边界，O(log m)。

        if left_idx >= m or right_idx < 0 or left_idx >= right_idx:
            ans.append(total1_all)
            continue

边界条件的第二道防线。三种情况直接返回：区间里没有废丹堆，或者只有一个：无法配对，白嫖数为零。

接下来就是处理真正的战场：区间里至少有两个废丹堆，能配对，能白嫖。

先做截断计算。首尾废丹堆可能被区间边界砍过，得算出实际剩余长度：

        left_len = min(zero_ends[left_idx], r) - max(zero_starts[left_idx], l) + 1
        right_len = min(zero_ends[right_idx], r) - max(zero_starts[right_idx], l) + 1

公式看着复杂，本质就是“重叠区间长度”。废丹堆的右边界和区间右边界，谁小听谁的；废丹堆的左边界和区间左边界，谁大听谁的。两个边界一夹，中间那段就是在区间里的实际长度。

然后分情况取最大值：

    	count = right_idx - left_idx + 1  # 区间内的废丹堆数量
    
        if count == 2:
            # 恰好2个废丹堆，直接配对
            mx = left_len + right_len
            
        else:
            # 超过2个废丹堆，三种选择取最大值
            val1 = left_len + zero_len[left_idx + 1]   # 首配对：首堆(截断) + 第二个(完整)
            val2 = zero_len[right_idx - 1] + right_len # 尾配对：倒数第二个(完整) + 尾堆(截断)
            val3 = seg.query(left_idx + 1, right_idx - 2)  # 中间完整相邻对(线段树查询)

            mx = max(val1, val2, val3)

        ans.append(total1_all + mx)

    return ans     

三种候选：首堆（截断）加第二个完整堆；倒数第二个完整堆加尾堆（截断）；中间完全在区间内的相邻对的最大值，线段树 O(log n) 直接返回。另外，如果 left_idx+1 > right_idx-2，线段树查询范围为空，返回 -10**9，在 max 里被自动淘汰——和昨天的 float('-inf') 异曲同工——又是“考虑边界条件”在默默兜底。

整套剑法写完，三次边界判断——废丹堆不够两个、区间内不超过一个废丹堆、线段树查空，还有一堆细节——左截断、右截断、完整废丹堆的定位、线段树查询范围的确定……每一样都需要小心处理边界条件。掌门那六个字，像一句咒语——嵌在每一个关键分支里。

我靠在椅背上，长出一口气。任码行不知什么时候凑了过来，沉默三秒后开口：“乾坤挪移查询术？？”

“是扫地僧给思路时现想的。”

“不如改成‘线段树二分查询炼丹大法’？”

我白了他一眼，“你这命名水平比我还中二。”

第四章：万问齐发一剑封

卯时将至，我打开丹炉控制台，启动批量处理模式。十万个查询如洪水般涌入，线段树如一把利剑，瞬间将它们全部斩杀，O(q log n) 的威力，果然不是盖的。总时间复杂度O(n + q log n)。

我把结果打包成飞鸽传书，发往掌门大殿。片刻后，一道金光落入掌心——掌门又秒回了。这响应速度，秒杀了我们炼丹房的 CI/CD 流水线。

我拆开一看，正是《数据结构真解》全卷。不是残卷，是全卷。厚厚一沓，封面烫金大字，纸张摸起来比我的蒲团还舒服。我颤抖着翻开第一页，上面写着：

“以不变，应万变。”

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。