题目地址：洛谷：【P4054】[JSOI2009]计数问题 – 洛谷、BZOJ：Problem 1452. — [JSOI2009]Count

题目描述

一个n*m的方格，初始时每个格子有一个整数权值。接下来每次有2种操作：

• 改变一个格子的权值；
• 求一个子矩阵中某种特定权值出现的个数。

输入输出格式

输入格式：
第一行有两个数N,M。
接下来N行，每行M个数，第i+1行第j个数表示格子(i,j)的初始权值。
接下来输入一个整数Q。
之后Q行，每行描述一个操作。
操作1：“1 x y c”(不含双引号)。表示将格子(x,y)的权值改成c（1<=x<=n,1<=y<=m,1<=c<=100)。
操作2：“2 x1 x2 y1 y2 c”(不含双引号，x1<=x2,y1<=y2)。表示询问所有满足格子颜色为c，且x1<=x<=x2,y1<=y<=y2的格子(x,y)的个数。

输出格式：
对于每个操作2，按照在输入中出现的顺序，依次输出一行一个整数表示所求得的个数。

输入输出样例

输入样例#1：

3 3
1 2 3
3 2 1
2 1 3
3
2 1 2 1 2 1
1 2 3 2
2 2 3 2 3 2

输出样例#1：

1
2

说明

数据规模：
30%的数据，满足：n,m<=30,Q<=50000
100%的数据，满足：n,m<=300,Q<=200000

题解

注意到权值的范围很小，对每个权值开一个二维树状数组即可。二维树状数组可以理解成树状数组套树状数组。
复杂度$O(n \log^2 n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 305;

int n, m, q, tr[105][MAXN][MAXN], a[MAXN][MAXN];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int y, int w, int v) {
    for(int i = x; i <= n; i += lowbit(i)) {
        for(int j = y; j <= m; j += lowbit(j)) {
            tr[w][i][j] += v;
        }
    }
}

inline int query(int x, int y, int w) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        for(int j = y; j; j -= lowbit(j)) {
            res += tr[w][i][j];
        }
    }
    return res;
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            a[i][j] = readint();
            add(i, j, a[i][j], 1);
        }
    }
    q = readint();
    while(q--) {
        int op = readint();
        if(op == 1) {
            int x = readint(), y = readint(), c = readint();
            add(x, y, a[x][y], -1);
            a[x][y] = c;
            add(x, y, a[x][y], 1);
        } else {
            int x1 = readint(), x2 = readint(), y1 = readint(), y2 = readint(), c = readint();
            printf("%d\n", query(x2, y2, c) - query(x1 - 1, y2, c) - query(x2, y1 - 1, c) + query(x1 - 1, y1 - 1, c));
        }
    }
    return 0;
}