<p>You are given a <strong>0-indexed</strong> <code>m x n</code> integer matrix <code>grid</code>. Your initial position is at the <strong>top-left</strong> cell <code>(0, 0)</code>.</p>

<p>Starting from the cell <code>(i, j)</code>, you can move to one of the following cells:</p>

<ul>
	<li>Cells <code>(i, k)</code> with <code>j &lt; k &lt;= grid[i][j] + j</code> (rightward movement), or</li>
	<li>Cells <code>(k, j)</code> with <code>i &lt; k &lt;= grid[i][j] + i</code> (downward movement).</li>
</ul>

<p>Return <em>the minimum number of cells you need to visit to reach the <strong>bottom-right</strong> cell</em> <code>(m - 1, n - 1)</code>. If there is no valid path, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex1.png" style="width: 271px; height: 171px;" />
<pre>
<strong>Input:</strong> grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The image above shows one of the paths that visits exactly 4 cells.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/25/ex2.png" style="width: 271px; height: 171px;" />
<pre>
<strong>Input:</strong> grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
<strong>Output:</strong> 3
<strong>Explanation: </strong>The image above shows one of the paths that visits exactly 3 cells.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/26/ex3.png" style="width: 181px; height: 81px;" />
<pre>
<strong>Input:</strong> grid = [[2,1,0],[1,0,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> It can be proven that no path exists.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= grid[i][j] &lt; m * n</code></li>
	<li><code>grid[m - 1][n - 1] == 0</code></li>
</ul>

class Solution:
  def minimumVisitedCells(self, grid: List[List[int]]) -> int:
    row_count = len(grid)
    col_count = len(grid[0])
    rows = [PQRUArray(col_count) for _ in range(row_count)]
    cols = [PQRUArray(row_count) for _ in range(col_count)]
    rows[0].update(0, 0, 1)
    for ri in range(row_count):
      for ci in range(col_count):
        min_cell_count = min(rows[ri].query(ci), cols[ci].query(ri))
        if grid[ri][ci] == 0:
          continue
        if ci + 1 < col_count:
          rows[ri].update(ci + 1, min(ci + grid[ri][ci], col_count - 1), min_cell_count + 1)
        if ri + 1 < row_count:
          cols[ci].update(ri + 1, min(ri + grid[ri][ci], row_count - 1), min_cell_count + 1)
    return min_cell_count if min_cell_count != math.inf else -1


import math


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 = [math.inf] * 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 min(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] = min(self._values[j], 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
6918