3501. Maximize Active Section with Trade II

import java.util.*;

class Solution {
    public List<Integer> maxActiveSectionsAfterTrade(String s, int[][] queries) {
        int n = s.length();

        // 1. Run-length encode s: each run = {start, end, char(0/1)}
        List<int[]> runs = new ArrayList<>();
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) j++;
            runs.add(new int[]{i, j - 1, s.charAt(i) - '0'});
            i = j;
        }

        int totalOnes = 0;
        for (int k = 0; k < n; k++) if (s.charAt(k) == '1') totalOnes++;

        int m = runs.size();

        // 2. Collect candidate interior 1-runs (must have a real run before AND after)
        List<int[]> cand = new ArrayList<>(); // start, end, fullZleft, fullZright
        for (int idx = 0; idx < m; idx++) {
            int[] run = runs.get(idx);
            if (run[2] != 1) continue;
            if (idx == 0 || idx == m - 1) continue; // touches global boundary -> never usable
            int[] prev = runs.get(idx - 1); // guaranteed a 0-run
            int[] next = runs.get(idx + 1); // guaranteed a 0-run
            int fullZleft = run[0] - prev[0];   // full length of preceding zero run
            int fullZright = next[1] - run[1];  // full length of following zero run
            cand.add(new int[]{run[0], run[1], fullZleft, fullZright});
        }

        int cnt = cand.size();
        int[] candStart = new int[cnt];
        int[] candEnd = new int[cnt];
        int[] fullZL = new int[cnt];
        int[] fullZR = new int[cnt];
        int[] fullG = new int[cnt];
        for (int k = 0; k < cnt; k++) {
            int[] c = cand.get(k);
            candStart[k] = c[0];
            candEnd[k] = c[1];
            fullZL[k] = c[2];
            fullZR[k] = c[3];
            fullG[k] = c[2] + c[3];
        }

        // 3. Sparse table over fullG for O(1) range-max queries
        int LOG = cnt > 0 ? (31 - Integer.numberOfLeadingZeros(cnt)) : 0;
        int[][] sparse = new int[LOG + 1][Math.max(cnt, 1)];
        if (cnt > 0) {
            sparse[0] = fullG.clone();
            for (int k = 1; k <= LOG; k++) {
                int half = 1 << (k - 1);
                for (int idx = 0; idx + (1 << k) <= cnt; idx++) {
                    sparse[k][idx] = Math.max(sparse[k - 1][idx], sparse[k - 1][idx + half]);
                }
            }
        }
        int[] log2 = new int[cnt + 1];
        for (int k = 2; k <= cnt; k++) log2[k] = log2[k / 2] + 1;

        // 4. Answer queries
        List<Integer> ans = new ArrayList<>();
        for (int[] q : queries) {
            int l = q[0], r = q[1];
            int result = totalOnes;

            if (cnt > 0) {
                int iLo = upperBound(candStart, l);       // first idx with start > l
                int iHi = lowerBound(candEnd, r) - 1;      // last idx with end < r

                if (iLo <= iHi && iLo < cnt && iHi >= 0) {
                    int gain = 0;

                    if (iHi - iLo >= 2) {
                        int lo = iLo + 1, hi = iHi - 1;
                        int len = hi - lo + 1;
                        int kk = log2[len];
                        gain = Math.max(gain, Math.max(sparse[kk][lo], sparse[kk][hi - (1 << kk) + 1]));
                    }

                    int clipLo = Math.min(candStart[iLo] - l, fullZL[iLo])
                               + Math.min(r - candEnd[iLo], fullZR[iLo]);
                    int clipHi = Math.min(candStart[iHi] - l, fullZL[iHi])
                               + Math.min(r - candEnd[iHi], fullZR[iHi]);

                    gain = Math.max(gain, Math.max(clipLo, clipHi));
                    result += gain;
                }
            }

            ans.add(result);
        }
        return ans;
    }

    // first index with arr[idx] > val
    private int upperBound(int[] arr, int val) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] <= val) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    // first index with arr[idx] >= val
    private int lowerBound(int[] arr, int val) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] < val) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
}

