短小二维树状数组模板WA
查看原帖
短小二维树状数组模板WA
547725
Zilljy258楼主2025/1/24 11:06

讨论区的 hack 全部可以通过,然而提交只能通过 Subtask #1。

代码简单短小的模板题,希望大佬抽空帮忙看一下,谢谢了。


#define lowbit(i) (i&(-i)) 

int n,m,q;
int a[301][301];
int t[101][301][301];

void add(int c,int x,int y,int z){
	for(int i=x;i<=n;i+=lowbit(i)){
		for(int j=y;j<=m;j+=lowbit(j)){
			t[c][i][j]+=z;
		}
	}
	return ;
}

int qry(int c,int x,int y){
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i)){
		for(int j=y;j>0;j-=lowbit(j)){
			ans+=t[c][i][j];
		}
	}
	return ans;
}

int main(){ 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
			add(a[i][j],i,j,1);
		}
	}
	int op,x1,y1,x2,y2,c;
	scanf("%d",&q);
	while(q--) {
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&x1,&y1,&c);
			add(a[x1][y1],x1,y1,-1);
			a[x1][y1]=c;
			add(a[x1][y1],x1,y1,1);
			
		}
		else{
			scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
			printf("%d\n",qry(c,x2,y2)-qry(c,x1-1,y1)-qry(c,x2,y1-1)+qry(c,x1-1,y1-1));
		}
	}
	return 0;
}

/*
(x-i+1)*(y-j+1)=(x+1)*(y+1)-i*(y+1)-j*(x+1)+i*j
*/
2025/1/24 11:06
加载中...