## 题目链接：

http://exam.upc.edu.cn/problem.php?id=5911

## 题目：

### 样例输入

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
2

## 思路：

注意到$c$的范围只有$[1, 100]$，考虑开100个二维树状数组，维护矩阵内某一个数字的计数。单次查询复杂度$O(log_2n \times log_2 m)$

## 实现：

#include <cstdio>
int n, m, q, x, x_, y, y_, op, tmp, map[307][307];
struct Tree {
int data[307][307];
int lowbit(int x) {
return x & -x;
}
void update(int x, int y, int w) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= n; j += lowbit(j)) {
data[i][j] += w;
}
}
}
int query(int x, int y) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
ans += data[i][j];
}
}
return ans;
}
} tree[107];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", map[i] + j), tree[map[i][j]].update(i, j, 1);
scanf("%d", &q);
while (q--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%d", &x, &y, &tmp);
tree[map[x][y]].update(x, y, -1);
map[x][y] = tmp;
tree[tmp].update(x, y, 1);
} else {
scanf("%d%d%d%d%d", &x, &x_, &y, &y_, &tmp);
int ret = tree[tmp].query(x_, y_) - tree[tmp].query(x - 1, y_) - tree[tmp].query(x_, y - 1) + tree[tmp].query(x - 1, y - 1);
printf("%d\n", ret);
}
}
return 0;
}