Luck and Love

 

世界上上最远的距离不是相隔天涯海角 

而是我在你面前 

可你却不知道我爱你 

                ―― 张小娴 

前段日子，枫冰叶子给Wiskey做了个征婚启事，聘礼达到500万哦，天哪，可是天文数字了啊，不知多少MM蜂拥而至，顿时万人空巷，连扫地的大妈都来凑热闹来了。―_―||| 

由于人数太多，Wiskey实在忙不过来，就把统计的事情全交给了枫冰叶子，自己跑回家休息去了。这可够枫冰叶子忙的了，他要处理的有两类事情，一是得接受MM的报名，二是要帮Wiskey查找符合要求的MM中缘分最高值。 

Input本题有多个测试数据，第一个数字M，表示接下来有连续的M个操作，当M＝0时处理中止。 

接下来是一个操作符C。 

当操作符为‘I’时，表示有一个MM报名，后面接着一个整数，H表示身高，两个浮点数，A表示活泼度，L表示缘分值。 （100<=H<=200， 0.0<=A，L<=100.0） 

当操作符为‘Q’时，后面接着四个浮点数，H1，H2表示身高区间，A1，A2表示活泼度区间，输出符合身高和活泼度要求的MM中的缘分最高值。 （100<=H1，H2<=200， 0.0<=A1，A2<=100.0）

所有输入的浮点数，均只有一位小数。 

Output对于每一次询问操作，在一行里面输出缘分最高值，保留一位小数。 

对查找不到的询问，输出-1。 

Sample Input

8I 160 50.5 60.0I 165 30.0 80.5I 166 10.0 50.0I 170 80.5 77.5Q 150 166 10.0 60.0Q 166 177 10.0 50.0I 166 40.0 99.9Q 166 177 10.0 50.00

Sample Output

80.550.099.9

——————————————————————————————————————————————————————————————————————————

处理二维表格中的数据修改和查询操作，用传说中的二维线段树。

首先第一维为行，把行建立线段树，线段树的节点代表1个到多个行。

然后把行线段树的每个节点对应的列建立线段树，每个节点代表在行节点控制范围内的1个到多个列。

时间负责度为log(m)*log(n)，其中m和n代表行数和列数。

 

另外，还有一种写法，就是建立四叉线段树。也可以称为“矩形树”。实际上就是把矩形按照行和列的二分，分为4块区域。应该更好理解且更好写。只是据说这种写法复杂度有可能退化。

——————————————————————————————————————————————————————————————————————————

1 #include
      
         2 using namespace std;  3 const int maxn=105;  4 const int maxm=1005;  5 struct Lie  6 {  7     int ll,lr;  8     int max;  9 }; 10 struct Hang 11 { 12     int l,r; 13     Lie lie[maxm<<2];  14 }hang[maxn<<2]; 15 int m,active,love,hight; 16 char s[2]; 17 void buil(int hh,int cur,int l,int r) 18 { 19     hang[hh].lie[cur].ll=l; 20     hang[hh].lie[cur].lr=r; 21     hang[hh].lie[cur].max=-1; 22     if(l==r)return ; 23     int mid=(l+r)>>1; 24     buil(hh,cur<<1,l,mid); 25     buil(hh,cur<<1 | 1,mid+1,r); 26 } 27 void build(int cur,int l,int r,int ll,int lr) 28 { 29     hang[cur].l=l;hang[cur].r=r; 30     buil(cur,1,ll,lr);  31     if(l==r)return ; 32     int mid=(l+r)>>1; 33     build(cur<<1,l,mid,ll,lr); 34     build(cur<<1 | 1,mid+1,r,ll,lr); 35 } 36 void upda(int pre,int cur,int hh,int lh,int dat) 37 { 38     if(hang[pre].lie[cur].ll==hang[pre].lie[cur].lr) 39     { 40         hang[pre].lie[cur].max=max(hang[pre].lie[cur].max,dat); 41         return ; 42     } 43     int mid=(hang[pre].lie[cur].ll+hang[pre].lie[cur].lr)>>1; 44     if(lh<=mid)upda(pre,cur<<1,hh,lh,dat); 45     else upda(pre,cur<<1|1,hh,lh,dat); 46     hang[pre].lie[cur].max=max(hang[pre].lie[cur<<1].max,hang[pre].lie[cur<<1|1].max); 47 } 48 void update(int cur,int hh,int lh,int dat) 49 { 50     upda(cur,1,hh,lh,dat); 51     if(hang[cur].l==hang[cur].r)return; 52     int mid=(hang[cur].l+hang[cur].r)>>1; 53     if(hh<=mid)update(cur<<1,hh,lh,dat); 54     else update(cur<<1|1,hh,lh,dat); 55 } 56 float quer(int pre,int cur,int l1,int l2) 57 { 58     if(l1<=hang[pre].lie[cur].ll && hang[pre].lie[cur].lr<=l2) 59     return hang[pre].lie[cur].max; 60     int mid=(hang[pre].lie[cur].ll + hang[pre].lie[cur].lr)>>1; 61     float ans=-1; 62     if(l1<=mid)ans=max(ans,quer(pre,cur<<1,l1,l2)); 63     if(mid
       
        <<1|1,l1,l2)); 64     return ans; 65 } 66 float query(int cur,int h1,int h2,int l1,int l2) 67 { 68     if(h1<=hang[cur].l && hang[cur].r<=h2)return quer(cur,1,l1,l2); 69     int mid=(hang[cur].l+hang[cur].r)>>1; 70     float ans=-1; 71     if(h1<=mid)ans=max(ans,query(cur<<1,h1,h2,l1,l2)); 72     if(h2>mid)ans=max(ans,query(cur<<1|1,h1,h2,l1,l2)); 73     return ans; 74 } 75 int main() 76 { 77     while(scanf("%d",&m)==1 && m) 78     { 79         build(1,100,200,0,1000); 80         for(int i=0;i
        
         h2)swap(h1,h2);100                 if(aa1>aa2)swap(aa1,aa2);101                 double ans=query(1,h1,h2,aa1,aa2);102                 if(ans<0)printf("-1\n");103                 else printf("%.1f\n",ans/10);104             }105         }106     }107     return 0;108 }