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);
}
}
}
}
