「BZOJ1452」[JSOI2009]Count

Description

一个N×MN\times M的方格,初始时每个格子有一个整数权值,接下来每次有22个操作:

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

Input

每一行有两个数字NNMM
接下来NN行,每行MM个数字。第i+1i+1行第jj个数字表示格子(i,j)(i,j)的初值
接下来输入一个QQ,后面QQ行每行描述一个操作
操作11:
1 x y c,表示将格子(x,y)(x,y)的值变为cc
操作2:
2 x1 x2 y1 y2 c,表示询问所有满足格子中数字为cc的格子数字

Output

对于每个操作22,按输入中出现的顺序,依次输出一行一个整数表示所求得的个数

Sample Input

1
2
3
4
5
6
7
8
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

Sample Output

1
2
1
2

HINT

n,m300,Q5000n,m\leq 300,Q\leq 5000
1xN,1yM,1c1001\leq x\leq N,1\leq y\leq M,1\leq c\leq 100
x1xx2,y1yy2x_1\leq x\leq x_2,y_1\leq y\leq y_2

Solution

二维树状数组裸体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 310;
int a[N][N];
int n, m;

struct T {
int c[N][N];
void add(int x, int y, int v) {
for(; x <= n; x += x & -x)
for(int dy = y; dy <= m; dy += dy & -dy)
c[x][dy] += v;
}
int query(int x, int y) {
int res = 0;
for(; x; x -= x & -x)
for(int dy = y; dy; dy -= dy & -dy)
res += c[x][dy];
return res;
}
int ask(int x1, int y1, int x2, int y2) {

return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
}c[110];

int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
a[i][j] = read();
c[a[i][j]].add(i, j, 1);
}
int Q = read();
for(int i = 1; i <= Q; ++i) {
int op = read();
if(op == 1) {
int x = read(), y = read(), t = read();
c[a[x][y]].add(x, y, -1);
c[t].add(x, y, 1);
a[x][y] = t;
} else {
int x1 = read(), x2 = read(), y1 = read(), y2 = read(), t = read();
writeln(c[t].ask(x1, y1, x2, y2));
}
}
return 0;
}