<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
  """Array with support for range queries and point updates.

  Allows efficient calculation of a combined value over a specified range,
  and updating individual cells within the array.
  """

  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):
    """Performs a range query, combining values within the range [li, ri]."""
    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):
    """Updates the element at index 'i' with the new value '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
  """Array with support for point queries and range updates.

  Allows efficient retrieval of the value at a specific index,
  and updating a range of vells within the array.
  """

  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):
    """Performs a point query, retrieving the value at index 'i'."""
    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):
    """Updates cells within the range [li, ri] using the value '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
  """Array with support for range queries and range updates.

  Allows efficient calculation of a combined value over a specified range,
  and updating ranges of cells within the array.
  """

  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):
    """Performs a range query, combining values within the range [li, ri]."""
    assert 0 <= li <= ri < self._leaf_count
    cover = _get_smallest_cover(li + self._leaf_count, ri + self._leaf_count)
    ancestors = _get_ancestors(cover[0] // 2, cover[-1] // 2)
    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):
    """Updates cells within the range [li, ri] using the value '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] // 2, cover[-1] // 2)
    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):
    """Propagates pending updates down the tree from ancestors to children."""
    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):
    """Applies an update to a specific node and its lazy update value."""
    # 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 two node indices 'i' and 'j' are provided, the list contains all their
  ancestors, with common ancestors de-duplicated.

  Nodes in the list are arranged in a bottom-up order with i and j in the front.
  """
  if j is None: j = i
  # assert 0 < i <= j
  ans = []
  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
76000