3501. Maximize Active Section with Trade II

題目 / Problem

中文：給定一個長度為 n 的二進位字串 s，'1' 代表「啟用」區段、'0' 代表「停用」區段。你最多可以做一次交易：先把一段被 0 包圍的連續 1 全部變成 0，接著再把一段被 1 包圍的連續 0 全部變成 1。另外給你一個查詢陣列 queries，queries[i] = [l, r] 代表子字串 s[l..r]。對每個查詢，把子字串當作兩端各補一個 '1'（即 t = '1' + s[l..r] + '1'，這兩個補上的 1 不計入答案），只在這個子字串範圍內做最優交易，問整個 s 最終最多有幾個啟用區段（區段外的部分不會被改動）。查詢之間互相獨立。

English: You are given a binary string s of length n where '1' is active and '0' is inactive. You may perform at most one trade: first turn a maximal block of 1s that is surrounded by 0s into 0s, then turn a maximal block of 0s that is surrounded by 1s into 1s. For each query [l, r], you may only trade inside the substring s[l..r], which is treated as t = '1' + s[l..r] + '1' (the two padding 1s do not count). Return, for each query, the maximum number of active sections in the whole string afterward (positions outside [l, r] are never touched). Queries are independent.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ queries.length ≤ 10^5, 0 ≤ l ≤ r < n.

Worked example: s = "0100", query [0,3]. The substring "0100" becomes t = "101001". Erase the middle 1 (surrounded by 0s) → "100001", then fill the 0000 (now surrounded by 1s) → "111111". Removing the padding gives "1111" → 4 active sections.

名詞解釋 / Glossary

啟用區段 / active section：字串中每一個 '1'。答案就是最終字串裡 '1' 的個數。An active section is simply a '1'; the answer counts how many '1's remain.
段 / run (segment)：一段相同字元的極大連續區塊。例如 "1000100" 被切成 1 | 000 | 1 | 00，共 4 個段。A run is a maximal block of identical characters; runs strictly alternate between 0-runs and 1-runs.
交易 / trade：先刪一段被 0 包圍的 1（讓它變 0），再填一段被 1 包圍的 0。淨效果是把「0區塊 1區塊 0區塊」中的兩個 0 區塊填滿。A trade erases a 1-run flanked by 0s and then fills a 0-block flanked by 1s.
補一 / augmentation：把子字串兩端各想像成有一個 '1'。它讓子字串邊界上的 0 也算「被 1 包圍」，方便填滿。Padding with '1' on both ends lets boundary 0s count as "surrounded by 1s".
截斷 / clamp：查詢只看 [l, r] 範圍，超出邊界的段長度要被切短。Clamping means cutting a run's length at the query boundary l or r.
線段樹 / segment tree：一棵支援「區間最大值查詢」的樹狀資料結構，建樹 O(m)、每次查詢 O(log m)。A segment tree answers "maximum value in an index range" in O(log m) per query.
區間最大查詢 / range-maximum query：在一個陣列的某段下標區間內求最大值。Finding the max of an array over an index interval.

思路

中文：先想暴力：對每個查詢，把子字串複製出來，枚舉所有可能的交易，模擬後數 1。單次要 O(n) 甚至更多，q 個查詢就是 O(nq)，在 10^5 × 10^5 下完全爆掉。所以要找出交易的「淨收益」公式。關鍵觀察：一次交易一定是挑一個被 0 包圍的 1 段（設長度 b，左邊 0 段長 a、右邊 0 段長 c），把 1 段清成 0，此時 a+b+c 個 0 連成一塊且被外圍的 1 包圍，再全部填成 1。原本這塊有 b 個 1，之後有 a+b+c 個 1，所以淨收益 = a + c，也就是「左 0 段長 + 右 0 段長」，跟中間 1 段本身多長無關。因此答案 = 整串 s 的 1 總數 + 這個範圍內能取到的最大淨收益（沒有可交易的就是 0）。把 s 切成交替的段，對每個 1 段 i 預先算 ans[i] = len[i-1] + len[i+1]（0 段的 ans 記 0），問題就變成「在查詢範圍內對這些 ans 求最大值」。但要小心兩個邊界：查詢兩端的 0 段可能被 l、r 截斷，這時不能用預存的整段長度，要用被切短後的長度。所以策略是：完全落在範圍內、且左右鄰居也完全落在範圍內的 1 段，用線段樹做區間最大查詢；而最靠近左端與右端、鄰居 0 段被截斷的那兩個 1 段，各自單獨處理。補一的 1 保證邊界 0 段確實「被 1 包圍」，可以合法填滿。

