ZOJ 2859 二维线段树

思路:自己写的第二发二维线段树1A。哈哈,看来对二维的push操作比較了解了;可是还没遇到在两个线段树中同一时候进行push操作的,事实上这题我是想在x维和y维同一时候进行push操作的。可是想了好久不会。然后看到这题又给出10秒,然后想想在x维线段直接单点查询肯定也过了,然后在第二维就仅仅有pushup操作。在第一维线段树没有pushup操作。要是在第一维也有pushup操作的话。那就不用单点查询那么慢了。

只是也A了,想找题即在二维同一时候进行pushup和pushdown操作的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 1010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int Map[maxn][maxn],Min[maxn][maxn];
int n,q,t,ans;
void pushup(int i,int j)
{
Min[i][j]=min(Min[i][j<<1],Min[i][j<<1|1]);
}
void build_y(int i,int u,int j,int l,int r)
{
if(l==r)
{
Min[i][j]=Map[u][l];
return ;
}
int mid=(l+r)>>1;
build_y(i,u,llson);build_y(i,u,rrson);
pushup(i,j);
}
void build_x(int i,int l,int r)
{
if(l==r)
{
build_y(i,l,1,1,n);
return ;
}
int mid=(l+r)>>1;
build_x(lson);build_x(rson);
}
int query_y(int i,int j,int l,int r,int y1,int y2)
{
if(l==y1&&y2==r) return Min[i][j];
int mid=(l+r)>>1;
if(y2<=mid) return query_y(i,llson,y1,y2);
else if(y1>mid) return query_y(i,rrson,y1,y2);
else return min(query_y(i,llson,y1,mid),query_y(i,rrson,mid+1,y2));
}
void query_x(int i,int l,int r,int x1,int x2,int y1,int y2)
{
if(l==r)
{
ans=min(ans,query_y(i,1,1,n,y1,y2));
return ;
}
int mid=(l+r)>>1;
if(x1<=mid) query_x(lson,x1,x2,y1,y2);
if(x2>mid) query_x(rson,x1,x2,y1,y2);
}
int main()
{
freopen("test.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&Map[i][j]);
build_x(1,1,n);
scanf("%d",&q);
while(q--)
{
int x1,y1,x2,y2;
ans=INF;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
query_x(1,1,n,x1,x2,y1,y2);
printf("%d\n",ans);
}
}
return 0;
}
上一篇:201621123014《Java程序设计》第十三周学习总结


下一篇:poj2019 二维RMQ模板题