[JSOI2009] [Luogu P4054] [树状数组] 计数问题 ( 二维树状数组模板 )

二维树状数组板子
貌似还是紫掉蓝

题目描述

一个 \(\left(n\times m\right)\) 的方格，初始时每个格子有一个整数权值。接下来每次有2种操作：
改变一个格子的权值；
求一个子矩阵中某种特定权值出现的个数。

输入格式

第一行有两个数 \(N\),\(M\)。
接下来 \(N\) 行，每行 \(M\) 个数，第 \(i+1\) 行第 \(j\) 个数表示格子 \(\left(i,j\right)\) 的初始权值。
接下来输入一个整数 \(Q\)。
之后 \(Q\) 行，每行描述一个操作。

操作 \(1\)：“\(1\quad x\quad y\quad c\)”(不含双引号)。表示将格子 \(\left(x,y\right)\) 的权值改成 \(c\) \(\left( 1\le x\le n,1\le y\le m,1\le c\le 100\right)\)。
操作 \(2\)：“\(2\quad x_1\quad x_2\quad y_1\quad y_2\quad c\)”(不含双引号，\(x_1\le x_2,y_1\le y_2\))。表示询问所有满足格子颜色为 \(c\)，且 \(x_1\le x\le x_2\), \(y_1\le y\le y_2\)的格子\(\left(x,y\right)\)的个数。

输出格式

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

注意毒瘤输入
最后那里答案统计会产生重叠, 需要删去重叠部分
不开快读会 \(WA\)

代码:

# include <iostream>
# include <cstdio>
# define MAXN 305

using namespace std;

int c[MAXN][MAXN][101], a[MAXN][MAXN]; // c[x][y][col] 统计 col 出现的次数
int n, m;

int read(){
    char ch = getchar();
    int x = 0;
    while(ch < ‘0‘ || ch > ‘9‘) ch = getchar();
    while(ch >=‘0‘ && ch <=‘9‘){
        x = x * 10 + ch - ‘0‘;
        ch = getchar();
    }
    return x;
}

int Lowbit(int x){
    return x&(-x);
}

void Update(int x, int y, int col, int val){
    a[x][y] = col;
    for(int i = x; i <= n; i += Lowbit(i)){
        for(int j = y; j <= m; j += Lowbit(j)){
            c[i][j][col] += val;
        }
    }
}

long long Getsum(int x, int y, int col){
    long long ans = 0;
    for(int i = x; i; i -= Lowbit(i)){
        for(int j = y; j; j -= Lowbit(j)){
            ans += c[i][j][col];
        }
    }
    return ans;
}

int main(){
    int q, opt, xa, ya, xb, yb, tmp;
    
    n = read(), m =read();

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            tmp = read();
            Update(i, j, tmp, 1);
        }
    }

    q = read();

    for(int i = 1; i <= q; i++){
        opt = read();
        if(opt == 1){
            xa = read(), ya = read(), tmp = read();
            Update(xa, ya, a[xa][ya], -1);
            Update(xa, ya, tmp, 1);
        }
        else{
            xa = read(), xb = read(), ya = read(), yb = read(), tmp =read();
            cout<<Getsum(xb, yb, tmp) + Getsum(xa-1, ya-1, tmp) - Getsum(xa-1, yb, tmp) - Getsum(xb, ya-1, tmp) <<endl;
        }
    }

    return 0;
}

[JSOI2009] [Luogu P4054] [树状数组] 计数问题 ( 二维树状数组模板 )

原文：https://www.cnblogs.com/Foggy-Forest/p/13332342.html