设为首页 加入收藏

TOP

HDU 4819 Mosaic 二维线段树
2015-07-20 18:03:16 来源: 作者: 【大 中 小】 浏览:2次
Tags：HDU 4819 Mosaic 二维 线段

连接：http://acm.hdu.edu.cn/showproblem.php?pid=4819

题意：给出一个800×800以下的矩阵，每次更新一个点的值为以这个点为中心的长度为Li的矩阵内的最大值和最小值的平均值，并且输出这个值。

思路：线段树模板题，二维线段树就是一个树套树的情况。

\


题的意义就在于给我带了一个二维线段树的模板，跑了2359ms，结构体的线段树不会被卡。<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPrT6wuujujwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include #include #include #include #include #include #include #include #include #include #include #include #include #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() =y2) return query_Max(i<<1,y1,y2); if(yy[i].mid() 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() =x2) return query_Max(i<<1,x1,y1,x2,y2); if(xx[i].mid() >1; change(c_x,c_y,t_need); printf("%d\n",t_need); } } return 0; }



【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：140725暑期培训.txt 下一篇：HDU 2669 Romantic 扩展欧几里得

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: