<p>You are given a <strong>binary</strong> string <code>s</code> and an integer <code>k</code>.</p>

<p>You are also given a 2D integer array <code>queries</code>, where <code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code>.</p>

<p>A <strong>binary string</strong> satisfies the <strong>k-constraint</strong> if <strong>either</strong> of the following conditions holds:</p>

<ul>
	<li>The number of <code>0</code>&#39;s in the string is at most <code>k</code>.</li>
	<li>The number of <code>1</code>&#39;s in the string is at most <code>k</code>.</li>
</ul>

<p>Return an integer array <code>answer</code>, where <code>answer[i]</code> is the number of <span data-keyword="substring-nonempty">substrings</span> of <code>s[l<sub>i</sub>..r<sub>i</sub>]</code> that satisfy the <strong>k-constraint</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;0001111&quot;, k = 2, queries = [[0,6]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[26]</span></p>

<p><strong>Explanation:</strong></p>

<p>For the query <code>[0, 6]</code>, all substrings of <code>s[0..6] = &quot;0001111&quot;</code> satisfy the k-constraint except for the substrings <code>s[0..5] = &quot;000111&quot;</code> and <code>s[0..6] = &quot;0001111&quot;</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;010101&quot;, k = 1, queries = [[0,5],[1,4],[2,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[15,9,3]</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings of <code>s</code> with a length greater than 3 do not satisfy the k-constraint.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i] == [l<sub>i</sub>, r<sub>i</sub>]</code></li>
	<li><code>0 &lt;= l<sub>i</sub> &lt;= r<sub>i</sub> &lt; s.length</code></li>
	<li>All queries are distinct.</li>
</ul>

class SegNode:
    def __init__(self, l, r, val, left=None, right=None):
        self.l, self.r, self.val = l, r, val
        self.left, self.right = left, right

class SegmentTree:
    def __init__(self, values):
        self.values = values
        self.root = self.build(0, len(values) - 1)

    def build(self, l, r):
        if l == r:
            return SegNode(l, r, self.values[l])
        m = (l + r) // 2
        left, right = self.build(l, m), self.build(m + 1, r)
        return SegNode(l, r, max(left.val, right.val), left, right)

    def query(self, l, r, node, is_root):
        if r < l or node.r < l or r < node.l:
            return -inf
        if l <= node.l and node.r <= r:
            return node.val
        a = self.query(l, r, node.left, False)
        b = self.query(l, r, node.right, False)
        return max(a, b)

    def conditional_query(self, l, r):
        
        offset = l - 1 # Keep the original l to calculate the relative index i
        while l < r:
            m = (l + r) // 2
            i = m - offset  # Calculate i as the relative index starting from 1
            if self.values[m] <= i:
                r = m  # (l, m) is valid, continue search in (l, m)
            else:
                l = m + 1  # (l, m) is not valid, search in (m + 1, r)

        i = l - offset + 1  # Calculate i for the final check
        return l if self.values[l] <= i else -1


class Solution:
    def countKConstraintSubstrings(
        self, s: str, k: int, queries: List[List[int]]
    ) -> List[int]:
        c = l = 0
        d, pref = [0] * len(s), [0] * len(s)

        for r in range(len(s)):
            c += s[r] == "1"
            while c > k and (r - l + 1) - c > k:
                c -= s[l] == "1"
                l += 1
            d[r] += r - l + 1
            pref[r] += pref[r - 1] + d[r]

        tree = SegmentTree(d)
        ans = []
        #print(d)
        for l, r in queries:
            c = 0
            o = tree.conditional_query(l, r)
            #print(o)
            for i, j in enumerate(range(l, r + 1), 1):
                if d[j] <= i:
                    #print("j", j)
                    c += pref[r] - (pref[o - 1] if j else 0)
                    break
                else:
                    #print("i", i)
                    c += i

            ans.append(c)
            #print()

        return ans

79300