<p>You are given a <code>m x n</code> 2D array <code>board</code> representing a chessboard, where <code>board[i][j]</code> represents the <strong>value</strong> of the cell <code>(i, j)</code>.</p>

<p>Rooks in the <strong>same</strong> row or column <strong>attack</strong> each other. You need to place <em>three</em> rooks on the chessboard such that the rooks <strong>do not</strong> <strong>attack</strong> each other.</p>

<p>Return the <strong>maximum</strong> sum of the cell <strong>values</strong> on which the rooks are placed.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = </span>[[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]</p>

<p><strong>Output:</strong> 4</p>

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/08/rooks2.png" style="width: 294px; height: 450px;" /></p>

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 3)</code>, and <code>(2, 1)</code> for a sum of <code>1 + 1 + 2 = 4</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,2,3],[4,5,6],[7,8,9]]</span></p>

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

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

<p>We can place the rooks in the cells <code>(0, 0)</code>, <code>(1, 1)</code>, and <code>(2, 2)</code> for a sum of <code>1 + 5 + 9 = 15</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,1,1],[1,1,1],[1,1,1]]</span></p>

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

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

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 1)</code>, and <code>(2, 0)</code> for a sum of <code>1 + 1 + 1 = 3</code>.</p>
</div>

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

<ul>
	<li><code>3 &lt;= m == board.length &lt;= 500</code></li>
	<li><code>3 &lt;= n == board[i].length &lt;= 500</code></li>
	<li><code>-10<sup>9</sup> &lt;= board[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

import heapq
from functools import cache

class SegmentTree2D:
    def __init__(self, matrix):
        if not matrix:
            return
        
        self.n = len(matrix)
        self.m = len(matrix[0])
        self.tree = [[(float('-inf'), -1)] * (2 * self.m) for _ in range(2 * self.n)]
        self._build(matrix)

    def _build(self, matrix):
        for i in range(self.n):
            row_offset = i + self.n
            for j in range(self.m):
                col_offset = j + self.m
                self.tree[row_offset][col_offset] = (matrix[i][j], i)
        
        for i in range(self.n):
            row_offset = i + self.n
            for j in range(self.m - 1, 0, -1):
                left_child = self.tree[row_offset][j * 2]
                right_child = self.tree[row_offset][j * 2 + 1]
                self.tree[row_offset][j] = max(left_child, right_child, key=lambda x: x[0])
        
        for i in range(self.n - 1, 0, -1):
            for j in range(2 * self.m):
                top_child = self.tree[i * 2][j]
                bottom_child = self.tree[i * 2 + 1][j]
                self.tree[i][j] = max(top_child, bottom_child, key=lambda x: x[0])

    def query(self, row1, col1, row2, col2):
        row1 += self.n
        row2 += self.n
        col1 += self.m
        col2 += self.m
        result = (float('-inf'), -1)
        
        while row1 <= row2:
            if row1 % 2 == 1:
                c1, c2 = col1, col2
                while c1 <= c2:
                    if c1 % 2 == 1:
                        result = max(result, self.tree[row1][c1], key=lambda x: x[0])
                        c1 += 1
                    if c2 % 2 == 0:
                        result = max(result, self.tree[row1][c2], key=lambda x: x[0])
                        c2 -= 1
                    c1 //= 2
                    c2 //= 2
                row1 += 1
            if row2 % 2 == 0:
                c1, c2 = col1, col2
                while c1 <= c2:
                    if c1 % 2 == 1:
                        result = max(result, self.tree[row2][c1], key=lambda x: x[0])
                        c1 += 1
                    if c2 % 2 == 0:
                        result = max(result, self.tree[row2][c2], key=lambda x: x[0])
                        c2 -= 1
                    c1 //= 2
                    c2 //= 2
                row2 -= 1
            row1 //= 2
            row2 //= 2
        
        return result
    
class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        st = SegmentTree2D(board)
        height = len(board)
        width = len(board[0])
        
        res = -float('inf')
        
        def constructSegments(height, blockedRows):
            blockedRows.sort()
            segments = []
            prev = 0

            for b in blockedRows:
                if b > prev:
                    segments.append([prev, b - 1])
                prev = b + 1

            if prev <= height - 1:
                segments.append([prev, height - 1])

            return segments

        @cache
        def wrapper(r1, c1, r2, c2):
            return st.query(r1, c1, r2, c2)
        
        for r in range(height):
            if width > 3:
                largest_three = heapq.nlargest(3, range(width), key=lambda c: board[r][c])
            else:
                largest_three = range(width)
            
            for c in largest_three:
                center = board[r][c]
                
                regions = []
                if r > 0:
                    regions.append((0, c + 1, r - 1, width - 1))
                
                if r != height - 1:
                    regions.append((r + 1, c + 1, height - 1, width - 1))
                
                maxRightScore = -float('inf')
                rowOccurence = None
                for region in regions:
                    q = wrapper(region[0], region[1], region[2], region[3])
                    maxRightScoreHere = q[0]
                    if maxRightScoreHere > maxRightScore:
                        maxRightScore = maxRightScoreHere
                        rowOccurence = q[1]
                
                if rowOccurence == r:
                    blockedRows = [r]
                else:
                    if rowOccurence != None:
                        blockedRows = [r, rowOccurence]
                    else:
                        blockedRows = [r]
                rowSegments = constructSegments(height, blockedRows)
                
                leftC1 = 0
                leftC2 = c - 1
                bigLeft = -float('inf')
                for r1, r2 in rowSegments:
                    q = wrapper(r1, leftC1, r2, leftC2)
                    bigLeft = max(bigLeft, q[0])
                
                score = center + maxRightScore + bigLeft
                res = max(score, res)
                
                regions = []
                
                if r > 0:
                    regions.append((0, 0, r - 1, c - 1))
                if r != height - 1:
                    regions.append((r + 1, 0, height - 1, c - 1))
                
                maxLeftScore = -float('inf')
                rowOcc = None
                for region in regions:
                    q = wrapper(region[0], region[1], region[2], region[3])
                    maxLeftScoreHere = q[0]
                    if maxLeftScoreHere > maxLeftScore:
                        maxLeftScore = maxLeftScoreHere
                        rowOcc = q[1]
                
                if rowOcc == r:
                    blockedRows = [r]
                else:
                    if rowOcc != None:
                        blockedRows = [r, rowOcc]
                    else:
                        blockedRows = [r]
                rowSegments = constructSegments(height, blockedRows)
                
                rightC1 = c + 1
                rightC2 = width - 1
                bigRight = -float('inf')
                for r1, r2 in rowSegments:
                    q = wrapper(r1, rightC1, r2, rightC2)
                    bigRight = max(bigRight, q[0])
                
                score = center + maxLeftScore + bigRight
                res = max(score, res)
        
        return res
47971