LC 6260. 矩阵查询可获得的最大分数

https://leetcode.cn/problems/maximum-number-of-points-from-grid-queries/

这题从数据规模上看就需要进行离线处理。

批量计算的目的是求解：如果满足X值的话，最多可以访问多少个点。整个过程类似于BFS/Dijkstra算法，只不过每次扩展的时候，如果下一个点的值小于当前点的话，需要使用当前点的值进行扩展。

我们将可以访问到的值，记录在 `points` 这个字典里面。不过需要注意的是，这个 `points` 里面存储并不是累加的结果，也就是假设X<Y, points[Y]里面并没有包含points[X]里面的值，这个最后需要累加起来。

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        from collections import Counter
        import heapq
        points = Counter()

        n, m = len(grid), len(grid[0])
        dq = []
        dq.append((grid[0][0], 0, 0))
        visited = set()
        visited.add((0, 0))
        while dq:
            (v, x, y) = heapq.heappop(dq)
            points[v] += 1
            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                x2, y2 = x + dx, y + dy
                if 0 <= x2 < n and 0 <= y2 < m:
                    if (x2, y2) not in visited:
                        visited.add((x2, y2))
                        value = max(grid[x2][y2], v)
                        heapq.heappush(dq, (value, x2, y2))

得到 points 这个数组之后，我们可以将Query合并进行，使用Marzullo算法，就可以得到每个query对应的结果。

我们这里设置 query对应的 event_type=0, 而points对应的 event_type=1, 因为query查询的是严格大于当前单元格的结果。

events = [(k, 1, v) for k, v in points.items()]
events += [(q, 0, i) for (i, q) in enumerate(queries)]
events.sort()
ans = [0] * len(queries)

res = 0
for k, ev, v in events:
    if ev == 0:
        ans[v] = res
    else:
        res += v
return ans