P4054 [JSOI2009] 计数问题

传送门

二维树状数组板子题（大概？）只要再多开一维 \(c\) 来存储该点的权值就可以了。这里的树状数组 \(a[i][j][c]\) 表示以第 \(i\) 行，第 \(j\) 列为右下角，权值为 \(c\) 的点出现的个数。那么每次更改权值时，先将原有的权值加上\(-1\) ，再将更新后的权值加上\(1\)。最后在更新一下权值就好了。

#include <bits/stdc++.h>
#define R register
using namespace std;
int n,m,q,a[305][305][105],mark[305][305];

inline int lowbit(int x){return x&~(x-1);}
inline void add(int x,int y,int c,int k){
	for(R int i=x;i<=n;i+=lowbit(i))
		for(R int j=y;j<=m;j+=lowbit(j))a[i][j][c]+=k;
}
inline int get_sum(int x,int y,int c){
	R int sum=0;
	for(R int i=x;i;i-=lowbit(i))
		for(R int j=y;j;j-=lowbit(j))sum+=a[i][j][c];
	return sum;
}

int main(){
	scanf("%d%d",&n,&m);
	for(R int i=1;i<=n;i++)
		for(R int j=1;j<=m;j++)scanf("%d",&mark[i][j]),add(i,j,mark[i][j],1);
	scanf("%d",&q);
	int k;
	for(R int i=1;i<=q;i++){
		scanf("%d",&k);
		if(k==1){
			R int x,y,c;
			scanf("%d%d%d",&x,&y,&c);
			add(x,y,mark[x][y],-1);
			add(x,y,c,1);
			mark[x][y]=c;
		}
		else{
			R int x1,y1,x2,y2,c;
			scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
			printf("%d\n",get_sum(x2,y2,c)-get_sum(x1-1,y2,c)-get_sum(x2,y1-1,c)+get_sum(x1-1,y1-1,c));
		}
	}
	return 0;
}