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

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1452

题目大意：给一个数字矩阵，两种操作。1.把（x，y）位置的数字改成z，2.查询（x1,y1）(x2,y2)构成的矩阵里头有多少个z

题目解析：

       我们首先考虑一维的情况，L到R有多少个z，为了优化我们开一个二维数组，记录每个z的前缀和，但是对于可修改的在线询问，一个一个的改前缀和是不是很费时，所以用一维树状数组优化。

     好，此时我们已经解决了一维的这个问题。但是这个是二维的，我们怎么搞。

      首先我们把待查询区间分成四块（纸上比划比划）

      1.（1，1）到（x2 , y2）;

      2.（1，1）到（x1-1,y1-1）;

      3.（1，1）到（x2,y1-1）;

      4.（1，1）到（x1-1,y2）;

那么(x1,y1)到（x2,y2）的z的个数就是 （手懒直接写上述编号的z的个数）1减3减4加2；

      我们暂且看作我们每行都建立了一个树状数组（修改时间肯定超，总不能一行一行的改吧），这样我们可以暴力每一行，再结合上边说的一维的操作。好我们现在解决超时。

      y坐标方向我们用了树状数组优化，那么行方向可不可以呢，答案是可以的，这样就像两个树状数组重叠一下一样，把这块矩阵分成了很多块，就像一维树状数组分成很多段一样，切记此处的c[x][y][z]，不是（1，1）到（x，y）中有多少个z，而是这个结点的叶子节点之和（往一维那里想）。

     举个例子：

x=y=7     那么单考虑一个一维的树状数组，【1，7】被分为【1，4】【5，6】【7，7】三个区间。

接下来我们考虑二维：

x方向分为【1，4】【5，6】【7，7】y方向同样，所以整个矩阵被分为九块，然后建出了一颗二维的树，我也不会画，因为我只是个小萌新

#include<iostream>
#include<stdio.h>
#include<string.h>
#define lowbit(x) x&(-x)
using namespace std;
int n,m;
int c[305][305][105];
int a[305][305];
int ask(int x,int y,int z){
    int ans=0;
    for(;x;x-=lowbit(x)){
        for(int j=y;j;j-=lowbit(j)){
            ans+=c[x][j][z];
        }
    }
    return ans;
}
void add(int x,int y,int z,int d){
    for(x;x<=n;x+=lowbit(x)){
        for(int j=y;j<=m;j+=lowbit(j)){
            c[x][j][z]+=d;
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
                add(i,j,a[i][j],1);
            }
        }
        int sb,k;scanf("%d",&k);
        while(k--){
            scanf("%d",&sb);
            if(sb==1){
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                add(x,y,a[x][y],-1);
                add(x,y,z,1);
                a[x][y]=z;
            }
            else{
                int x1,x2,y1,y2,z;
                scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&z);
                int ans=ask(x2,y2,z)-ask(x1-1,y2,z)-ask(x2,y1-1,z)+ask(x1-1,y1-1,z);
                printf("%d\n",ans);
            }
        }
    }

}