<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>

class RangeQuery:
    def __init__(self, data, func=max):
        self.func = func
        self._data = _data = [list(data)]
        self.n = len(data)
        i, n = 1, len(_data[0])
        while 2 * i <= n:
            prev = _data[-1]
            _data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
            i <<= 1

    def query(self, start, stop):
        if start >= stop:
            return -inf
        """func of data[start, stop)"""
        depth = (stop - start).bit_length() - 1
        return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

    def __getitem__(self, idx):
        return self._data[0][idx]
            
class Solution:
    def maximumValueSum(self, A):
        R, C = len(A), len(A[0])
        vals = []
        for i in range(R):
            for j in range(C):
                vals.append([A[i][j], i, j])

        di, dj = defaultdict(list), defaultdict(list)
        for i in range(R):
            for j in range(C):
                di[i].append((A[i][j], i, j))
                dj[j].append((A[i][j], i, j))
        s = set()
        for i in range(R):
            di[i].sort(reverse=True)
            for x in di[i][:10]:
                s.add(x)
        for j in range(C):
            dj[j].sort(reverse=True)
            for x in dj[j][:10]:
                s.add(x)
        
        s = list(s)
        s.sort(reverse=True)
        ss = list(s)[:36]
        ss = [x[1:] for x in ss]
        s = list(s)[:36]
        s = [x[1:] for x in s]
        #s.sort()
        stl = []
        for i in range(R):
            stl.append(RangeQuery(A[i]))
        ans = -inf
        for i in range(len(s)):
            for j in range(len(ss)):
                if s[i][0] == ss[j][0] or s[i][1] == ss[j][1]:
                    continue
                tmp = A[s[i][0]][s[i][1]] + A[ss[j][0]][ss[j][1]]
                jjl, jjr = min(s[i][1], ss[j][1]), max(s[i][1], ss[j][1])
                maxi = -inf
                #for ii in range(s[j][0]+1, R):
                for ii in range(R):
                    if ii != s[i][0] and ii != ss[j][0]:
                        maxi = max(maxi, stl[ii].query(0, jjl), stl[ii].query(jjl+1, jjr), stl[ii].query(jjr+1, C))
                tmp += maxi
                if tmp > ans:
                    #print(A[s[i][0]][s[i][1]] , A[s[j][0]][s[j][1]], maxi)
                    ans = tmp
        return ans
                
            

84853