3933. Largest Local Values in a Matrix II

You are given an n x m integer matrix matrix containing non-negative integers.

A non-zerocell (row, col) checks the cells near it as follows:

• Let x = matrix[row][col].
• Consider every cell within x rows and x columns of (row, col).
• Ignore cells that are outside the matrix.
• Ignore the cells where both the row distance and column distance are exactly x.

The cell (row, col) is a local maximum if it is non-zero and no considered cell has a value greater than x.

Return an integer denoting the number of local maximums in matrix.

​​​​​​​Example 1:

Input: matrix = [[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,2,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]
Output: 1
​​​​​​​​​​​​​​​​​​​​​
Explanation:

For the non-zero cell (3, 3), x = matrix[3][3] = 2.
The highlighted cells are the considered cells within x rows and x columns of (3, 3).
The four cells with both row and column distances equal to x = 2 are ignored.
No considered cell has a value greater than 2, so (3, 3) is a local maximum.
There are no other non-zero cells, so the answer is 1.

int fenwick[202][202];
void update(int i, int j) {
    for(int x = i + 1; x < 202; x += x & -x) {
        for(int y = j + 1; y < 202; y += y & -y) {
            fenwick[x][y] += 1;
        }
    }
}
int query(int i, int j) {
    int res = 0;
    for(int x = i + 1; x; x -= x & -x) {
        for(int y = j + 1; y; y -= y & -y) {
            res += fenwick[x][y];
        }
    }
    return res;
}
int query(int y1, int x1, int y2, int x2) {
    int res = query(y2,x2);
    if(y1 > 0) res -= query(y1 -1, x2);
    if(x1 > 0) res -= query(y2, x1 - 1);
    if(y1 > 0 and x1 > 0) res += query(y1 - 1, x1 - 1);
    return res;
}

class Solution {
public:
    int countLocalMaximums(vector<vector<int>>& matrix) {
        priority_queue<array<int,3>,vector<array<int,3>>> q;
        int n = matrix.size(), m = matrix[0].size();
        memset(fenwick, 0, sizeof fenwick);
        for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
                if(matrix[i][j]) q.push({matrix[i][j],i,j});
            }
        int res = 0;
        while(q.size()) {
            int x = q.top()[0];
            queue<pair<int,int>> qq;
            while(q.size() and q.top()[0] == x) {
                auto [_,i,j] = q.top(); q.pop();
                int y1 = i - x, y2 = i + x, x1 = j - x, x2 = j + x;
                int sum = query(max(0,y1), max(0,x1), min(n-1,y2), min(m-1,x2));
                for(auto& py : {y1,y2}) for(auto& px : {x1,x2}) {
                    if(0 <= py and py < n and 0 <= px and px < m and matrix[py][px] > x) sum--;
                }
                res += sum == 0;
                qq.push({i,j});

            }
            while(qq.size()) {
                auto [i,j] = qq.front(); qq.pop();
                update(i,j);
            }
        }
        return res;
    }
};