BZOJ-1452: [JSOI2009]Count

[文章目录]

Description

给你一个n*m的矩阵,每个格子有自己所属的种类。给出q次询问,每次询问一个子矩阵中种类为c的格子的个数。并且带有单点修改。n<=300,m<=300,c<=100,q<=200000

看到就知道是建c个二维树状数组。然后就忘了二维树状数组是怎么写的了。233,滑稽。

就是把一群一维的树状数组挪到一起,然后将相同位置上的再形成一个树状数组,所以查询的时候复杂度就变成了logn^2。相当于一维树状数组中的前缀和又在二维上构造了个前缀和。那么,一个节点在修改的时候,在横向和纵向两个方向有关的点都需要累加。

直白点:前缀和的前缀和。 代码如下。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,q,map[310][310],f[110][330][330];
void fix(int w,int x,int y,int v)
{
	for(int i=x;i<=n;i+=-i&i)
		for(int j=y;j<=m;j+=-j&j)
			f[w][i][j]+=v;
}
int query(int w,int x,int y)
{
	int re=0;
	for(int i=x;i>0;i-=-i&i)
		for(int j=y;j>0;j-=-j&j)
			re+=f[w][i][j];
	return re;
}
void output(int x)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",f[x][i][j]);
		puts("");
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&map[i][j]);
			fix(map[i][j],i,j,1);
		}
	scanf("%d",&q);
	int c,x1,x2,y1,y2,x,y,sw;
	while(q--)
	{
		scanf("%d",&sw);
		if(sw==1)
		{
			scanf("%d%d%d",&x,&y,&c);
			fix(map[x][y],x,y,-1);
			fix(c,x,y,1); map[x][y]=c;
		}
		else
		{
			scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);x1--,y1--;
			printf("%d\n",query(c,x2,y2)-query(c,x2,y1)-query(c,x1,y2)+query(c,x1,y1));
		}
	}
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注