Day6

Description

一个N*M的方格，初始时每个格子有一个整数权值，接下来每次有2个操作:

改变一个格子的权值

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

 

Input

每一行有两个数字N，M

接下来N行，每行M个数字。第i+1行第j个数字表示格子(i,j)的初值

接下来输入一个Q，后面Q行每行描述一个操作

操作1:

1 x y c，表示将格子(x,y)的值变为c

操作2:

2 x1 x2 y1 y2 c，表示询问所有满足格子中数字为c的格子数字

(n,m<=300,Q<=5000)

(1<=x<=N,1<=y<=M,1<=c<=100)

(x1<=x<=x2,y1<=y<=y2)

Output

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

Sample Input

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

 

思路：简单的二维树状数组，看数据只有300，权值只有100，那就为每个权值都设一个树状数组即可，其他没什么区别

#define lowbit(x) ((x)&(-x))
typedef long long LL;

const int maxm = 305;

int C[maxm][maxm][105], N, M, B[maxm][maxm];

void add(int x, int y, int val, int k) {
    for(int i = x; i <= N; i += lowbit(i))
        for(int j = y; j <= M; j += lowbit(j))
            C[i][j][val] += k;
}

int getsum(int x, int y, int val) {
    int ret = 0;
    for(int i = x; i; i -= lowbit(i))
        for(int j = y; j; j -= lowbit(j))
            ret += C[i][j][val];
    return ret;
}

int range_getsum(int xa, int ya, int xb, int yb, int val) {
    return getsum(xb, yb, val) - getsum(xb, ya-1, val) - getsum(xa-1, yb, val) + getsum(xa-1, ya-1, val);
}

int main() {
    scanf("%d%d", &N, &M);
    int t;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j) {
            scanf("%d", &t);
            B[i][j] = t;
            add(i, j, t, 1);
        }
    int Q, type, xa, xb, ya, yb, c;
    scanf("%d", &Q);
    while(Q--) {
        scanf("%d", &type);
        if(type == 1) {
            scanf("%d%d%d", &xa, &ya, &c);
            add(xa, ya, B[xa][ya], -1);
            B[xa][ya] = c;
            add(xa, ya, c, 1);
        } else if(type == 2) {
            scanf("%d%d%d%d%d", &xa, &xb, &ya, &yb, &c);
            printf("%d
", range_getsum(xa, ya, xb, yb, c));
        }
    }
    return 0;
}