<p>Given a 2D character matrix <code>grid</code>, where <code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>, return the number of <span data-keyword="submatrix">submatrices</span> that contain:</p>

<ul>
	<li><code>grid[0][0]</code></li>
	<li>an <strong>equal</strong> frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.</li>
	<li><strong>at least</strong> one <code>&#39;X&#39;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;X&quot;,&quot;Y&quot;,&quot;.&quot;],[&quot;Y&quot;,&quot;.&quot;,&quot;.&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/06/07/examplems.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 175px; height: 350px;" /></strong></p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;Y&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>No submatrix has an equal frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;.&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;.&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>No submatrix has at least one <code>&#39;X&#39;</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 1000</code></li>
	<li><code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>.</li>
</ul>

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        def cumsum2d(arr):
            result = [[0 for i in range(len(arr[0]))] for j in range(len(arr))]
            for i in range(len(arr)):
                sum = 0
                for j in range(len(arr[0])):
                    sum += arr[i][j]
                    result[i][j] = sum + (result[i-1][j] if i > 0 else 0)
            return result
        def query(cs2d, a, b, A, B): # a, b are the coordinates of the top left corner, A, B are the coordinates of the bottom right corner
            result = 0
            result += cs2d[A][B]
            result += cs2d[a-1][b-1] if a-1 >= 0 and b-1 >= 0 else 0
            result -= cs2d[a-1][B] if a-1 >= 0 else 0
            result -= cs2d[A][b-1] if b-1 >= 0 else 0
            return result
        x_grid = [[1 if x == 'X' else 0 for x in xs] for xs in grid]
        y_grid = [[1 if x == 'Y' else 0 for x in xs] for xs in grid]
        cs2d_x = cumsum2d(x_grid)
        cs2d_y = cumsum2d(y_grid)
        result = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                x_count = query(cs2d_x, 0, 0, i, j)
                y_count = query(cs2d_y, 0, 0, i, j)
                if x_count and x_count == y_count:
                    result += 1
        return result
120326