English: Brute force copies each substring, tries every trade, and recounts — O(nq), hopeless at 10^5 × 10^5. The trick is a closed-form net gain. Any trade picks a 1-run surrounded by 0s: erase it, merging the left 0-run (length a) and right 0-run (length c) with the erased 1-run (length b) into one 0-block of size a+b+c that is now flanked by 1s, then fill it. That region held b ones before and a+b+c ones after, so the net gain is a + c — the two neighboring 0-run lengths, independent of the 1-run itself. Hence answer = (total ones in s) + (best net gain reachable inside [l,r]), or just the total ones when no trade is possible. Split s into alternating runs and precompute, for each 1-run i, ans[i] = len[i-1] + len[i+1]. A query then reduces to a range-maximum over these ans values — solved with a segment tree in O(log m). The one wrinkle: the boundary 0-runs may be clamped by l or r, so their true stored length is wrong there. We therefore use the segment tree only for 1-runs whose both neighbors sit fully inside the range, and handle the (at most) one clamped 1-run on each side separately. The padding 1s guarantee those boundary 0-blocks really are "surrounded by 1s" and thus legally fillable.

逐步走查 / Walkthrough

Take s = "0100". First split into runs and precompute ans:

run id	value	start..end	length	`ans` (`= len[i-1]+len[i+1]` for `1`-runs)
0	`0`	0..0	1	0 (it's a `0`-run)
1	`1`	1..1	1	`len[0]+len[2] = 1+2 = 3`
2	`0`	2..3	2	0 (it's a `0`-run)

onesTotal = 1 (one '1' in the whole string).

Query [0, 3] (the full string, nothing clamped):

step	value	中文 / English
`a = segId[0]`, `b = segId[3]`	`a=0, b=2`	找到左右端所在的段 / find the runs containing `l` and `r`
`loIdx` (`rs[0]==0`)	`0`	段 0 從 `l` 開始 → 完全在範圍內 / run 0 starts at `l`, fully inside
`hiIdx` (`re[2]==3`)	`2`	段 2 在 `r` 結束 → 完全在範圍內 / run 2 ends at `r`, fully inside
interior range `[loIdx+1, hiIdx-1] = [1,1]`	segment-tree max `= ans[1] = 3`	中間 `1` 段左右鄰居都完整 / neighbors of run 1 both fully inside
left/right boundary candidates	also give 3	邊界沒被截斷，結果相同 / no clamping here
result	`onesTotal + best = 1 + 3 = 4`	✔

Query [0, 2] (right 0-run gets clamped — the instructive case):

step	value	中文 / English
`a=segId[0]=0`, `b=segId[2]=2`		run containing `r=2` is run 2 (`"00"`, spans 2..3)
`loIdx` (`rs[0]==0`)	`0`	left fully inside
`hiIdx` (`re[2]=3 ≠ r=2`)	`b-1 = 1`	段 2 被 `r` 切斷，不算完整 / run 2 is cut by `r`, not fully inside
interior range `[1, 0]`	empty	沒有兩邊都完整的內部 `1` 段 / no fully-surrounded interior `1`-run
left candidate: `rv[0]==0`, `i=1`	`lz = rs[1]-l = 1`, `rz = min(re[2],r)-rs[2]+1 = min(3,2)-2+1 = 1`	右 `0` 段被截斷成長度 1 / right `0`-run clamped to length 1
candidate gain	`lz + rz = 2`
result	`1 + 2 = 3`	✔

The clamp is the whole point: the full run "00" has length 2, but inside [0,2] only one 0 is usable, so the gain drops from 3 to 2.

Solution — C

#include <stdlib.h>
#include <string.h>

// 演算法 / Algorithm:
//   把 s 切成交替的 0/1 段;對每個「被 0 包圍的 1 段」淨收益 = 左0段長 + 右0段長。
//   Split s into alternating runs; a trade's net gain = leftZeroLen + rightZeroLen.
//   內部段用線段樹做區間最大查詢;兩端被截斷的段單獨處理。
//   Use a segment tree for interior runs; handle the two clamped boundary runs specially.

// ---- 線段樹全域變數 / segment-tree globals ----
static int *g_tree;   // 線段樹儲存陣列 / the tree array
static int *g_ans;    // 每個段的淨收益候選值 / per-run gain values

// 建樹:把 g_ans[lo..hi] 的最大值填進 g_tree / build max-tree over run range [lo,hi]
static void build(int node, int lo, int hi) {
    if (lo == hi) { g_tree[node] = g_ans[lo]; return; }  // 葉子:直接存該段的值 / leaf holds one run's value
    int mid = (lo + hi) / 2;                              // 對半切 / split in half
    build(node * 2,     lo,      mid);                    // 建左子樹 / left child
    build(node * 2 + 1, mid + 1, hi);                     // 建右子樹 / right child
    int L = g_tree[node * 2], R = g_tree[node * 2 + 1];   // 取兩子結果 / children results
    g_tree[node] = L > R ? L : R;                         // 父結點存較大者 / parent = max of children
}

// 區間最大查詢:回傳 g_ans 在下標 [ql,qr] 內的最大值 / range-max over [ql,qr]
static int query(int node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;                     // 此結點與查詢無交集 / no overlap
    if (ql <= lo && hi <= qr) return g_tree[node];        // 此結點被查詢完全包含 / fully covered
    int mid = (lo + hi) / 2;                              // 否則往下分 / otherwise recurse
    int L = query(node * 2,     lo,      mid, ql, qr);    // 查左半 / query left
    int R = query(node * 2 + 1, mid + 1, hi, ql, qr);     // 查右半 / query right
    return L > R ? L : R;                                 // 合併取最大 / combine by max
}

int* maxActiveSectionsAfterTrade(char* s, int** queries, int queriesSize,
                                 int* queriesColSize, int* returnSize) {
    int n = (int)strlen(s);                               // 字串長度 / string length

    // 為每個段分配空間;段數最多 n 個 / at most n runs
    int *rs   = malloc(sizeof(int) * n);                  // 每段起點 / run start index
    int *re   = malloc(sizeof(int) * n);                  // 每段終點 / run end index
    int *rv   = malloc(sizeof(int) * n);                  // 每段的值 0 或 1 / run value
    int *segId = malloc(sizeof(int) * n);                 // 位置 -> 所屬段編號 / position to run id
    int m = 0;                                            // 段的總數 / number of runs
    int onesTotal = 0;                                    // 整串 1 的個數 / total ones in s

    for (int i = 0; i < n; ) {                            // 掃描整串切段 / scan and cut into runs
        int j = i;                                        // j 找出這一段的結尾 / j finds the run end
        while (j < n && s[j] == s[i]) j++;                // 只要字元相同就延伸 / extend while equal
        rs[m] = i; re[m] = j - 1; rv[m] = s[i] - '0';     // 記錄這一段 / record this run ('0'->0,'1'->1)
        if (rv[m] == 1) onesTotal += (j - i);             // 若是 1 段就累加長度 / count ones
        for (int k = i; k < j; k++) segId[k] = m;         // 標記此段內每個位置 / label positions
        m++;                                              // 段數 +1 / next run
        i = j;                                            // 從下一段開始 / move to next run
    }

    // 預算每個 1 段的淨收益 ans[i] = len[i-1] + len[i+1] / precompute gains
    g_ans = malloc(sizeof(int) * m);
    for (int i = 0; i < m; i++) {
        if (rv[i] == 1 && i > 0 && i < m - 1)             // 必須是內部的 1 段 / interior 1-run only
            g_ans[i] = (re[i-1] - rs[i-1] + 1) + (re[i+1] - rs[i+1] + 1); // 左段長 + 右段長 / two neighbor lengths
        else
            g_ans[i] = 0;                                 // 0 段或邊界段無收益 / no gain otherwise
    }
    g_tree = malloc(sizeof(int) * 4 * m);                 // 線段樹需要約 4m 空間 / tree needs ~4m nodes
    build(1, 0, m - 1);                                   // 從根結點 1 建樹 / build from root node 1

    int *res = malloc(sizeof(int) * queriesSize);         // 答案陣列 / result array
    for (int q = 0; q < queriesSize; q++) {
        int l = queries[q][0], r = queries[q][1];         // 這個查詢的區間 / this query's range
        int a = segId[l], b = segId[r];                   // 左右端所在的段 / runs containing l and r
        int best = 0;                                     // 目前最大淨收益 / best gain so far

        if (a != b) {                                     // a==b 表示整段同字元,無法交易 / single run: no trade
            // loIdx/hiIdx 是「完全落在範圍內」的最小/最大段編號 / smallest & largest fully-inside runs
            int loIdx = (rs[a] == l) ? a : a + 1;         // 段 a 只有從 l 起才算完整 / run a is full only if it starts at l
            int hiIdx = (re[b] == r) ? b : b - 1;         // 段 b 只有在 r 結束才算完整 / run b is full only if it ends at r

            // 內部 1 段:左右鄰居都完整 -> 用線段樹 / interior runs with both neighbors inside
            if (loIdx + 1 <= hiIdx - 1) {                 // 該範圍非空才查 / query only if range non-empty
                int v = query(1, 0, m - 1, loIdx + 1, hiIdx - 1);
                if (v > best) best = v;
            }

            // 左邊界候選:l 落在 0 段裡,右邊第一個 1 段的左 0 段被截斷 / left clamped candidate
            if (rv[a] == 0) {                             // l 在 0 段內 / l sits in a 0-run
                int i = a + 1;                            // 下一段必是 1 段 / next run is a 1-run
                if (re[i] <= r &&                         // 該 1 段完整落在範圍內 / 1-run fully inside
                    i + 1 <= m - 1 && rs[i+1] <= r) {     // 且右側範圍內還有 0 / and a 0 exists to its right
                    int rz = (re[i+1] < r ? re[i+1] : r) - rs[i+1] + 1; // 右 0 段長(必要時截斷) / right zero length, clamped
                    int lz = rs[i] - l;                   // 左 0 段長:從 l 到 1 段前 / left zeros from l
                    if (lz + rz > best) best = lz + rz;   // 更新最大 / update best
                }
            }

            // 右邊界候選:r 落在 0 段裡,左邊最後一個 1 段的右 0 段被截斷 / right clamped candidate
            if (rv[b] == 0) {                             // r 在 0 段內 / r sits in a 0-run
                int i = b - 1;                            // 前一段必是 1 段 / previous run is a 1-run
                if (rs[i] >= l &&                         // 該 1 段完整落在範圍內 / 1-run fully inside
                    i - 1 >= 0 && re[i-1] >= l) {         // 且左側範圍內還有 0 / and a 0 exists to its left
                    int lz = re[i-1] - (rs[i-1] > l ? rs[i-1] : l) + 1; // 左 0 段長(必要時截斷) / left zeros, clamped
                    int rz = r - re[i];                   // 右 0 段長:從 1 段後到 r / right zeros up to r
                    if (lz + rz > best) best = lz + rz;   // 更新最大 / update best
                }
            }
        }
        res[q] = onesTotal + best;                        // 答案 = 全串 1 數 + 最佳收益 / total ones + best gain
    }

    *returnSize = queriesSize;                            // 告訴呼叫者答案長度 / set output length
    free(rs); free(re); free(rv); free(segId);            // 釋放暫存 / free scratch arrays
    free(g_ans); free(g_tree);                            // 釋放線段樹 / free tree
    return res;                                           // 交還答案(呼叫者負責釋放) / caller frees res
}

Solution — C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 演算法 / Algorithm:
//   切成交替 0/1 段;每次交易淨收益 = 左0段長 + 右0段長 = ans[1段]。
//   Runs of 0/1; a trade's gain = leftZeroLen + rightZeroLen = ans[1-run].
//   內部段用線段樹區間最大;兩端截斷的段各自處理。答案 = 全串1數 + 最佳收益。
//   Segment tree for interior runs, special-case the two clamped boundary runs.

class Solution {
    vector<int> tree, ansv;                               // tree=線段樹, ansv=每段收益 / tree + per-run gains

    // 建樹:store max of ansv[lo..hi] / build max segment tree
    void build(int node, int lo, int hi) {
        if (lo == hi) { tree[node] = ansv[lo]; return; }  // 葉子存單段值 / leaf = one run's value
        int mid = (lo + hi) / 2;                          // 對半 / midpoint
        build(node * 2, lo, mid);                         // 左子樹 / left
        build(node * 2 + 1, mid + 1, hi);                 // 右子樹 / right
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]); // 取兩子最大 / parent = max
    }

    // 區間最大查詢 [ql,qr] / range-max query
    int query(int node, int lo, int hi, int ql, int qr) {
        if (qr < lo || hi < ql) return 0;                 // 無交集 / no overlap
        if (ql <= lo && hi <= qr) return tree[node];      // 完全覆蓋 / fully covered
        int mid = (lo + hi) / 2;
        return max(query(node * 2, lo, mid, ql, qr),      // 合併左右 / combine children
                   query(node * 2 + 1, mid + 1, hi, ql, qr));
    }

public:
    vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) {
        int n = (int)s.size();                            // 字串長度 / length

        // rs/re/rv 用 vector 動態存段;push_back 逐段加入 / grow run arrays with push_back
        vector<int> rs, re, rv, segId(n);                 // segId: 位置 -> 段編號 / position to run id
        long long onesTotal = 0;                          // 全串 1 的總數 / total ones
        for (int i = 0; i < n; ) {                        // 掃描切段 / scan into runs
            int j = i;                                    // 找段尾 / find run end
            while (j < n && s[j] == s[i]) j++;            // 相同字元延伸 / extend equal chars
            int id = (int)rs.size();                      // 這是第 id 個段 / current run id
            rs.push_back(i);                              // 記起點 / start
            re.push_back(j - 1);                          // 記終點 / end
            rv.push_back(s[i] - '0');                     // 記值(0/1) / value
            if (s[i] == '1') onesTotal += (j - i);        // 是 1 段就累加 / count ones
            for (int k = i; k < j; k++) segId[k] = id;    // 標記位置歸屬 / label positions
            i = j;                                        // 下一段 / next run
        }
        int m = (int)rs.size();                           // 段數 / number of runs

        // 預算每個內部 1 段的收益 / precompute gains for interior 1-runs
        ansv.assign(m, 0);                                // 預設全 0 / default 0
        for (int i = 0; i < m; i++)
            if (rv[i] == 1 && i > 0 && i < m - 1)         // 內部 1 段才有左右鄰居 / interior 1-run has both neighbors
                ansv[i] = (re[i-1] - rs[i-1] + 1) + (re[i+1] - rs[i+1] + 1); // 左段長 + 右段長 / neighbor lengths

        tree.assign(4 * m, 0);                            // 線段樹配置 4m / allocate ~4m nodes
        build(1, 0, m - 1);                               // 建樹 / build

        vector<int> res;                                  // 答案 / results
        res.reserve(queries.size());                      // 先預留空間 / reserve capacity
        for (auto& qq : queries) {                        // range-for 逐個查詢 / iterate queries
            int l = qq[0], r = qq[1];                     // 結構化取值 / query range
            int a = segId[l], b = segId[r];               // 左右端所在段 / runs of l and r
            int best = 0;                                 // 最佳收益 / best gain

            if (a != b) {                                 // 同一段內無法交易 / single run: no trade
                int loIdx = (rs[a] == l) ? a : a + 1;     // 最小完整段 / smallest fully-inside run
                int hiIdx = (re[b] == r) ? b : b - 1;     // 最大完整段 / largest fully-inside run

                if (loIdx + 1 <= hiIdx - 1)               // 內部 1 段用線段樹 / interior via segment tree
                    best = max(best, query(1, 0, m - 1, loIdx + 1, hiIdx - 1));

                if (rv[a] == 0) {                         // 左邊界:l 在 0 段內 / left clamp
                    int i = a + 1;                        // 右鄰的 1 段 / the 1-run after l
                    if (re[i] <= r && i + 1 <= m - 1 && rs[i+1] <= r) { // 1 段完整且右邊有 0 / valid
                        int rz = min(re[i+1], r) - rs[i+1] + 1; // 右 0 段長(截斷) / right zeros clamped
                        int lz = rs[i] - l;               // 左 0 段長(從 l 起) / left zeros from l
                        best = max(best, lz + rz);        // 更新 / update
                    }
                }
                if (rv[b] == 0) {                         // 右邊界:r 在 0 段內 / right clamp
                    int i = b - 1;                        // 左鄰的 1 段 / the 1-run before r
                    if (rs[i] >= l && i - 1 >= 0 && re[i-1] >= l) { // 1 段完整且左邊有 0 / valid
                        int lz = re[i-1] - max(l, rs[i-1]) + 1; // 左 0 段長(截斷) / left zeros clamped
                        int rz = r - re[i];               // 右 0 段長(到 r) / right zeros up to r
                        best = max(best, lz + rz);        // 更新 / update
                    }
                }
            }
            res.push_back((int)onesTotal + best);         // 答案 = 全串1數 + 收益 / total ones + gain
        }
        return res;                                       // 回傳所有答案 / return answers
    }
};

