【线段树套线段树】HDU4819[Mosaic]题解
发布时间
阅读量：
阅读量
题目概述
给定一个n×n阶的矩阵A以及m个待处理的查询请求Q1,Q2,...,Qm。对于每一个查询请求(Qi=(xi,yi,zi))而言，请您计算该查询涉及以坐标(xi,yi)为中心点的一个zi×zi子矩阵，并计算其中的最大值MAX以及最小值MIN。随后将中心坐标(xi,yi)更新为计算得到的结果floor((MIN + MAX)/2)，其中floor函数用于向下取整。
解题报告
这属于经典的区域查询问题中的一种常见操作方式。具体而言，在这种场景下最基础的操作是单点修改操作。为了实现这一功能可以选择嵌套多层线段树结构来完成操作。需要注意的是，在空间资源较为紧张的情况下我们通常不会直接存储每个节点的所有子节点信息而是在必要时动态生成这些子节点的信息以节省内存空间。这样一来不仅能够显著降低内存占用率还能提高算法的运行效率
示例程序
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=800,maxt=4*maxn,MAXINT=((1<<30)-1)*2+1;
int te,n,m,pic[maxn+5][maxn+5];
//===========================================================
struct SegmentTreexy //线段树套线段树
{
int MIN[maxt+5][maxt+5],MAX[maxt+5][maxt+5];
int posx,posy,Lx,Rx,Ly,Ry,fa,k;bool is_leaf; //fa是当前x树，is_leaf表示fa是否是叶节点
void Pushupy(int fa,int p) //更新列
{
MIN[fa][p]=min(MIN[fa][p<<1],MIN[fa][p<<1|1]);
MAX[fa][p]=max(MAX[fa][p<<1],MAX[fa][p<<1|1]);
}
void Pushupx(int fa,int p) //更新行
{
MIN[fa][p]=min(MIN[fa<<1][p],MIN[fa<<1|1][p]);
MAX[fa][p]=max(MAX[fa<<1][p],MAX[fa<<1|1][p]);
}
void Buildy(int p,int L,int R,int *a) //构造列
{
if (L==R) {if (is_leaf) MIN[fa][p]=MAX[fa][p]=a[L]; else Pushupx(fa,p);return;}
//如果是fa叶节点就直接构造，否则更新
int mid=L+(R-L>>1);
Buildy(p<<1,L,mid,a);Buildy(p<<1|1,mid+1,R,a);
Pushupy(fa,p);
}
void Buildx(int p,int L,int R) //构造行
{
if (L==R) fa=p,is_leaf=true,Buildy(1,Ly,Ry,pic[L]); else
{
int mid=L+(R-L>>1);
Buildx(p<<1,L,mid);Buildx(p<<1|1,mid+1,R);
fa=p;is_leaf=false;Buildy(1,Ly,Ry,pic[L]);
}
}
void Inserty(int p,int L,int R) //更新列
{
if (posy<L||R<posy) return;
if (L==R) {if (is_leaf) MIN[fa][p]=MAX[fa][p]=k; else Pushupx(fa,p);return;}
//如果是fa叶节点就直接修改，否则更新
int mid=L+(R-L>>1);
Inserty(p<<1,L,mid);Inserty(p<<1|1,mid+1,R);
Pushupy(fa,p);
}
void Insertx(int p,int L,int R) //更新行
{
if (posx<L||R<posx) return;
if (L==R) fa=p,is_leaf=true,Inserty(1,1,n); else
{
int mid=L+(R-L>>1);
Insertx(p<<1,L,mid);Insertx(p<<1|1,mid+1,R);
fa=p;is_leaf=false;Inserty(1,1,n);
}
}
int Askminy(int p,int L,int R) //在列中求MIN
{
if (Ry<L||R<Ly) return MAXINT;
if (Ly<=L&&R<=Ry) return MIN[fa][p];
int mid=L+(R-L>>1);
return min(Askminy(p<<1,L,mid),Askminy(p<<1|1,mid+1,R));
}
int Askminx(int p,int L,int R) //在行中求MIN
{
if (Rx<L||R<Lx) return MAXINT;
if (Lx<=L&&R<=Rx) {fa=p;return Askminy(1,1,n);}
int mid=L+(R-L>>1);
return min(Askminx(p<<1,L,mid),Askminx(p<<1|1,mid+1,R));
}
int Askmaxy(int p,int L,int R) //在列中求MAX
{
if (Ry<L||R<Ly) return -MAXINT;
if (Ly<=L&&R<=Ry) return MAX[fa][p];
int mid=L+(R-L>>1);
return max(Askmaxy(p<<1,L,mid),Askmaxy(p<<1|1,mid+1,R));
}
int Askmaxx(int p,int L,int R) //在行中求MAX
{
if (Rx<L||R<Lx) return -MAXINT;
if (Lx<=L&&R<=Rx) {fa=p;return Askmaxy(1,1,n);}
int mid=L+(R-L>>1);
return max(Askmaxx(p<<1,L,mid),Askmaxx(p<<1|1,mid+1,R));
}
void Build(int x_s,int y_s,int x_t,int y_t) {Lx=x_s;Rx=x_t;Ly=y_s;Ry=y_t;Buildx(1,Lx,Rx);}
void Insert(int x,int y,int z) {posx=x;posy=y;k=z;Insertx(1,1,n);}
int Ask(int x_s,int y_s,int x_t,int y_t)
{
Lx=x_s;Rx=x_t;Ly=y_s;Ry=y_t;
return (Askminx(1,1,n)+Askmaxx(1,1,n))/2;
}
};
SegmentTreexy tr;
//===========================================================
bool Eoln(char ch) {return ch==10||ch==13||ch==EOF;}
int readi(int &x)
{
int tot=0,f=1;char ch=getchar(),lst=ch;
while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=getchar();}
if (lst=='-') f=-f;
while ('0'<=ch&&ch<='9') tot=tot*10+ch-48,ch=getchar();
x=tot*f;
return Eoln(ch);
}
int main()
{
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
readi(te);
for (int t=1;t<=te;t++)
{
printf("Case #%d:\n",t);
readi(n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
readi(pic[i][j]);
tr.Build(1,1,n,n);
readi(m);
while (m--)
{
int x,y,z;readi(x);readi(y);readi(z);z/=2;
int Lx=x-z,Rx=x+z,Ly=y-z,Ry=y+z,now=tr.Ask(Lx,Ly,Rx,Ry);
printf("%d\n",now);
tr.Insert(x,y,now);
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~