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

from typing import List
import bisect

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        n = len(s)
        
        # Precompute x0[y]: smallest x s.t. [x..y] has <=k 0's
        x0 = [0] * n
        count0 = 0
        x = 0
        for y in range(n):
            if s[y] == '0':
                count0 +=1
            while count0 >k:
                if s[x] == '0':
                    count0 -=1
                x +=1
            x0[y] =x
        
        # Precompute x1[y]: smallest x s.t. [x..y] has <=k 1's
        x1 = [0] * n
        count1 =0
        x =0
        for y in range(n):
            if s[y] == '1':
                count1 +=1
            while count1 >k:
                if s[x] == '1':
                    count1 -=1
                x +=1
            x1[y] =x
        
        # Precompute x_up[y}: smallest x s.t. [x..y] has <=k0's and <=k1's
        x_up = [0] * n
        count0 =0
        count1 =0
        x =0
        for y in range(n):
            if s[y] == '0':
                count0 +=1
            else:
                count1 +=1
            while count0 >k or count1 >k:
                if s[x] == '0':
                    count0 -=1
                else:
                    count1 -=1
                x +=1
            x_up[y] =x
        
        # Precompute prefix sums
        P_y_plus1 = [0] * n
        P_y_plus1[0] =1
        for y in range(1, n):
            P_y_plus1[y] = P_y_plus1[y-1] + (y+1)
        
        P_x0 = [0] * n
        P_x0[0] =x0[0]
        for y in range(1, n):
            P_x0[y] = P_x0[y-1] + x0[y]
        
        P_x1 = [0] * n
        P_x1[0] =x1[0]
        for y in range(1, n):
            P_x1[y] = P_x1[y-1] + x1[y]
        
        P_xup = [0] * n
        P_xup[0] =x_up[0]
        for y in range(1, n):
            P_xup[y] = P_xup[y-1] + x_up[y]
        
        # Function to find yStart
        def find_yStart(x_arr, li, ri):
            # Find the first y in [li, ri] with x_arr[y] >= li
            # x_arr is non-decreasing
            left = li
            right = ri
            res = ri +1
            while left <=right:
                mid = (left + right) //2
                if x_arr[mid] >= li:
                    res = mid
                    right = mid -1
                else:
                    left = mid +1
            return res
        
        # Function to compute sum_max
        def compute_sum_max(x_arr, P_x_arr, li, ri):
            yStart = find_yStart(x_arr, li, ri)
            if yStart > ri:
                return li * (ri - li +1)
            else:
                sum_part1 = li * (yStart - li)
                sum_part2 = P_x_arr[ri] - (P_x_arr[yStart -1] if yStart >0 else 0)
                return sum_part1 + sum_part2
        
        # Function to compute sum_intersection
        def compute_sum_intersection(li, ri):
            # sum(y +1) from li to ri
            total_sum_y = ((ri +1)*(ri +2))//2 - (li)*(li +1)//2
            # sum_max(x_up[y], li)
            yStart = find_yStart(x_up, li, ri)
            if yStart > ri:
                sum_max = li * (ri - li +1)
            else:
                sum_max = li * (yStart - li) + (P_xup[ri] - (P_xup[yStart -1] if yStart >0 else 0))
            return total_sum_y - sum_max
        
        result = []
        for li, ri in queries:
            # Compute A
            total_sum_y = ((ri +1)*(ri +2))//2 - (li)*(li +1)//2
            sum_max_A = compute_sum_max(x0, P_x0, li, ri)
            sum_A = total_sum_y - sum_max_A
            
            # Compute B
            sum_max_B = compute_sum_max(x1, P_x1, li, ri)
            sum_B = total_sum_y - sum_max_B
            
            # Compute Intersection D
            sum_intersection = compute_sum_intersection(li, ri)
            
            # Answer
            answer = sum_A + sum_B - sum_intersection
            result.append(answer)
        
        return result

75500