from typing import List

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)

        runs = []
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            runs.append((i, j - 1, int(s[i])))
            i = j

        total_ones = s.count('1')
        cand = []

        for idx in range(1, len(runs) - 1):
            st, ed, bit = runs[idx]
            if bit == 0:
                continue
            prev = runs[idx - 1]
            nxt = runs[idx + 1]
            left = st - prev[0]
            right = nxt[1] - ed
            cand.append((st, ed, left, right))

        cnt = len(cand)

        start = [0] * cnt
        end = [0] * cnt
        left = [0] * cnt
        right = [0] * cnt
        gain = [0] * cnt

        for i in range(cnt):
            start[i], end[i], left[i], right[i] = cand[i]
            gain[i] = left[i] + right[i]

        if cnt:
            LOG = cnt.bit_length()
            sparse = [gain[:]]

            k = 1
            while (1 << k) <= cnt:
                prev = sparse[-1]
                cur = []
                half = 1 << (k - 1)
                for i in range(cnt - (1 << k) + 1):
                    cur.append(max(prev[i], prev[i + half]))
                sparse.append(cur)
                k += 1

            lg = [0] * (cnt + 1)
            for i in range(2, cnt + 1):
                lg[i] = lg[i // 2] + 1

        def upper(arr, val):
            lo, hi = 0, len(arr)
            while lo < hi:
                mid = (lo + hi) // 2
                if arr[mid] <= val:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        def lower(arr, val):
            lo, hi = 0, len(arr)
            while lo < hi:
                mid = (lo + hi) // 2
                if arr[mid] < val:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        ans = []

        for l, r in queries:
            res = total_ones

            if cnt:
                lo = upper(start, l)
                hi = lower(end, r) - 1

                if lo <= hi:
                    best = 0

                    if hi - lo >= 2:
                        L = lo + 1
                        R = hi - 1
                        length = R - L + 1
                        k = lg[length]
                        best = max(
                            sparse[k][L],
                            sparse[k][R - (1 << k) + 1]
                        )

                    clipL = min(start[lo] - l, left[lo]) + min(r - end[lo], right[lo])
                    clipR = min(start[hi] - l, left[hi]) + min(r - end[hi], right[hi])

                    best = max(best, clipL, clipR)
                    res += best

            ans.append(res)

        return ans

class Solution {
public:
    vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) {
        int n = s.size();

        vector<array<int,3>> runs;
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s[j] == s[i]) j++;
            runs.push_back({i, j - 1, s[i] - '0'});
            i = j;
        }

        int totalOnes = 0;
        for (char c : s) if (c == '1') totalOnes++;

        vector<array<int,4>> cand;

        for (int i = 1; i + 1 < runs.size(); i++) {
            if (runs[i][2] == 0) continue;

            int left = runs[i][0] - runs[i - 1][0];
            int right = runs[i + 1][1] - runs[i][1];

            cand.push_back({runs[i][0], runs[i][1], left, right});
        }

        int cnt = cand.size();

        vector<int> st(cnt), ed(cnt), zl(cnt), zr(cnt), full(cnt);

        for (int i = 0; i < cnt; i++) {
            st[i] = cand[i][0];
            ed[i] = cand[i][1];
            zl[i] = cand[i][2];
            zr[i] = cand[i][3];
            full[i] = zl[i] + zr[i];
        }

        int LOG = cnt ? 32 - __builtin_clz(cnt) : 0;
        vector<vector<int>> sp(LOG, vector<int>(max(1, cnt)));

        if (cnt) {
            sp[0] = full;
            for (int k = 1; k < LOG; k++) {
                int half = 1 << (k - 1);
                for (int i = 0; i + (1 << k) <= cnt; i++) {
                    sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + half]);
                }
            }
        }

        vector<int> lg(cnt + 1);
        for (int i = 2; i <= cnt; i++) lg[i] = lg[i / 2] + 1;

        vector<int> ans;

        for (auto &q : queries) {
            int l = q[0], r = q[1];
            int res = totalOnes;

            if (cnt) {
                int lo = upper_bound(st.begin(), st.end(), l) - st.begin();
                int hi = lower_bound(ed.begin(), ed.end(), r) - ed.begin() - 1;

                if (lo <= hi && lo < cnt && hi >= 0) {
                    int best = 0;

                    if (hi - lo >= 2) {
                        int L = lo + 1;
                        int R = hi - 1;
                        int len = R - L + 1;
                        int k = lg[len];
                        best = max(sp[k][L], sp[k][R - (1 << k) + 1]);
                    }

                    int clipL = min(st[lo] - l, zl[lo]) + min(r - ed[lo], zr[lo]);
                    int clipR = min(st[hi] - l, zl[hi]) + min(r - ed[hi], zr[hi]);

                    best = max(best, max(clipL, clipR));
                    res += best;
                }
            }

            ans.push_back(res);
        }

        return ans;
    }
};

var maxActiveSectionsAfterTrade = function(s, queries) {
    const n = s.length;

    const runs = [];
    let i = 0;
    while (i < n) {
        let j = i;
        while (j < n && s[j] === s[i]) j++;
        runs.push([i, j - 1, Number(s[i])]);
        i = j;
    }

    let totalOnes = 0;
    for (const ch of s) if (ch === '1') totalOnes++;

    const cand = [];

    for (let i = 1; i + 1 < runs.length; i++) {
        if (runs[i][2] === 0) continue;

        const left = runs[i][0] - runs[i - 1][0];
        const right = runs[i + 1][1] - runs[i][1];

        cand.push([runs[i][0], runs[i][1], left, right]);
    }

    const cnt = cand.length;

    const st = [], ed = [], zl = [], zr = [], full = [];

    for (const c of cand) {
        st.push(c[0]);
        ed.push(c[1]);
        zl.push(c[2]);
        zr.push(c[3]);
        full.push(c[2] + c[3]);
    }

    const lg = new Array(cnt + 1).fill(0);
    for (let i = 2; i <= cnt; i++) lg[i] = lg[i >> 1] + 1;

    const sparse = [];
    if (cnt) {
        sparse.push(full.slice());

        for (let k = 1; (1 << k) <= cnt; k++) {
            const prev = sparse[k - 1];
            const cur = [];
            const half = 1 << (k - 1);

            for (let i = 0; i + (1 << k) <= cnt; i++) {
                cur.push(Math.max(prev[i], prev[i + half]));
            }

            sparse.push(cur);
        }
    }

    function upper(arr, val) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] <= val) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    function lower(arr, val) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < val) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    const ans = [];

    for (const [l, r] of queries) {
        let res = totalOnes;

        if (cnt) {
            const lo = upper(st, l);
            const hi = lower(ed, r) - 1;

            if (lo <= hi && lo < cnt && hi >= 0) {
                let best = 0;

                if (hi - lo >= 2) {
                    const L = lo + 1;
                    const R = hi - 1;
                    const len = R - L + 1;
                    const k = lg[len];

                    best = Math.max(
                        sparse[k][L],
                        sparse[k][R - (1 << k) + 1]
                    );
                }

                const clipL = Math.min(st[lo] - l, zl[lo]) + Math.min(r - ed[lo], zr[lo]);
                const clipR = Math.min(st[hi] - l, zl[hi]) + Math.min(r - ed[hi], zr[hi]);

                best = Math.max(best, clipL, clipR);
                res += best;
            }
        }

        ans.push(res);
    }

    return ans;
};