二維線段樹，沒什么好說的，郁悶的是我的程序在HDU上提交了多少次一直是WA，到網(wǎng)上參考別人的程序也沒有發(fā)現(xiàn)有什么不一樣的地方！然后自己隨機(jī)生成了N組數(shù)據(jù)和標(biāo)程對比，還是沒能發(fā)現(xiàn)什么。無奈換了一個(gè)OJ——TZC，結(jié)果AC了……
想到了昨天發(fā)生的一件囧事：NOIP2009第一題我只拿了90分，昨天重新做，結(jié)果還是90！看看數(shù)據(jù)，看看自己的結(jié)果，沒有發(fā)現(xiàn)錯(cuò)誤啊~郁悶~后來我把我程序產(chǎn)生的輸出復(fù)制到數(shù)據(jù)上，重新測評，還是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 閱讀(319)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)