[luogu]P4054 [JSOI2009]计数问题 树状数组解决二维前缀和

前言

传送门 :

思路

题目要求,单点修改,并且区间求和,显然我们可以联想到树状数组

因此我们可以使用 t r [ i ] [ j ] [ k ] tr[i][j][k] tr[i][j][k]来记录,一个坐标上的状态

剩下的就和一维树状数组差不多了,不多做解释

Mycode

const int N  = 310;
int tr[N][N][110];
int a[N][N];

int n,m;

int lowbit(int x){
	return x & -x;
}

void add(int x,int y,int color,int k){
	for(int i = x; in>>m;
	for(int i=1;ia[i][j];
			add(i,j,a[i][j],1);
		}
		
	int q;cin>>q;
	for(int i=1;i>op;
		
		if(*op == '2'){
			int x1,y1,x2,y2,c;cin>>x1>>x2>>y1>>y2>>c;
			couty>>k;
			add(x,y,a[x][y],-1);
			a[x][y] = k;
			add(x,y,a[x][y],1);
		}
	}
}