题目链接：

第一道二维线段树， 感觉和一维的基本上一样，只不过多了一个子函数！

以身高建立主函数，活泼度为子函数。

身高可以转化为0-100， 因为活泼度只有一位小数，可以乘以10转化为整数！

code：

1 # include
      
          2 # include
       
           3 # define HMax 405   4 # define AMax 4005   5 struct sub_tree{
      6     int la,ra,Max;   7 };   8 struct main_tree{
      9     sub_tree A[AMax];  10     int l,r;  11 }H[HMax];  12 int num;  13 int max(int a,int b)  14 {
     15     return a>b?a:b;  16 }  17 void sub_bulid(int la,int ra,int t1,int t)  18 {
     19     H[t].A[t1].la=la;  20     H[t].A[t1].ra=ra;  21     H[t].A[t1].Max=-1;  22     if(la==ra) return;  23     int mid=(la+ra)/2;  24     sub_bulid(la,mid,2*t1,t);  25     sub_bulid(mid+1,ra,2*t1+1,t);  26 }  27 void bulid(int l,int r,int la,int ra,int t)  28 {
     29     H[t].l=l;  30     H[t].r=r;  31     sub_bulid(la,ra,1,t);  32     if(l==r) return;  33     int mid=(l+r)/2;  34     bulid(l,mid,la,ra,2*t);  35     bulid(mid+1,r,la,ra,2*t+1);  36 }  37 void sub_insert(int a,int L,int t1,int t)  38 {
     39     if(H[t].A[t1].Max
        
         =H[t].A[2*t1+1].la) return sub_query(A1,A2,2*t1+1,t);  56     else  57     {
     58         return max(sub_query(A1,H[t].A[2*t1].ra,2*t1,t),sub_query(H[t].A[2*t1+1].la,A2,2*t1+1,t));  59     }  60 }  61 void query(int h1,int h2,int A1,int A2,int t)  62 {
     63     if(H[t].l==h1 && H[t].r==h2)  64     {
     65         num=max(num,sub_query(A1,A2,1,t));  66         return;  67     }  68     if(h2<=H[2*t].r) query(h1,h2,A1,A2,2*t);  69     else if(h1>=H[2*t+1].l) query(h1,h2,A1,A2,2*t+1);  70     else  71     {
     72         query(h1,H[2*t].r,A1,A2,2*t);  73         query(H[2*t+1].l,h2,A1,A2,2*t+1);  74     }  75 }  76 int main()  77 {
     78     int m,hh,a,L,A1,A2,h1,h2,tmp;  79     double a1,L1,a2;  80     char ch[5];  81     while(scanf("%d",&m)!=EOF && m)  82     {
     83         bulid(0,100,0,1000,1);  84         while(m--)  85         {
     86             scanf("%s",ch);  87             if(ch[0]=='I')  88             {
     89                 scanf("%d%lf%lf",&hh,&a1,&L1);  90             hh-=100;  91             a=(int)(a1*10);  92             L=(int)(L1*10);  93                 insert(hh,a,L,1);  94             }  95             else  96             {
     97                 scanf("%d%d%lf%lf",&h1,&h2,&a1,&a2);  98                 h1-=100;  99                 h2-=100; 100                 A1=(int)(a1*10); 101                 A2=(int)(a2*10); 102                 if(h1>h2) 103                 {
    104                     tmp=h1; 105                     h1=h2; 106                     h2=tmp; 107                 } 108                 if(A1>A2) 109                 {
    110                     tmp=A1; 111                     A1=A2; 112                     A2=tmp; 113                 } 114                 num=-1; 115                 query(h1,h2,A1,A2,1); 116 if(num==-1) {printf("-1\n");continue;} 117                 L1=1.0*num/10; 118                 printf("%.1lf\n",L1); 119             } 120         } 121     } 122     return 0; 123 }