BZOJ 1452: [JSOI2009]Count 二维树状数组

1452: [JSOI2009]Count

Description

Input

Output

Sample Input

Sample Output

1
2

HINT

Source

题解：设定C[101][N][N] 树状数组上价值为val的lowbit数组

//meek

///#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#include <set>

#include <stack>

#include <sstream>

#include <vector>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

#define fi first

#define se second

#define MP make_pair

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//****************************************

const int N=;

const ll INF = 1ll<<;

const int inf = <<;

const int mod= ;

int C[][][],a[][],n,m;

void update(int x,int y,int c,int val) {

    for(int i=x;i<=N;i+=i&(-i)) {

        for(int j=y;j<=N;j+=j&(-j)) {

            C[c][i][j]+=val;

        }

    }

}

int ask(int x,int y,int c) {

    int sum=;

    for(int i=x;i>=;i-=i&(-i)) {

        for(int j=y;j>=;j-=j&(-j)) {

            sum+=C[c][i][j];

        }

    }

    return sum;

}

int main() {

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) {

        for(int j=;j<=m;j++) scanf("%d",&a[i][j]),update(i,j,a[i][j],);

    }

    int q,x,y,t,c,x1,x2,y1,y2;

    scanf("%d",&q);

    for(int i=;i<=q;i++) {

        scanf("%d",&t);

        if(t==) {

            scanf("%d%d%d",&x,&y,&c);

            update(x,y,a[x][y],-);

            a[x][y]=c;

            update(x,y,c,);

        }

        else {

            scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);

            printf("%d\n",(ask(x2,y2,c)-ask(x1-,y2,c)-ask(x2,y1-,c)+ask(x1-,y1-,c)));

        }

    }

    return ;

}

代码