首页 > 代码库 > HDU 4819 Mosaic 二维线段树
HDU 4819 Mosaic 二维线段树
连接:http://acm.hdu.edu.cn/showproblem.php?pid=4819
题意:给出一个800×800以下的矩阵,每次更新一个点的值为以这个点为中心的长度为Li的矩阵内的最大值和最小值的平均值,并且输出这个值。
思路:线段树模板题,二维线段树就是一个树套树的情况。
题的意义就在于给我带了一个二维线段树的模板,跑了2359ms,结构体的线段树不会被卡。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <cstdlib> #include <queue> #include <stack> #include <vector> #include <ctype.h> #include <algorithm> #include <string> #include <set> #define PI acos(-1.0) #define maxn 1000 #define INF 0x7fffffff #define eps 1e-16 #define MOD 1000000009 typedef long long LL; typedef unsigned long long ULL; using namespace std; int x_pos[maxn],y_pos[maxn]; int n;//y最大范围 struct y_line { int left,right; int Max,Min; //int sum; int mid(){return (left+right)>>1;} }; struct x_line { int left,right; y_line yy[maxn*4]; int mid(){return (left+right)>>1;} void build_ytree(int i,int l,int r) { yy[i].Max=-INF; yy[i].Min=INF; yy[i].left=l; yy[i].right=r; if(l==r) { y_pos[l]=i; return ; } build_ytree(i<<1,l,yy[i].mid()); build_ytree(i<<1|1,yy[i].mid()+1,r); } int query_Min(int i,int y1,int y2) { if(yy[i].left==y1&&yy[i].right==y2) return yy[i].Min; if(yy[i].mid()>=y2) return query_Min(i<<1,y1,y2); if(yy[i].mid()<y1) return query_Min(i<<1|1,y1,y2); return min(query_Min(i<<1,y1,yy[i].mid()),query_Min(i<<1|1,yy[i].mid()+1,y2)); } int query_Max(int i,int y1,int y2) { if(yy[i].left==y1&&yy[i].right==y2) return yy[i].Max; if(yy[i].mid()>=y2) return query_Max(i<<1,y1,y2); if(yy[i].mid()<y1) return query_Max(i<<1|1,y1,y2); return max(query_Max(i<<1,y1,yy[i].mid()),query_Max(i<<1|1,yy[i].mid()+1,y2)); } }xx[maxn*4]; void build_xtree(int i,int l,int r) { xx[i].left=l; xx[i].right=r; xx[i].build_ytree(1,1,n); if(l==r) { x_pos[l]=i; return ; } build_xtree(i<<1,l,xx[i].mid()); build_xtree(i<<1|1,xx[i].mid()+1,r); } void change(int x,int y,int num) { int x_p=x_pos[x],y_p=y_pos[y]; for(int i=x_p;i>0;i>>=1) for(int j=y_p;j>0;j>>=1) if(j==y_p&&i==x_p) { xx[i].yy[j].Max=xx[i].yy[j].Min=num; } else if(j==y_p) { xx[i].yy[j].Max=max(xx[i<<1].yy[j].Max,xx[i<<1|1].yy[j].Max); xx[i].yy[j].Min=min(xx[i<<1].yy[j].Min,xx[i<<1|1].yy[j].Min); } else { xx[i].yy[j].Max=max(xx[i].yy[j<<1].Max,xx[i].yy[j<<1|1].Max); xx[i].yy[j].Min=min(xx[i].yy[j<<1].Min,xx[i].yy[j<<1|1].Min); } } int query_Min(int i,int x1,int y1,int x2,int y2) { if(xx[i].left==x1&&xx[i].right==x2) return xx[i].query_Min(1,y1,y2); if(xx[i].mid()>=x2) return query_Min(i<<1,x1,y1,x2,y2); if(xx[i].mid()<x1) return query_Min(i<<1|1,x1,y1,x2,y2); return min(query_Min(i<<1,x1,y1,xx[i].mid(),y2),query_Min(i<<1|1,xx[i].mid()+1,y1,x2,y2)); } int query_Max(int i,int x1,int y1,int x2,int y2) { if(xx[i].left==x1&&xx[i].right==x2) return xx[i].query_Max(1,y1,y2); if(xx[i].mid()>=x2) return query_Max(i<<1,x1,y1,x2,y2); if(xx[i].mid()<x1) return query_Max(i<<1|1,x1,y1,x2,y2); return max(query_Max(i<<1,x1,y1,xx[i].mid(),y2),query_Max(i<<1|1,xx[i].mid()+1,y1,x2,y2)); } int main() { int T,tot,c_x,c_y,r; scanf("%d",&T); for(int ii=1;ii<=T;ii++) { scanf("%d",&n); build_xtree(1,1,n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { int x; scanf("%d",&x); change(i,j,x); } scanf("%d",&tot); printf("Case #%d:\n",ii); for(int i=0;i<tot;i++) { scanf("%d%d%d",&c_x,&c_y,&r); int a,b,c,d; a=max(1,c_x-r/2); b=max(1,c_y-r/2); c=min(n,c_x+r/2); d=min(n,c_y+r/2); int t_min=query_Min(1,a,b,c,d); int t_max=query_Max(1,a,b,c,d); int t_need=(t_min+t_max)>>1; change(c_x,c_y,t_need); printf("%d\n",t_need); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。