複雜度 / Complexity

Time: O(n + q·log m) — 切段掃一遍 s 是 O(n);建線段樹 O(m);每個查詢做一次區間最大查詢是 O(log m),共 q 個。m ≤ n,所以整體 O(n + q log n)。Building runs is one pass O(n); the tree builds in O(m); each of the q queries does one O(log m) range-max query (the boundary work is O(1)).
Space: O(n) — rs/re/rv/segId 共 O(n),線段樹 O(4m) = O(n)。答案 O(q)。All arrays are linear; the segment tree uses about 4m nodes.

Pitfalls & Edge Cases

收益不是中間 1 段的長度 / gain is not the erased 1-run's length:很多人誤以為收益跟被刪的 1 段有關,但淨收益只等於左右兩個 0 段長度和。搞錯公式整題就錯。The net gain is leftZeroLen + rightZeroLen, independent of the 1-run erased.
邊界段要截斷 / clamp the boundary runs:查詢兩端的 0 段常常只有一部分落在 [l,r] 內。若直接用預存的整段長度會高估。程式用 min(re[i+1], r)、max(l, rs[i-1]) 及 rs[i]-l、r-re[i] 來取被切短後的長度。Using a stored full run length at a clamped boundary overcounts; always cut at l/r.
答案含區間外的 1 / answer includes ones outside [l,r]:答案是「整串修改後」的啟用數,不是子字串的。因此要加上 onesTotal(全串 1 數),而不是只算子字串。Positions outside the query are unchanged, so we add the whole-string onesTotal, not just the substring's ones.
a == b(整段同字元)/ single-run range:此時範圍內沒有「被 0 包圍的 1 段」,無法交易,收益為 0,答案就是 onesTotal。這也正確處理了例子中 "00"、"100" 回傳 1 的情況。When l and r land in the same run there is no tradeable structure; best stays 0.
補一的 1 只讓邊界 0 段合法可填,不讓邊界 1 段可刪 / padding helps 0s, not 1s:靠邊界的 1 段若在該側沒有真實的 0,就不能被刪(補上的是 1 不是 0)。程式用 rv[a]==0 / rv[b]==0 的條件確保這點。A boundary 1-run cut by l/r has no 0 on that side and is never erasable.
線段樹大小 / tree sizing:一定要開 4*m 避免遞迴越界;m ≥ 1(因為 n ≥ 1)所以 build(1,0,m-1) 安全。Allocate 4*m nodes; m is at least 1.