HDU4819 Mosaic

题目大意

给出一个n*n的矩阵,给出m个询问,每个询问形如x,y,z,表示询问以x,y为中心点的z*z子矩阵的最大值MAX和最小值MIN,输出(MIN+MAX)/2。并将x,y修改为(MIN+MAX)/2(向下取整)。

Solution

支持修改一个数,并询问一个区间中的最大、最小值,可以想到用线段树维护。以前写过把一个二维矩阵分成四块的二维线段树,因为各种原因,它的复杂度很大。所以只能用树套树维护。外层的线段树中,每个节点都维护一棵内层的线段树,就可以做到询问区间。但在外层的线段树上似乎只能单点修改。

代码 
//要注意细节,由于各种细节原因,写挂了很多次。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int Min[3210][3210],Max[3210][3210];
int a[1010][1010],y,n,m,ly,ry,T,L,R,ansmin,ansmax;
void buildy(int l,int r,int t)
{
	if (l==r)
	{
		if (L==R) Min[T][t]=Max[T][t]=a[L][l];
		else Min[T][t]=min(Min[T<<1][t],Min[T<<1|1][t]),Max[T][t]=max(Max[T<<1][t],Max[T<<1|1][t]);
		return;
	}
	int mid=(l+r)>>1;
	buildy(l,mid,t<<1);
	buildy(mid+1,r,t<<1|1);
	Min[T][t]=min(Min[T][t<<1],Min[T][t<<1|1]);
	Max[T][t]=max(Max[T][t<<1],Max[T][t<<1|1]);
}
void buildx(int l,int r,int t)
{ 
	if (l==r)
	{
		L=l,R=r,T=t;
		buildy(1,n,1);
		return;
	}
	int mid=(l+r)>>1;
	buildx(l,mid,t<<1);
	buildx(mid+1,r,t<<1|1);
	L=l,R=r,T=t;
	buildy(1,n,1);
}
void queryy(int l,int r,int x,int y,int t,int T)
{
	if (l==x&&y==r)
	{
		ansmax=max(ansmax,Max[T][t]),ansmin=min(Min[T][t],ansmin);
		return;
	}
	int mid=(l+r)>>1;
	if (y<=mid) queryy(l,mid,x,y,t<<1,T);
	else if (x>mid) queryy(mid+1,r,x,y,t<<1|1,T);
	else
	{
		queryy(l,mid,x,mid,t<<1,T);
		queryy(mid+1,r,mid+1,y,t<<1|1,T);
	}
}
void queryx(int l,int r,int x,int y,int t)
{
	if (l==x&&y==r)
	{
		queryy(1,n,ly,ry,1,t);
		return;
	}
	int mid=(l+r)>>1;
	if (y<=mid) queryx(l,mid,x,y,t<<1);
	else if (x>mid) queryx(mid+1,r,x,y,t<<1|1);
	else
	{
		queryx(l,mid,x,mid,t<<1);
		queryx(mid+1,r,mid+1,y,t<<1|1);
	}
}
void modifyy(int l,int r,int t,int x,int key)
{
	if (l==r)
	{
		if (L==R)
			Min[T][t]=Max[T][t]=key;
		else Min[T][t]=min(Min[T<<1][t],Min[T<<1|1][t]),Max[T][t]=max(Max[T<<1][t],Max[T<<1|1][t]);
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) modifyy(l,mid,t<<1,y,key);
	else modifyy(mid+1,r,t<<1|1,x,key);
	Min[T][t]=min(Min[T][t<<1],Min[T][t<<1|1]);
	Max[T][t]=max(Max[T][t<<1],Max[T][t<<1|1]);
}
void modifyx(int l,int r,int x,int t,int key)
{
	if (l==r)
	{
		T=t;
		L=l,R=r;
		modifyy(1,n,1,y,key);
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) modifyx(l,mid,x,t<<1,key);
	else modifyx(mid+1,r,x,t<<1|1,key);
	T=t;
	L=l,R=r;
	modifyy(1,n,1,y,key);
}
int main()
{
	int cas,Cas=0;
	scanf("%d",&cas);
	while (cas--)
	{
		scanf("%d",&n);
		memset(Max,0,sizeof(Max));
		memset(Min,0,sizeof(Min)); 
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				scanf("%d",&a[i][j]);
		buildx(1,n,1);
		scanf("%d",&m);
		printf("Case #%d:\n",++Cas);
		while (m--)
		{
			int x,z;
			scanf("%d%d%d",&x,&y,&z);
			if (x>n||y>n) continue;
			if (x<1||y<1) continue;
			z=(z+1)>>1;
			int lx=x-z+1,rx=x+z-1;
			ly=y-z+1,ry=y+z-1;
			lx=max(lx,1),rx=min(rx,n);
			ly=max(ly,1),ry=min(ry,n);
			ansmin=1000000007;
			ansmax=-1000000007;
			queryx(1,n,lx,rx,1);
			printf("%d\n",(ansmax+ansmin)>>1);
			modifyx(1,n,x,1,(ansmax+ansmin)>>1);
		}
	}
	return 0;
}

 

Leave a Comment

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