Day6 - C - Count HYSBZ - 1452 /1452: [JSOI2009]Count

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 = ;

int C[maxm][maxm][], 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 = ;

    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-, val) - getsum(xa-, yb, val) + getsum(xa-, ya-, val);

}

int main() {

    scanf("%d%d", &N, &M);

    int t;

    for(int i = ; i <= N; ++i)

        for(int j = ; j <= M; ++j) {

            scanf("%d", &t);

            B[i][j] = t;

            add(i, j, t, );

        }

    int Q, type, xa, xb, ya, yb, c;

    scanf("%d", &Q);

    while(Q--) {

        scanf("%d", &type);

        if(type == ) {

            scanf("%d%d%d", &xa, &ya, &c);

            add(xa, ya, B[xa][ya], -);

            B[xa][ya] = c;

            add(xa, ya, c, );

        } else if(type == ) {

            scanf("%d%d%d%d%d", &xa, &xb, &ya, &yb, &c);

            printf("%d\n", range_getsum(xa, ya, xb, yb, c));

        }

    }

    return ;

}