方格计数问题(Counting Problem) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

int N, M;
int bit[101][305][305];
int grid[305][305];

void add(int c, int x, int y, int v) {
    for (int i = x; i <= N; i += i & -i) {
        for (int j = y; j <= M; j += j & -j) {
            bit[c][i][j] += v;
        }
    }
}

int sumPrefix(int c, int x, int y) {
    int s = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            s += bit[c][i][j];
        }
    }
    return s;
}

int queryRect(int c, int x1, int x2, int y1, int y2) {
    return sumPrefix(c, x2, y2) - sumPrefix(c, x1 - 1, y2) - sumPrefix(c, x2, y1 - 1) + sumPrefix(c, x1 - 1, y1 - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> M)) return 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cin >> grid[i][j];
            add(grid[i][j], i, j, 1);
        }
    }
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y, c;
            cin >> x >> y >> c;
            add(grid[x][y], x, y, -1);
            grid[x][y] = c;
            add(c, x, y, 1);
        } else {
            int x1, x2, y1, y2, c;
            cin >> x1 >> x2 >> y1 >> y2 >> c;
            cout << queryRect(c, x1, x2, y1, y2) << "\n";
        }
    }
    return 0;
}