二维线段树，没什么好说的，郁闷的是我的程序在HDU上提交了多少次一直是WA，到网上参考别人的程序也没有发现有什么不一样的地方！然后自己随机生成了N组数据和标程对比，还是没能发现什么。无奈换了一个OJ——TZC，结果AC了……
想到了昨天发生的一件囧事：NOIP2009第一题我只拿了90分，昨天重新做，结果还是90！看看数据，看看自己的结果，没有发现错误啊~郁闷~后来我把我程序产生的输出复制到数据上，重新测评，还是90！
以下是我的代码：
#include<stdio.h>
#define L(x) (x<<1)
#define R(x) (x<<1)+1
#define max(a,b) (a>b?a:b)
const long maxn=107;
typedef struct
{
long a,b,max;
}subtree;
typedef struct
{
long a,b;
subtree sub[maxn*30];
}segment;
segment seg[maxn*3];
void swap(long &a,long &b)
{
long t=a;a=b;b=t;
}
void swap(double &a,double &b)
{
double t=a;a=b;b=t;
}
void build_sub(long x,long y,long FT,long now)
{
long mid=(x+y)>>1;
seg[FT].sub[now].a=x;seg[FT].sub[now].b=y;
seg[FT].sub[now].max=-1;
if(x<y)
{
build_sub(x,mid,FT,L(now));
build_sub(mid+1,y,FT,R(now));
}
}
void build(long Hx,long Hy,long Ax,long Ay,long now)
{
long mid=(Hx+Hy)>>1;
seg[now].a=Hx;seg[now].b=Hy;
build_sub(Ax,Ay,now,1);
if(Hx<Hy)
{
build(Hx,mid,Ax,Ay,L(now));
build(mid+1,Hy,Ax,Ay,R(now));
}
}
void insert_sub(long A,long FT,long now,long love)
{
long a=seg[FT].sub[now].a,b=seg[FT].sub[now].b,mid=(a+b)>>1;
seg[FT].sub[now].max=max(seg[FT].sub[now].max,love);
if(a<b)
{
if(mid>=A)
insert_sub(A,FT,L(now),love);
else
insert_sub(A,FT,R(now),love);
}
}
void insert(long H,long A,long now,long love)
{
long a=seg[now].a,b=seg[now].b,mid=(a+b)>>1;
insert_sub(A,now,1,love);
if(a<b)
{
if(mid>=H)
insert(H,A,L(now),love);
else
insert(H,A,R(now),love);
}
}
long query_sub(long x,long y,long FT,long now)
{
long a=seg[FT].sub[now].a,b=seg[FT].sub[now].b,mid=(a+b)>>1;
long re=-1;
if(x<=a&&b<=y)
re=seg[FT].sub[now].max;
else
{
if(mid>=x)
re=query_sub(x,y,FT,L(now));
if(mid+1<=y)
re=max(re,query_sub(x,y,FT,R(now)));
}
return re;
}
long query(long Hx,long Hy,long Ax,long Ay,long now)
{
long a=seg[now].a,b=seg[now].b,mid=(a+b)>>1;
long re=-1;
if(Hx<=a&&b<=Hy)
re=query_sub(Ax,Ay,now,1);
else
{
if(mid>=Hx)
re=query(Hx,Hy,Ax,Ay,L(now));
if(mid+1<=Hy)
re=max(re,query(Hx,Hy,Ax,Ay,R(now)));
}
return re;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
long m;
char cmd[7];
while(scanf("%ld",&m)==1)
{
if(m==0) break;
build(100,200,0,1000,1);
while(m--)
{
scanf("%s",cmd);
if(cmd[0]=='I')
{
long H;
double A,L;
scanf("%ld%lf%lf",&H,&A,&L);
insert(H,(long)(A*10),1,(long)(L*10));
}
else
{
long Hx,Hy;
double Ax,Ay,ans;
scanf("%ld%ld%lf%lf",&Hx,&Hy,&Ax,&Ay);
if(Hx>Hy) swap(Hx,Hy);
if(Ax>Ay) swap(Ax,Ay);
ans=query(Hx,Hy,(long)(Ax*10),(long)(Ay*10),1);
if(ans<=0)
printf("%ld\n",-1);
else
printf("%.1lf\n",ans/10);
}
}
}
return 0;
}
posted on 2010-02-22 13:56
lee1r 阅读(302)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构