<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 BIT:
    def __init__(self, n):
        self.arr = [0 for i in range(n+1)]
        self.n = n
        
    def lowbit(self, x):
        return x & (-x)
    
    def add(self, idx, x):
        idx += 1
        while idx <= self.n:
            self.arr[idx] += x
            idx += self.lowbit(idx)
            
    def presum(self, idx):
        res = 0
        idx += 1
        while idx > 0:
            res += self.arr[idx]
            idx -= self.lowbit(idx)
        return res
    
    def query(self, l, r):
        return self.presum(r) - self.presum(l-1)
    
class Solution:
    # ans[l, r] = \sum_{i=l}^{r}{i - max(l, f[i]) + 1} = \sum_{i=l}^{r}{i + 1} - \sum_{i=l}^{r}{max(f[i], l)}
    # f[i]: leftmost idx for right boundary i
    # 维护带max条件的区间和，只能离线处理+两个BIT
    # 排序queries，两个BIT，如果f[i] >= l，则A[i] = f[i], B[i] = 0，否则A[i] = 0, B[i] = 1
    # 则区间和 = sum(A[l...r]) + sum(B[l...r]) * l
    # 从l'到l，只需把f[i]在[l', l)的A[i]都置为0，然后B[i]置为1
    # 一个BIT是不行的，因为把A[i]置为l只能满足当前的l，当进入下一个l又得重复更新很多A[i]，
    # 用一个B[i]则一劳永逸，每个位置只会更新一次
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        n = len(s)
        qs = []
        for i, [l, r] in enumerate(queries):
            qs.append((l, r, i))
        qs.sort()
        
        end = [[] for i in range(n)]
        zero = 1 if s[0] == '0' else 0
        one = 1 - zero
        end[0].append(0)
        left = 0
        A = BIT(n)
        A.add(0, 0)
        f = [0 for i in range(n)]

        for i in range(1, n):
            if s[i] == '0': zero += 1
            else: one += 1
            
            while (zero > k and one > k) and left < i:
                if s[left] == '0': zero -= 1
                else: one -= 1
                left += 1
            
            end[left].append(i)
            A.add(i, left)
            f[i] = left
        # print(end)
        # print(f)
        B = BIT(n)
        ans = [0 for i in range(len(qs))]
        prevl = 0
        for l, r, i in qs:
            for j in range(prevl, l):
                for idx in end[j]:
                    A.add(idx, -f[idx])
                    B.add(idx, 1)
            # print(l, r, A.query(l, r), B.query(l, r))
            ans[i] = (l + r) * (r - l + 1) / 2 + (r - l + 1) - (A.query(l, r) + B.query(l, r) * l)
            ans[i] = int(ans[i])
            prevl = l
        
        return ans
75900