二维线段树入门题
分别以身高和活泼度开两维
以身高-100，，活泼度*10,为两个区间
所谓的二维就是在第一维查找到正确位置时，进入第二维再查找
#include "stdio.h"#include "string.h"double ans;double Max(double a,double b){if (a<b) return b;else return a;}struct Mark{int l,r;double x;};struct Data{int l,r; // 身高维Mark mark[4010]; // 活泼度维}data[410];void build_sec(int l,int r,int k,int kk){int mid;data[k].mark[kk].l=l;data[k].mark[kk].r=r;data[k].mark[kk].x=-1;if (l==r) return ;mid=(l+r)/2;build_sec(l,mid,k,kk*2);build_sec(mid+1,r,k,kk*2+1);}void build_main(int l,int r,int ll,int rr,int k){int mid;data[k].l=l;data[k].r=r;build_sec(ll,rr,k,1);if (l==r) return ;mid=(l+r)/2;build_main(l,mid,ll,rr,k*2);build_main(mid+1,r,ll,rr,k*2+1);}void updata_sec(int w2,double z,int k,int kk){int mid;if (z>data[k].mark[kk].x) data[k].mark[kk].x=z;if (data[k].mark[kk].l==data[k].mark[kk].r) return ;mid=(data[k].mark[kk].l+data[k].mark[kk].r)/2;if (w2<=mid) updata_sec(w2,z,k,kk*2);else updata_sec(w2,z,k,kk*2+1);}void updata_main(int w1,int w2,double z,int k){int mid;updata_sec(w2,z,k,1);if (data[k].l==data[k].r) return ;mid=(data[k].l+data[k].r)/2;if (w1<=mid) updata_main(w1,w2,z,k*2);else updata_main(w1,w2,z,k*2+1);}double query_sec(int l,int r,int k,int kk){int mid;if (data[k].mark[kk].l==l && data[k].mark[kk].r==r)return data[k].mark[kk].x;mid=(data[k].mark[kk].l+data[k].mark[kk].r)/2;if (r<=mid) return query_sec(l,r,k,kk*2);elseif (l>mid) return query_sec(l,r,k,kk*2+1);elsereturn Max(query_sec(l,mid,k,kk*2),query_sec(mid+1,r,k,kk*2+1));}void query_main(int l,int r,int ll,int rr,int k){int mid;if (data[k].l==l && data[k].r==r){ans=Max(ans,query_sec(ll,rr,k,1));return ;}mid=(data[k].l+data[k].r)/2;if (r<=mid) query_main(l,r,ll,rr,k*2);elseif (l>mid) query_main(l,r,ll,rr,k*2+1);else{query_main(l,mid,ll,rr,k*2);query_main(mid+1,r,ll,rr,k*2+1);}}int main(){int n,x,w1,w2,l1,l2,r1,r2;double y,z;char ch[10];while (scanf("%d",&n)!=EOF){if(n==0) break;build_main(0,100,0,1000,1);while (n–){scanf("%s",ch);if (ch[0]=='I'){scanf("%d%lf%lf",&x,&y,&z);w1=x-100;w2=y*10;updata_main(w1,w2,z,1);}else{scanf("%d%d%lf%lf",&l1,&r1,&y,&z);l1-=100;r1-=100;l2=y*10;r2=z*10;if (l1>r1) {x=l1; l1=r1; r1=x;}if (l2>r2) {x=l2; l2=r2; r2=x;}ans=-1.0;query_main(l1,r1,l2,r2,1);if (ans+1<=0.000000001)printf("-1\n");elseprintf("%.1lf\n",ans);}}}return 0;}
“人无完人金无足赤”，只要是人就不会是完美的，
