<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 Solution:
  def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
    s = [int(x) for x in s]

    result = [0] * len(queries)

    idx = [[] for _ in range(len(s))]
    for i, [_, ri] in enumerate(queries):
      idx[ri].append(i)

    class MySlidingWindow(SlidingWindow):
      def __init__(self):
        super().__init__(s, Sum())

      def should_contract_left(self, li: int, ri: int) -> bool:
        one_count = self.observer.sum
        zero_count = ri - li + 1 - one_count
        return one_count > k and zero_count > k

      def is_window_good(self, li: int, ri: int) -> bool:
        return True

    array = RangeArray(len(s))
    for li, ri in MySlidingWindow().run():
      array.update(li, ri, 1)
      for i in idx[ri]:
        result[i] = array.query(*queries[i])

    return result


class RangeArray:

  def __init__(self, size: int):
    assert size > 0
    self._leaf_count = self._get_leaf_count(size)
    self._node_count = self._leaf_count * 2  # including the sentinel 0th node
    self._tree_depth = self._leaf_count.bit_length()
    self._values = [0] * self._node_count
    self._updates = [0] * self._node_count

  def update(self, li: int, ri: int, value):
    # assert 0 <= li <= ri < self._leaf_count
    split = self._split(li, ri)
    ancestors = self._ancestors(split[0], split[-1])
    self._push_updates_down(ancestors)
    for i in split:
      self._values[i] += value * self._range_length(i)
      self._updates[i] += value
    for i in ancestors:
      self._values[i] = self._values[2 * i] + self._values[2 * i + 1]

  def query(self, li: int, ri: int):
    # assert 0 <= li <= ri < self._leaf_count
    split = self._split(li, ri)
    self._push_updates_down(self._ancestors(split[0], split[-1]))
    return sum(self._values[i] for i in split)

  # --------------------------------------------------------------------------

  def _get_leaf_count(self, size: int):
    """Returns the smallest power of 2 greater than or equal to size."""
    msb = 1 << (size.bit_length() - 1)
    return msb * 2 if msb < size else msb

  def _range_start(self, i: int):
    p = 1 << (i.bit_length() - 1)  # the first cell on the same level as i
    return p + (i - p) * self._range_length(p)

  def _range_length(self, i: int):
    return 1 << (self._tree_depth - i.bit_length())

  def _push_updates_down(self, ancestors):
    """Pushes updates down the tree."""
    for i in reversed(ancestors):
      if self._updates[i] == 0:
        continue
      li = 2 * i
      ri = li + 1
      self._values[li] += self._updates[i] * self._range_length(li)
      self._values[ri] += self._updates[i] * self._range_length(ri)
      self._updates[li] += self._updates[i]
      self._updates[ri] += self._updates[i]
      self._updates[i] = 0

  # --------------------------------------------------------------------------

  def _split(self, li: int, ri: int):
    """Splits the given range into base segments sorted from left to right."""
    # assert 0 <= li <= ri < self._leaf_count
    li += self._leaf_count
    ri += self._leaf_count
    split = []
    right_path = []
    while li <= ri:
      if li % 2 == 1:
        split.append(li)
        li += 1
      if ri % 2 == 0:
        right_path.append(ri)
        ri -= 1
      li //= 2
      ri //= 2
    split.extend(reversed(right_path))
    return split

  def _ancestors(self, i: int, j: int):
    """Rturns all ancestors of given cells bottom up."""
    # assert 1 <= i < self._node_count
    # assert 1 <= j < self._node_count
    ancestors = []
    i //= 2
    j //= 2
    while i != j:
      if i > j:
        ancestors.append(i)
        i //= 2
      else:
        ancestors.append(j)
        j //= 2
    while i > 0:
      ancestors.append(i)
      i //= 2
    return ancestors

    
from collections.abc import Sequence


class SlidingWindow:
  """Represents a sliding window algorithm framework.

  This class provides a structure for implementing sliding window algorithms.
  Concrete implementations should inherit from this class and override the
  should_contract_left() and is_window_good() methods.
  """

  class Observer:

    def init(self, sequence: Sequence):
      self.seq = sequence

    def start_run(self, _range):
      ...

    def finish_run(self):
      ...

    def enter_cell(self, right_idx: int):
      ...

    def exit_cell(self, left_idx: int):
      ...

  def __init__(self, sequence: Sequence, observer=None):
    self.seq = sequence
    self.observer = observer if observer is not None else self.Observer()
    self.observer.init(sequence)

  def should_contract_left(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def is_window_good(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def run(self, _range=None):
    _range = _range if _range is not None else range(len(self.seq))
    self.observer.start_run(_range)
    li = _range.start
    for ri in _range:
      self.observer.enter_cell(ri)
      while li <= ri and self.should_contract_left(li, ri):
        step = self.observer.exit_cell(li)
        li += step if step else _range.step
      if li <= ri and self.is_window_good(li, ri):
        yield li, ri
    self.observer.finish_run()


class LengthBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_len: int, max_len: int, observer=None):
    super().__init__(sequence, observer)
    self.min_len = min_len
    self.max_len = max_len

  def should_contract_left(self, li: int, ri: int) -> bool:
    return ri - li + 1 > self.max_len

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_len <= ri - li + 1 <= self.max_len


class AggregateBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_value, max_value, observer=None):
    super().__init__(sequence, observer)
    self.min_value = min_value
    self.max_value = max_value

  def should_contract_left(self, li: int, ri: int) -> bool:
    return self.observer.aggregate() > self.max_value

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_value <= self.observer.aggregate() <= self.max_value


class Count(SlidingWindow.Observer):

  def start_run(self, _range):
    from collections import Counter
    self.counter = Counter()

  def enter_cell(self, ri):
    self.counter[self.seq[ri]] += 1

  def exit_cell(self, li):
    val = self.seq[li]
    self.counter[val] -= 1
    if self.counter[val] == 0:
      del self.counter[val]


class Min(SlidingWindow.Observer):

  def start_run(self, _range):
    from collections import deque
    self._queue = deque()

  def enter_cell(self, ri: int):
    while self._queue and self.seq[self._queue[-1]] > self.seq[ri]:
      self._queue.pop()
    self._queue.append(ri)

  def exit_cell(self, li: int):
    while self._queue and self._queue[0] <= li:
      self._queue.popleft()

  def min(self):
    return self.seq[self.min_idx()]

  def min_idx(self):
    assert self._queue
    return self._queue[0]


class Sum(SlidingWindow.Observer):

  def start_run(self, _range):
    self.sum = 0

  def enter_cell(self, ri: int):
    self.sum += self.seq[ri]

  def exit_cell(self, li: int):
    self.sum -= self.seq[li]

  def aggregate(self):
    return self.sum
76700