hdu 1823 二维线段树
2010年12月01日 03:08
题意很明确,貌似主要就是用来测模板的....写的这个二维线段树虽然很长很罗嗦,但还是geilivable的啊,只不过用c++才能过
#include <cstdio> typedef struct { int l,r; double val; } node1; double max(double a,double b){return a>b?a:b;}; void swap(double &a,double &b) { double t=a;a=b;b=t; } struct tree1 { node1 node[3000]; void build(int l,int r,int root) { node[root].l=l;node[root].r=r; node[root].val=-1; if(l==r) return; int m=(l+r)/2; build(l,m,2*root); build(m+1,r,2*root+1); } void update(int x,double val,int root) { if(node[root].val<val) node[root].val=val; if(node[root].l == node[root].r) return; int m=(node[root].l+node[root].r)/2; if(x<=m) update(x,val,2*root); else update(x,val,2*root+1); } double query(int l,int r,int root) { if(node[root].l==l && node[root].r==r) return node[root].val; int m=(node[root].l+node[root].r)/2; if(r<=m) return query(l,r,root*2); else if(l>m) return query(l,r,root*2+1); else return max(query(l,m,root*2), query(m+1,r,root*2+1)); } }; typedef struct {int l,r;tree1 tree; } node2; struct tree2 { node2 node[300]; void build(int xmin,int xmax,int ymin,int ymax,int root) { node[root].l=xmin;node[root].r=xmax; node[root].tree.build(ymin,ymax,1); if(xmin==xmax) return; int m=(xmin+xmax)/2; build(xmin,m,ymin,ymax,2*root); build(m+1,xmax,ymin,ymax,2*root+1); } void update(int x,int y,double val,int root) { node[root].tree.update(y,val,1); if(node[root].l==node[root].r) return; int m=(node[root].l+node[root].r)/2; if(x<=m) update(x,y,val,root*2); else update(x,y,val,root*2+1); } double query(int x1,int x2,int y1,int y2,int root) { if(node[root].l==x1 && node[root].r==x2) return node[root].tree.query(y1,y2,1); int m=(node[root].l+node[root].r)/2; if(x2<=m) return query(x1,x2,y1,y2,2*root); else if(x1>m) return query(x1,x2,y1,y2,2*root+1); else return max(query(x1,m,y1,y2,root*2) ,query(m+1,x2,y1,y2,root*2+1)); } }; tree2 tree; int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout); #endif int n,h,hh;char s[2]; double a,aa,l,ans; while(scanf("%d",&n),n) { tree.build(100,200,0,1000,1); while(n--) { scanf("%s",s); if(s[0]=='I') { scanf("%d %lf %lf",&h,&a,&l); tree.update(h,int(a*10),l,1); } else { scanf("%d %d %lf %lf",&h,&hh,&a,&aa); if(h>hh) {h^=hh;hh^=h;h^=hh;} if(a>aa) swap(a,aa); ans=tree.query(h,hh,int(a*10),int(aa*10),1); if(ans<0) puts("-1"); else printf("%.1f\n",ans); } } } }