1452: [JSOI2009]Count

二维树状数组裸题

1452: [JSOI2009]Count

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 2753  Solved: 1608
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

1
2

#include <bits/stdc++.h>
using namespace std;
int d[305][305][101];
int a[305][305];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
int n,m;
int get_id(int x){
    return x&(-x);
}
void update(int x,int y,int c,int vul){
    for(int i=x;i<=n;i+=get_id(i)){
        for(int j=y;j<=m;j+=get_id(j)){
            d[i][j][c]+=vul;
        }
    }
}
int Sum(int x,int y,int c){
    int sum=0;
    for(int i=x;i>=1;i-=get_id(i)){
        for(int j=y;j>=1;j-=get_id(j)){
            sum+=d[i][j][c];
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            update(i,j,a[i][j],1);
        }
    }
    int q;scanf("%d",&q);
    int op,t1,t2,t3,t4,t5;
    while(q--){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&t1,&t2,&t3);
            update(t1,t2,a[t1][t2],-1);
            update(t1,t2,t3,1);
            a[t1][t2]=t3;
        }
        else{
            scanf("%d%d%d%d%d",&t1,&t2,&t3,&t4,&t5);
            printf("%d
",Sum(t2,t4,t5)-Sum(t1-1,t4,t5)-Sum(t2,t3-1,t5)+Sum(t1-1,t3-1,t5));
        }
    }
    return 0;
}