HDU 1823 Luck and Love

Luck and Love

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

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.0 0

Sample Output

80.5 50.0 99.9

题解：二维线段树练习题。

总结一下写树套树的注意事项吧

1.一定区分好谁套谁，谁是x树谁是y树。

2.函数名、变量名一定一致，对于我就是所有的y树都加上_x后缀。

3.更新要更新到底，查询正常查询，这点我想了好久。。。

4.先写y树，然后往上套x树。

5.一定注意好内存指针神马的。。。树套树指针比较乱

5.宏看好了是哪个。。。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cstring>
  7 #define PAU putchar(' ')
  8 #define ENT putchar('
')
  9 #define CH for(int d=0;d<2;d++)if(ch[d])
 10 #define lson x->ch[0],L,M
 11 #define rson x->ch[1],M+1,R
 12 #define lsonx x,y->ch[0],L,M
 13 #define rsonx x,y->ch[1],M+1,R
 14 using namespace std;
 15 const int maxn=200+10,maxnode=400+10,maxnode2=4000,inf=-1u>>1;
 16 struct nodex{
 17     nodex*ch[2];double mx;int siz;
 18     void init(double a){mx=a;return;}
 19     void update(){
 20         mx=-inf;CH{mx=max(ch[d]->mx,mx);}return;
 21     }
 22 };
 23 struct node{
 24     nodex segx[maxnode2],*nodecntx,*rootx;node*ch[2];int siz;node(){nodecntx=segx;}
 25 }seg[maxnode],*nodecnt=seg,*root;
 26 int n,m,pos,posx,qlx,qrx,ql,qr;double cv;
 27 void buildx(node*&x,nodex*&y,int L=0,int R=m){
 28     y=x->nodecntx++;int M=L+R>>1;if(L==R)y->init(-inf);
 29     else buildx(lsonx),buildx(rsonx),y->update();y->siz=R-L+1;return;
 30 }
 31 void build(node*&x=root,int L=1,int R=n){
 32     x=nodecnt++;buildx(x,x->rootx);int M=L+R>>1;if(L==R);
 33     else build(lson),build(rson);x->siz=R-L+1;return;
 34 }
 35 void updatex(node*&x,nodex*&y,int L=0,int R=m){
 36     if(L==R)y->mx=max(y->mx,cv);
 37     else{int M=L+R>>1;
 38         if(posx<=M)updatex(lsonx);else updatex(rsonx);y->update();
 39     }return;
 40 }
 41 void update(node*&x=root,int L=1,int R=n){
 42     updatex(x,x->rootx);if(L==R);
 43     else{int M=L+R>>1;
 44         if(pos<=M)update(lson);else update(rson);
 45     }return;
 46 }
 47 double _mx;
 48 void queryx(node*&x,nodex*&y,int L=0,int R=m){
 49     if(qlx<=L&&R<=qrx)_mx=max(_mx,y->mx);
 50     else{int M=L+R>>1;
 51         if(qlx<=M)queryx(lsonx);if(qrx>M)queryx(rsonx);
 52     }return;
 53 }
 54 void query(node*&x=root,int L=1,int R=n){
 55     if(ql<=L&&R<=qr)queryx(x,x->rootx);
 56     else{int M=L+R>>1;
 57         if(ql<=M)query(lson);if(qr>M)query(rson);
 58     }return;
 59 }
 60 inline int read(){
 61     int x=0,sig=1;char ch=getchar();
 62     while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
 63     while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
 64     return x*=sig;
 65 }
 66 inline void write(int x){
 67     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
 68     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
 69     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
 70 }
 71 void init(){
 72     int Q;
 73     while(scanf("%d",&Q) && Q){
 74         int i,j;
 75         m=1000;n=200;
 76         build(root,100,200);
 77         char str[3];
 78         while(Q--){
 79             scanf("%s",str);
 80             if(str[0]=='I'){
 81                 double x,y;
 82                 int h;
 83                 scanf("%d%lf%lf",&h,&x,&y);
 84                 int xx=x*10;
 85                 pos=h;posx=xx;cv=y;
 86                 update(root,100,200);
 87             } else {
 88                 int h1,h2;
 89                 double x1,x2;
 90                 int y1,y2;
 91                 scanf("%d%d%lf%lf",&h1,&h2,&x1,&x2);
 92                 y1=x1*10,y2=x2*10;
 93                 if(h1>h2)swap(h1,h2);
 94                 if(y1>y2)swap(y1,y2);
 95                 ql=h1;qr=h2;qlx=y1;qrx=y2;
 96                 _mx=-inf;query(root,100,200);
 97                 if(_mx==-inf)printf("-1
");
 98                 else printf("%.1lf
",_mx);
 99             }
100         }for(node*x=seg;x!=nodecnt;x++)x->nodecntx=x->segx;nodecnt=seg;
101     }
102     return;
103 }
104 void work(){
105     return;
106 }
107 void print(){
108     return;
109 }
110 int main(){init();work();print();return 0;}