<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>

def LEFT(node):
    return node*2

def RIGHT(node):
    return node*2 + 1

def IS_LEFT(node):
    return node%2 == 0

def IS_RIGHT(node):
    return node%2 == 1

def PARENT(node):
    return node//2

class SegmentTree:
    def __init__(self, nums, merge, def_val):
        n = len(nums)
        self.n = n
        self.tree = [def_val] * (2 * n)
        self.merge = merge
        self.def_val = def_val

        self.tree[n:2*n] = nums
        for node in range(n-1, 0, -1):
            self.eval_node(node)
    
    def eval_node(self, node):
        self.tree[node] = self.merge(self.tree[LEFT(node)], self.tree[RIGHT(node)])

    def update(self, i, val):
        node = i + self.n
        self.tree[node] = val
        node = PARENT(node)
        while node > 0:
            self.eval_node(node)
            node = PARENT(node)

    def query(self, l, r):
        l += self.n
        r += self.n
        ans = self.def_val

        while l<r:
            if IS_RIGHT(l):
                ans = self.merge(ans, self.tree[l])
                l += 1
            if IS_RIGHT(r):
                r -= 1
                ans = self.merge(ans, self.tree[r])
            l = PARENT(l)
            r = PARENT(r)

        return ans

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        start = 0
        n = len(s)
        ans = 0

        sum2 = lambda a, b: a+b
        st = SegmentTree([0] * (n+1), sum2, 0)
        stCnt = SegmentTree([0] * (n+1), sum2, 0)

        cnt0 = 0

        def cnt1():
            return end-start+1 - cnt0
        
        qi = defaultdict(list)
        for i, (l, r) in enumerate(queries):
            qi[r].append((i, l))

        ans = [0] * len(queries)

        for end in range(n):
            if s[end] == '0':
                cnt0 += 1
            
            while cnt0 > k and cnt1() > k:
                if s[start] == '0':
                    cnt0 -= 1
                start += 1
            
            # print(end, start, st.query(start, start+1))
            
            # start number of items are valid till end
            st.update(start, st.query(start, start+1) + start)
            stCnt.update(start, stCnt.query(start, start+1) + 1)


            for i, l in qi[end]:
                # print(st.tree)
                # print(st.query(l, end), stCnt.query(l, end))
                invalid = st.query(l, end+1) - stCnt.query(l, end+1)*l
                # print(invalid)
                N = (end-l) + 1
                ans[i] = (N*(N+1))//2 - invalid
        

        return ans


























79700