计数问题(二维数状数组)

题目描述
一个n*m的方格，初始时每个格子有一个整数权值。接下来每次有2种操作：
改变一个格子的权值；
求一个子矩阵中某种特定权值出现的个数。
输入
第一行有两个数n,m。
接下来n行，每行m个数，第i+1行第j个数表示格子(i,j)的初始权值。
接下来输入一个整数q。
接下来q行，每行描述一个操作。
操作1：“1 x y c”(不含双引号)。表示将格子(x,y)的权值改成c（1<=x<=n,1<=y<=m,1<=c<=100)。
操作2：“2 x1 x2 y1 y2 c”(不含双引号，x1<=x2,y1<=y2)。表示询问所有满足格子权值为c，且x1<=x<=x2,y1<=y<=y2的格子(x,y)的个数。
输出
对于每个操作2，按照在输入中出现的顺序，依次输出一行一个整数表示所求得的个数。
样例输入
3 3
1 2 3
3 2 1
2 1 3
3
2 1 2 1 2 1
1 2 3 2
2 2 3 2 3 2
样例输出
1
2
提示
对于30%的数据n,m<=30，q<=10000
对于100%的数据 n,m<=300，q<=100000，1<=c<=100

对于这种二维的区间查询单点修改题目，想到的只能是线段树啊树状数组什么的，其实有一瞬间想到是不是莫队，但其实就是一个二维树状数模板题，因此就学了学二维树状数组的操作。其实基本和一维树状数组操作差不多，对于求区间信息的操作，使用了容斥原理，也就是说求x1,y1到x2,y2这个区间矩形内的信息时，先求和得到1 ，1至x2,y2这个面积内的前缀和，然后减去1，1到x1-1,y2和x2,y-1这两个不需要的面积，然后因为1,1至x1,y2这块面积被重复减去了一次，再加回来，最终前缀和即所求面积的前缀和。

关于二维树状数组，更新时同样是从x到n和从y到n的lowbit(x)递增更新，求和时仍是从x到1和从y到1的求和，只不过这个过程用两层for循环依次对二维平面上每个坐标的节点进行更新和求和

此题中树状数组的二维平面作为坐标的标记，第三维是每个数的序号标记，最终存储的是每个坐标上num数字的出现次数前缀和，将其根据需要的区间进行求和和容斥即可。当然对于被修改的数字，也要根据情况对树状数组上的前缀和进行相应删改。

代码如下：

#include
#include
#include
#include
using namespace std;
int n,m,t;
int tri[305][305][102];
int a[305][305];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int y,int num)
{
    for(int i=x; i<=n; i+=lowbit(i))
        for(int j=y; j<=m; j+=lowbit(j))
            tri[i][j][num]++;
}
void del(int x,int y,int num)
{
    for(int i=x; i<=n; i+=lowbit(i))
        for(int j=y; j<=m; j+=lowbit(j))
            tri[i][j][num]--;
}
int sum(int x,int y,int z)
{
    int sum=0;
    for(int i=x; i>0; i-=lowbit(i))
        for(int j=y; j>0; j-=lowbit(j))
            sum+=tri[i][j][z];
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(tri,0,sizeof(tri));
    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]);
        }
    scanf("%d",&t);
    while(t--)
    {
//        printf("=====%d\n",t);
        int flag;
        scanf("%d",&flag);
        if(flag==1)
        {
            int x,y,tmp;
            scanf("%d%d%d",&x,&y,&tmp);
            del(x,y,a[x][y]);
            a[x][y]=tmp;
            update(x,y,tmp);
        }
        else
        {
            int x1,x2,y1,y2,tmp,ans=0;
            scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&tmp);
            ans=sum(x2,y2,tmp)-sum(x1-1,y2,tmp)-sum(x2,y1-1,tmp)+sum(x1-1,y1-1,tmp);
            printf("%d\n",ans);
        }
    }
}