程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4819 Mosaic 二維線段樹

HDU 4819 Mosaic 二維線段樹

編輯：C++入門知識

HDU 4819 Mosaic 二維線段樹

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

題意：給出一個800×800以下的矩陣，每次更新一個點的值為以這個點為中心的長度為Li的矩陣內的最大值和最小值的平均值，並且輸出這個值。

思路：線段樹模板題，二維線段樹就是一個樹套樹的情況。

題的意義就在於給我帶了一個二維線段樹的模板，跑了2359ms，結構體的線段樹不會被卡。<喎?http://www.Bkjia.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; }