HDU 1823 二維線段樹

HDU 1823 二維線段樹

二維線段樹入門題

分別以身高和活潑度開兩維

以身高-100，活潑度*10,為兩個區間

所謂的二維就是在第一維查找到正確位置時，進入第二維再查找

#include "stdio.h"
#include "string.h"
double ans;
double Max(double a,double b)
{
    if (adata[k].mark[kk].x) data[k].mark[kk].x=z;

    if (data[k].mark[kk].l==data[k].mark[kk].r) return ;
    mid=(data[k].mark[kk].l+data[k].mark[kk].r)/2;

    if (w2<=mid) updata_sec(w2,z,k,kk*2);
    else updata_sec(w2,z,k,kk*2+1);
}

void updata_main(int w1,int w2,double z,int k)
{
    int mid;
    updata_sec(w2,z,k,1);

    if (data[k].l==data[k].r) return ;
    mid=(data[k].l+data[k].r)/2;
    if (w1<=mid) updata_main(w1,w2,z,k*2);
    else updata_main(w1,w2,z,k*2+1);
}

double query_sec(int l,int r,int k,int kk)
{
    int mid;
    if (data[k].mark[kk].l==l && data[k].mark[kk].r==r)
        return data[k].mark[kk].x;

    mid=(data[k].mark[kk].l+data[k].mark[kk].r)/2;
    if (r<=mid) return query_sec(l,r,k,kk*2);
    else
        if (l>mid) return query_sec(l,r,k,kk*2+1);
    else
        return Max(query_sec(l,mid,k,kk*2),query_sec(mid+1,r,k,kk*2+1));
}
void query_main(int l,int r,int ll,int rr,int k)
{
    int mid;
    if (data[k].l==l && data[k].r==r)
    {
        ans=Max(ans,query_sec(ll,rr,k,1));
        return ;
    }
    mid=(data[k].l+data[k].r)/2;
    if (r<=mid) query_main(l,r,ll,rr,k*2);
    else
        if (l>mid) query_main(l,r,ll,rr,k*2+1);
    else
    {
        query_main(l,mid,ll,rr,k*2);
        query_main(mid+1,r,ll,rr,k*2+1);
    }
}
int main()
{
    int n,x,w1,w2,l1,l2,r1,r2;
    double y,z;
    char ch[10];
    while (scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        build_main(0,100,0,1000,1);
        while (n--)
        {
            scanf("%s",ch);
            if (ch[0]=='I')
            {
                scanf("%d%lf%lf",&x,&y,&z);
                w1=x-100;
                w2=y*10;
                updata_main(w1,w2,z,1);
            }
            else
            {
                scanf("%d%d%lf%lf",&l1,&r1,&y,&z);
                l1-=100;
                r1-=100;
                l2=y*10;
                r2=z*10;
                if (l1>r1) {x=l1; l1=r1; r1=x;}
                if (l2>r2) {x=l2; l2=r2; r2=x;}
                ans=-1.0;
                query_main(l1,r1,l2,r2,1);
                if (ans+1<=0.000000001)
                    printf("-1\n");
                else
                    printf("%.1lf\n",ans);
            }
        }
    }
    return 0;
}