3501. Maximize Active Section with Trade II

Problem Overview

Each query restricts the trade to substring s[l..r] (virtually flanked by 1s).

Intuition

Each query restricts the trade to substring s[l..r] (virtually flanked by 1s). Outside characters never change, so the answer is always globalOnes + bestGainInside[l..r]. The best gain is still “sum of two adjacent zero-runs,” but runs may be clipped when l or r cuts into a zero block, and only pairs fully inside the query window are eligible — so offline RMQ over adjacent zero-pair lengths answers every query in O(1) after an O(n log n) sparse-table build.

Algorithm

1Count total ones in s. Collect every contiguous zero-run as (start, length) and map each index to its run id (−1 before the first zero).
2Build merge[i] = length[i] + length[i+1] for adjacent zero-runs; put merge into a sparse table for range maximum.
3For query [l, r]: left = remaining zeros from l to the end of its run; right = zeros from the start of r’s run through r.
4Take max of: ones (no trade); ones + left + right when l and r sit in consecutive zero-runs; ones + RMQ over fully interior adjacent pairs; ones + left + next full run; ones + right + previous full run — whichever cases are valid for the window.
5Return the list of answers; queries are independent.

Example Walkthrough

Input: s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]

1.ones = 1; zero-runs: [0,1] length 1 and [2,3] length 2; merge = [3].
2.Query [0,3]: best trade merges both runs → 1 + 3 = 4.
3.Query [0,2]: clipped right run contributes 1 → 1 + 1 + 1 = 3.
4.Queries [1,3] and [2,3]: no valid surrounded 1-block to trade → stay at 1.

Output: [4, 3, 1, 1]

Common Pitfalls

•Trade is only inside [l, r]; do not use zero-runs that lie entirely outside the window.
•When l or r lands inside a zero-run, use the clipped length, not the full run length.
•If there are fewer than two zero-runs in range, gain is 0 — return ones.
•Sparse table answers max over merge indices, not over character indices; map group ids carefully at the endpoints.
•n, q up to 1e5 — per-query linear scans TLE; need O(1) or O(log n) per query after preprocessing.

3501.cs

public class Solution
{
    // Approach: Same trade idea as LC 3499 — a valid trade activates two adjacent
    // zero-runs (net gain = sum of their lengths). Precompute every zero-run, build
    // adjacent-pair lengths, and answer range-max of those pairs with a sparse table.
    // Each query [l,r] clips runs at the endpoints and takes the best of: no trade,
    // merge two clipped endpoint runs, or RMQ over fully interior adjacent pairs.
    // Complexity: O(n log n + q) time and O(n log n) space.
    public IList<int> MaxActiveSectionsAfterTrade(string s, int[][] queries)
    {
        int n = s.Length;
        int ones = 0;
        foreach (char c in s)
            if (c == '1')
                ++ones;

        var (zeroGroups, zeroGroupIndex) = GetZeroGroups(s);

        if (zeroGroups.Count == 0)
            return Enumerable.Repeat(ones, queries.Length).ToList();

        var st = new SparseTable(GetZeroMergeLengths(zeroGroups));
        var ans = new List<int>(queries.Length);

        foreach (int[] query in queries)
        {
            int l = query[0];
            int r = query[1];
            int left = zeroGroupIndex[l] == -1
                ? -1
                : zeroGroups[zeroGroupIndex[l]].Length - (l - zeroGroups[zeroGroupIndex[l]].Start);
            int right = zeroGroupIndex[r] == -1
                ? -1
                : r - zeroGroups[zeroGroupIndex[r]].Start + 1;
            var (startAdjacentGroupIndex, endAdjacentGroupIndex) = MapToAdjacentGroupIndices(
                zeroGroupIndex[l] + 1,
                s[r] == '1' ? zeroGroupIndex[r] : zeroGroupIndex[r] - 1);

            int activeSections = ones;
            if (s[l] == '0' && s[r] == '0' && zeroGroupIndex[l] + 1 == zeroGroupIndex[r])
                activeSections = Math.Max(activeSections, ones + left + right);
            else if (startAdjacentGroupIndex <= endAdjacentGroupIndex)
                activeSections = Math.Max(activeSections,
                    ones + st.Query(startAdjacentGroupIndex, endAdjacentGroupIndex));
            if (s[l] == '0' &&
                zeroGroupIndex[l] + 1 <= (s[r] == '1' ? zeroGroupIndex[r] : zeroGroupIndex[r] - 1))
                activeSections = Math.Max(activeSections,
                    ones + left + zeroGroups[zeroGroupIndex[l] + 1].Length);
            if (s[r] == '0' && zeroGroupIndex[l] < zeroGroupIndex[r] - 1)
                activeSections = Math.Max(activeSections,
                    ones + right + zeroGroups[zeroGroupIndex[r] - 1].Length);
            ans.Add(activeSections);
        }

        return ans;
    }

    // Returns the zero groups and the index of the zero group that contains the i-th character.
    private (List<Group> zeroGroups, int[] zeroGroupIndex) GetZeroGroups(string s)
    {
        var zeroGroups = new List<Group>();
        int[] zeroGroupIndex = new int[s.Length];

        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '0')
            {
                if (i > 0 && s[i - 1] == '0')
                    zeroGroups[^1].Length++;
                else
                    zeroGroups.Add(new Group(i, 1));
            }
            zeroGroupIndex[i] = zeroGroups.Count - 1;
        }

        return (zeroGroups, zeroGroupIndex);
    }

    // Returns the sums of the lengths of adjacent zero groups.
    private int[] GetZeroMergeLengths(List<Group> zeroGroups)
    {
        int[] zeroMergeLengths = new int[zeroGroups.Count - 1];
        for (int i = 0; i < zeroGroups.Count - 1; ++i)
            zeroMergeLengths[i] = zeroGroups[i].Length + zeroGroups[i + 1].Length;
        return zeroMergeLengths;
    }

    // Returns the indices of the adjacent groups that contain l and r completely.
    private (int start, int end) MapToAdjacentGroupIndices(int startGroupIndex, int endGroupIndex)
    {
        return (startGroupIndex, endGroupIndex - 1);
    }
}

class Group
{
    public int Start;
    public int Length;

    public Group(int start, int length)
    {
        Start = start;
        Length = length;
    }
}

class SparseTable
{
    private readonly int n;
    private readonly int[][] st; // st[i][j] := max(nums[j..j + 2^i - 1])

    public SparseTable(int[] nums)
    {
        n = nums.Length;
        st = new int[BitLength(n) + 1][];
        for (int i = 0; i < st.Length; ++i)
            st[i] = new int[n + 1];

        if (n > 0)
            Array.Copy(nums, 0, st[0], 0, n);

        for (int i = 1; i < st.Length; ++i)
            for (int j = 0; j + (1 << i) <= n; ++j)
                st[i][j] = Math.Max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }

    // Returns max(nums[l..r]).
    public int Query(int l, int r)
    {
        int i = BitLength(r - l + 1) - 1;
        return Math.Max(st[i][l], st[i][r - (1 << i) + 1]);
    }

    private static int BitLength(int value)
    {
        return value == 0 ? 0 : 32 - System.Numerics.BitOperations.LeadingZeroCount((uint)value);
    }
}

Was this solution helpful?