BZOJ 1452 Count(二维树状数组)

大水题。 建立100个二维树状数组,总复杂度就是O(qlognlogm).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

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

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int tree[][N][N], a[N][N], n, m;

void add(int x, int i, int j, int val){

    while (i<=n) {

        int k=j;

        while (k<=m) tree[x][i][k]+=val, k+=lowbit(k);

        i+=lowbit(i);

    }

}

int query(int x, int i, int j){

    int res=;

    while (i) {

        int k=j;

        while (k) res+=tree[x][i][k], k-=lowbit(k);

        i-=lowbit(i);

    }

    return res;

}

int main ()

{

    int Q, flag, x1, y1, x2, y2, c;

    n=Scan(); m=Scan();

    FOR(i,,n) FOR(j,,m) {

        a[i][j]=Scan();

        add(a[i][j],i,j,);

    }

    Q=Scan();

    while (Q--) {

        flag=Scan();

        if (flag==) {

            x1=Scan(); y1=Scan(); c=Scan();

            add(a[x1][y1],x1,y1,-); add(c,x1,y1,);

            a[x1][y1]=c;

        }

        else {

            x1=Scan(); x2=Scan(); y1=Scan(); y2=Scan(); c=Scan();

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

        }

    }

    return ;

}