hdu1823 2차원 라인 트리

처음으로 2차원 트리를 썼는데 다른 사람의 코드를 참고했다. 주요한 사고방식은 1차원 트리와 유사하지만 2차원 사상은 행렬 4분으로 바뀌었다.

#include<cstdio>
#include<cstring>
int seg[8000*800],n;
int max(int a,int b)
{
    return a>b?a:b;
}
void ud(int al,int ar,int hl,int hr,int a,int h,int d,int i)
{
    if(seg[i]<d)
        seg[i]=d;
    if(al==ar&&hl==hr)
        return;
    int am=(al+ar)>>1;
    int hm=(hl+hr)>>1;
    if(a<=am&&h<=hm)
        ud(al,am,hl,hm,a,h,d,4*i+1);
    if(a<=am&&h>hm)
        ud(al,am,hm+1,hr,a,h,d,4*i+2);
    if(a>am&&h<=hm)
        ud(am+1,ar,hl,hm,a,h,d,4*i+3);
    if(a>am&&h>hm)
        ud(am+1,ar,hm+1,hr,a,h,d,4*i+4);
}
int qu(int al,int ar,int hl,int hr,int a1,int a2,int h1,int h2,int i)
{
    int t=-1;
    if(a1<=al&&ar<=a2&&h1<=hl&&hr<=h2)
        return seg[i];
    int am=(al+ar)>>1;
    int hm=(hl+hr)>>1;
    if(am>=a1&&hm>=h1)
        t=max(t,qu(al,am,hl,hm,a1,a2,h1,h2,4*i+1));
    if(am>=a1&&h2>hm)
        t=max(t,qu(al,am,hm+1,hr,a1,a2,h1,h2,4*i+2));
    if(a2>am&&hm>=h1)
        t=max(t,qu(am+1,ar,hl,hm,a1,a2,h1,h2,4*i+3));
    if(a2>am&&h2>hm)
        t=max(t,qu(am+1,ar,hm+1,hr,a1,a2,h1,h2,4*i+4));
    return t;
}
int main()
{
    while(scanf("%d",&n),n)
    {
        memset(seg,-1,sizeof(seg));
        for(int i=0;i<n;i++)
        {
            char s[2];
            scanf("%s",s);
            if(*s=='I')
            {
                int h;
                double a,f;
                scanf("%d%lf%lf",&h,&a,&f);
                ud(0,1000,100,200,int(10*a),h,int(10*f),1);
            }
            else
            {
                int h1,h2;
                double a1,a2;
                scanf("%d%d%lf%lf",&h1,&h2,&a1,&a2);
                if(h1>h2)
                {
                    int tp=h1;
                    h1=h2;
                    h2=tp;
                }
                if(a1>a2)
                {
                    double tp=a1;
                    a1=a2;
                    a2=tp;
                }
                int ans=qu(0,1000,100,200,int(10*a1),int(10*a2),h1,h2,1);
                if(ans==-1)
                    puts("-1");
                else
                    printf("%.1lf
",(double)ans/10);
            }
        }
    }
    return 0;
}