<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 = RQRUArray(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 RQPUArray:  # RangeQueryPointUpdateArray

  def __init__(self, size: int):
    assert size > 0
    self._leaf_count = _get_required_leaf_count(size)
    self._node_count = self._leaf_count * 2  # including the sentinel 0th node
    # TODO: Choose a neutral value:
    self._values = [0] * self._node_count

  def query(self, li: int, ri: int):
    assert 0 <= li <= ri < self._leaf_count
    li += self._leaf_count
    ri += self._leaf_count
    # TODO: Implement the "combine" operation:
    return sum(self._values[i] for i in _get_smallest_cover(li, ri))

  def update(self, i: int, v):
    assert 0 <= i < self._leaf_count
    i += self._leaf_count
    for j in _get_ancestors(i):
      # TODO: Implement the "update" operation:
      self._values[j] = self._values[j] + v


class PQRUArray:  # PointQueryRangeUpdateArray

  def __init__(self, size: int):
    assert size > 0
    self._leaf_count = _get_required_leaf_count(size)
    self._node_count = self._leaf_count * 2  # including the sentinel 0th node
    # TODO: Choose a neutral value:
    self._values = [0] * self._node_count

  def query(self, i: int):
    assert 0 <= i < self._leaf_count
    i += self._leaf_count
    # TODO: Implement the "combine" operation:
    return sum(self._values[j] for j in _get_ancestors(i))

  def update(self, li: int, ri: int, v):
    assert 0 <= li <= ri < self._leaf_count
    li += self._leaf_count
    ri += self._leaf_count
    for j in _get_smallest_cover(li, ri):
      # TODO: Implement the "update" operation:
      self._values[j] = self._values[j] + v


class RQRUArray:  # RangeQueryRangeUpdateArray

  def __init__(self, size: int):
    assert size > 0
    self._leaf_count = _get_required_leaf_count(size)
    self._node_count = self._leaf_count * 2  # including the sentinel 0th node
    self._depth = self._leaf_count.bit_length()  # tree depth
    # TODO: Choose a neutral value:
    self.kNeutralValue = 0
    self._values = [self.kNeutralValue] * self._node_count
    self._updates = [self.kNeutralValue] * self._node_count

  def query(self, li: int, ri: int):
    assert 0 <= li <= ri < self._leaf_count
    cover = _get_smallest_cover(li + self._leaf_count, ri + self._leaf_count)
    ancestors = _get_ancestors(cover[0], cover[-1])
    self._push_updates(ancestors)
    # TODO: Implement the "combine" operation:
    return sum(self._values[i] for i in cover)

  def update(self, li: int, ri: int, v):
    assert 0 <= li <= ri < self._leaf_count
    cover = _get_smallest_cover(li + self._leaf_count, ri + self._leaf_count)
    ancestors = _get_ancestors(cover[0], cover[-1])
    self._push_updates(ancestors)
    for i in cover:
      self._update(i, v)
    for i in ancestors:
      # TODO: Implement the "combine" operation:
      self._values[i] = self._values[2 * i] + self._values[2 * i + 1]

  def _push_updates(self, ancestors):
    for i in reversed(ancestors):  # from top to bottom
      if self._updates[i] == self.kNeutralValue: continue
      self._update(2 * i, self._updates[i])
      self._update(2 * i + 1, self._updates[i])
      self._updates[i] = self.kNeutralValue

  def _update(self, i: int, v):
    # TODO: Implement the "update" operation:
    self._values[i] = self._values[i] + v * _range_size(i, self._depth)
    self._updates[i] = self._updates[i] + v


# ----------------------------------------------------------------------------
# Helper Functions
# ----------------------------------------------------------------------------


def _get_required_leaf_count(size: int):
  """Calculates the required number of leaf nodes for a segment tree.

  Segment trees require a complete binary tree structure, hence the number of
  leaf nodes needed to accommodate elements with indices in the range [0, size)
  needs to be 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(i: int, tree_depth: int):
  """
  Calculates the starting index of the segment represented by the i-th node in
  the segment tree.
  """
  level_start = 1 << (i.bit_length() - 1)  # first node on the same level as i
  return level_start + (i - level_start) * _range_size(i, tree_depth)


def _range_size(i: int, tree_depth: int):
  """
  Calculates the length (size) of the segment represented by the i-th node in
  the segment tree.
  """
  return 1 << (tree_depth - i.bit_length())


def _get_smallest_cover(i: int, j: int):
  """Finds the smallest set of segments that cover the given range.

  Computes the smallest set of segments (represented by nodes) in a segment
  tree that completely covers the range between nodes i and j (inclusive).
  Each node in the resulting list represents a segment that lies entirely
  within the given range. Nodes in the list are arranged from left to right. 

  The list includes:
    - Right children of nodes on the path from leaf node i to the LCA(i, j).
    - Left children of nodes on the path from the LCA(i, j) to leaf node j.
  """
  # assert 0 < i <= j and i.bit_length() == j.bit_length()
  ans = []
  left_children = []
  while i <= j:
    if i % 2 == 1:
      ans.append(i)
      i += 1
    if j % 2 == 0:
      left_children.append(j)
      j -= 1
    i //= 2
    j //= 2
  ans.extend(reversed(left_children))
  return ans


def _get_ancestors(i: int, j: int = None):
  """Finds the list of ancestors of given nodes in a segment tree.

  If only one node 'i' is provided, the list of ancestors includes 'i' itself.
  If two node indices 'i' and 'j' are provided, the list contains all their
  ancestors, with common ancestors de-duped.

  Nodes in the list are arranged in a bottom-up order.
  """
  if j is None:
    ans = [i]
    j = i
  else:
    ans = []
  # assert 0 < i <= j
  i //= 2
  j //= 2
  while i != j:
    if i > j:
      ans.append(i)
      i //= 2
    else:
      ans.append(j)
      j //= 2
  while i > 0:
    ans.append(i)
    i //= 2
  return ans

    
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
77100