学步园

一道很裸的二维线段树。

题意：操作①：加入一些mm的身高(x维)，活泼度(y维)，缘分值。

         操作②：给定一个身高区间，一个活泼值区间，求出该区间内缘分值的最大值。

二维线段树，其实也很简单，整个就是一个“树套树”的结构，一维线段树中每个结点中有一颗子树。

由一维推广到二维，在一维中的的一个值，变成了一颗树。

查询的时候就是先找到对应的身高区间，然后再在活泼度区间查找最大的缘分值。

// hdu 1823 luck and love 二维线段树<br /> #include<iostream><br /> #include<algorithm><br /> #include<cstring><br /> #include<cstdio><br /> using namespace std;<br /> const int MAX=200;</p> <p>struct SUBTREE<br /> {<br /> int l,r;<br /> double dd;<br /> };<br /> struct STREE<br /> {<br /> int l,r;<br /> SUBTREE sub[4000];<br /> }ST[4*MAX];</p> <p>void init(int root,int rt,int ll,int rr)<br /> {<br /> ST[root].sub[rt].l=ll;<br /> ST[root].sub[rt].r=rr;<br /> ST[root].sub[rt].dd=-1;<br /> if(ll==rr) return ;<br /> int mid=(ll+rr)/2;<br /> init(root,2*rt,ll,mid);<br /> init(root,2*rt+1,mid+1,rr);<br /> }<br /> void Build(int root,int left,int right,int ll,int rr)<br /> {<br /> ST[root].l=left;<br /> ST[root].r=right;<br /> init(root,1,ll,rr);<br /> if(left==right) return ;<br /> int mid=(left+right)/2;<br /> Build(2*root,left,mid,ll,rr);<br /> Build(2*root+1,mid+1,right,ll,rr);<br /> }</p> <p>void add(int root,int rt,int sd,double val)<br /> {<br /> ST[root].sub[rt].dd=max(val,ST[root].sub[rt].dd);<br /> if(ST[root].sub[rt].l==ST[root].sub[rt].r)<br /> {<br /> return ;<br /> }<br /> int mid=(ST[root].sub[rt].l+ST[root].sub[rt].r)/2;<br /> if(sd<=mid) add(root,2*rt,sd,val);<br /> else add(root,2*rt+1,sd,val);<br /> ST[root].sub[rt].dd=max(ST[root].sub[2*rt].dd,ST[root].sub[2*rt+1].dd);<br /> }</p> <p>void Insert(int root,int d,int sd,double val)<br /> {<br /> add(root,1,sd,val);<br /> if(ST[root].l==ST[root].r)<br /> {<br /> return ;<br /> }<br /> if(d<=ST[2*root].r) Insert(2*root,d,sd,val);<br /> else Insert(2*root+1,d,sd,val);<br /> // up(root,1);<br /> }</p> <p>double ser(int root,int rt,int ll,int rr)<br /> {<br /> if(ST[root].sub[rt].l==ll&&ST[root].sub[rt].r==rr)<br /> {<br /> return ST[root].sub[rt].dd;<br /> }<br /> int mid=(ST[root].sub[rt].l+ST[root].sub[rt].r)/2;<br /> if(rr<=mid) return ser(root,2*rt,ll,rr);<br /> else if(ll>mid) return ser(root,2*rt+1,ll,rr);<br /> else<br /> {<br /> double aa=ser(root,2*rt,ll,mid);<br /> double bb=ser(root,2*rt+1,mid+1,rr);<br /> return aa>bb?aa:bb;<br /> }<br /> }<br /> double Find(int root,int left,int right,int ll,int rr)<br /> {<br /> if(ST[root].l==left&&ST[root].r==right)<br /> {<br /> double tmp=ser(root,1,ll,rr);<br /> return tmp;<br /> }<br /> int mid=(ST[root].l+ST[root].r)/2;<br /> if(right<=mid) return Find(2*root,left,right,ll,rr);<br /> else if(left>mid) return Find(2*root+1,left,right,ll,rr);<br /> else<br /> {<br /> double aa=Find(2*root,left,mid,ll,rr);<br /> double bb=Find(2*root+1,mid+1,right,ll,rr);<br /> return aa>bb?aa:bb;<br /> }<br /> }<br /> int M;<br /> int main()<br /> {<br /> int high,act;<br /> char ch[10];<br /> double tt,love;<br /> while(scanf("%d",&M)&&M)<br /> {<br /> Build(1,100,200,0,1000);</p> <p> while(M--)<br /> {<br /> scanf("%s",ch);<br /> if(ch[0]=='I')<br /> {<br /> scanf("%d%lf%lf",&high,&tt,&love);<br /> act=(int)(tt*10);<br /> Insert(1,high,act,love);<br /> }<br /> else<br /> {<br /> int lh,rh;<br /> double la,ra;<br /> scanf("%d%d%lf%lf",&lh,&rh,&la,&ra);<br /> if(lh>rh) lh^=rh^=lh^=rh;<br /> if(la>ra) {double tmp=la;la=ra;ra=tmp;}<br /> double ans=Find(1,lh,rh,(int)(la*10),(int)(ra*10));<br /> if(ans==-1) puts("-1");<br /> else printf("%.1lf/n",ans);<br /> }<br /> }<br /> }<br /> system("pause");<br /> return 0;<br /> }<br />