HDU 4819 Mosaic D区段树-白红宇

连接：

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

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

题的意义就在于给我带了一个二维线段树的模板，跑了2359ms。结构体的线段树不会被卡。

代码：

#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 1000000009typedef 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;}

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4720699.html，如需转载请自行联系原作者