首页 > 代码库 > HDU 1823 二维线段树（区间max）

HDU 1823 二维线段树（区间max）

2024-07-15 16:18:59   220人阅读

Luck and Love

Time Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5262    Accepted Submission(s): 1317


Problem Description
世界上上最远的距离不是相隔天涯海角
而是我在你面前
可你却不知道我爱你
                ―― 张小娴

前段日子，枫冰叶子给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
8
I 160 50.5 60.0
I 165 30.0 80.5
I 166 10.0 50.0
I 170 80.5 77.5
Q 150 166 10.0 60.0
Q 166 177 10.0 50.0
I 166 40.0 99.9
Q 166 177 10.0 50.00
 

 

Sample Output
80.5
50.0
99.9
 
 
第一次写二维线段树，代码参考别人的。在本题中以h为x轴区间，以a为y轴区间，因为每个身高里可能含有很多不同的a，所以在普通的线段树中的每个结点里又套了个线段树。
 
代码：
  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <vector>  5 #include <iostream>  6 using namespace std;  7   8 struct mem{  9     int l, r, maxh; 10 }; 11  12 struct node{ 13     mem b[4444]; 14     int l, r; 15 }a[888]; 16  17 void sub_build(int l,int r,int roota,int rootb){ 18     a[roota].b[rootb].l=l; 19     a[roota].b[rootb].r=r; 20     a[roota].b[rootb].maxh=-1; 21     if(l==r) return; 22     int mid=(l+r)/2; 23     sub_build(l,mid,roota,rootb<<1); 24     sub_build(mid+1,r,roota,rootb<<1|1); 25 } 26  27 void build(int la,int ra,int lb,int rb,int root){ 28     sub_build(lb,rb,root,1); 29     a[root].l=la; 30     a[root].r=ra; 31     if(la==ra) return; 32     int mid=(la+ra)/2; 33     build(la,mid,lb,rb,root<<1); 34     build(mid+1,ra,lb,rb,root<<1|1); 35 } 36  37 void sub_update(int p,int val,int roota,int rootb){ 38     if(a[roota].b[rootb].l==p&&a[roota].b[rootb].r==p){ 39         a[roota].b[rootb].maxh=max(a[roota].b[rootb].maxh,val);return; 40     } 41     int mid=(a[roota].b[rootb].l+a[roota].b[rootb].r)/2; 42     if(p<=mid) sub_update(p,val,roota,rootb<<1); 43     else sub_update(p,val,roota,rootb<<1|1); 44     a[roota].b[rootb].maxh=max(a[roota].b[rootb<<1].maxh,a[roota].b[rootb<<1|1].maxh); 45 } 46  47 void update(int p1,int p2,int val,int root){ 48         sub_update(p2,val,root,1); 49     if(a[root].l==p1&&a[root].r==p1){ 50      51         return; 52     } 53     int mid=(a[root].l+a[root].r)/2; 54     if(p1<=mid) update(p1,p2,val,root<<1); 55     else update(p1,p2,val,root<<1|1); 56 } 57  58 int sub_query(int l,int r,int roota,int rootb){ 59     if(a[roota].b[rootb].l==l&&a[roota].b[rootb].r==r){ 60         return a[roota].b[rootb].maxh; 61     } 62     int mid=(a[roota].b[rootb].l+a[roota].b[rootb].r)/2; 63     if(r<=mid) return sub_query(l,r,roota,rootb<<1); 64     else if(l>mid) return sub_query(l,r,roota,rootb<<1|1); 65     else return max(sub_query(l,mid,roota,rootb<<1),sub_query(mid+1,r,roota,rootb<<1|1)); 66 } 67  68 int query(int h1,int h2,int a1,int a2,int root){ 69      70     if(a[root].l==h1&&a[root].r==h2){ 71         return sub_query(a1,a2,root,1); 72     } 73     int mid=(a[root].l+a[root].r)/2; 74     if(h2<=mid) return query(h1,h2,a1,a2,root<<1); 75     else if(h1>mid) return query(h1,h2,a1,a2,root<<1|1); 76     else return max(query(h1,mid,a1,a2,root<<1),query(mid+1,h2,a1,a2,root<<1|1)); 77 } 78  79 main() 80 { 81     int n, i, j, k; 82     int h1, h2; 83     double a1, a2, l; 84     char c[10]; 85     int ans; 86     while(scanf("%d",&n)==1&&n){ 87         build(100,200,0,1000,1); 88         while(n--){ 89             scanf("%s",c); 90         if(strcmp(c,"I")==0){ 91             scanf("%d %lf %lf",&h1,&a1,&l); 92             update(h1,a1*10,l*10,1); 93              94         } 95         else{ 96             scanf("%d %d %lf %lf",&h1,&h2,&a1,&a2); 97             if(h1>h2) swap(h1,h2); 98             if(a1>a2) swap(a1,a2); 99             ans=query(h1,h2,a1*10,a2*10,1);100             if(ans<0) printf("-1\n");101         else printf("%.1lf\n",ans/10.0);102         }103       }    104     }105 }

 


联系
我们