hdu 2795 빌 보드 (선분 트 리 지점)

제목 링크:  http://acm.hdu.edu.cn/showproblem.php?pid=2795
제목 의 대의:    광고 벽 높이 는 위 에서 아래로 h 이 고 너비 왼쪽 에서 오른쪽으로 w 이 며 n 장의 광고 판 도 있다.
                  단위 높이, 너비 와 이 파이 광고 판 으로 벽 을 덮어 줍 니 다.
                  출력 광고 판 높이 (맨 위 에 있 는 것 을 우선 선택 하고 같은 높이 는 맨 왼쪽 에 두 기), 놓 지 않 으 면 출력 - 1
문제 풀이 방향:   선분 트 리 를 만 들 고 구간 은 각 높이 의 남 은 폭 을 표시 합 니 다.
                 맨 아래 의 노드 (Tree [t]. left = = Tree [t]. right), 남 은 너비 MAX 를 저장 합 니 다.
                 다른 노드 는 좌우 하위 트 리 의 남 은 너비 MAX 를 저장 합 니 다.
                 검색 할 때 이 노드 의 MAX 가 광고 판 의 너비 보다 크 면 아래로 찾 습 니 다.
                 좌우 하위 트 리 가 모두 만족 하 는 경우 왼쪽 하위 트 리 를 우선 선택 하고, MAX 가 만족 하지 않 는 다 면 이 하위 트 리 검색 을 중단 합 니 다.
코드:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define Max 210000

#define INF 0x3f3f3f3f

#define MAX(a,b) a>b?a:b

#define MID(a,b) (a+b)>>1

#define L(a) a<<1

#define R(a) (a<<1+1)

typedef struct{

    int left,right;

    int leftmax,rightmax,max;

}Node;

Node Tree[Max<<2];

int n,h,w,pd,kk;

void Build(int t,int l,int r)                  // 1      [l,r]    

{

    int mid;

    Tree[t].left=l,Tree[t].right=r;

    if(Tree[t].left==Tree[t].right)

    {

        Tree[t].max=Tree[t].leftmax=Tree[t].rightmax=w;

        return ;

    }

    mid=MID(Tree[t].left,Tree[t].right);

    Build(L(t),l,mid);

    Build(R(t),mid+1,r);

    Tree[t].leftmax=Tree[L(t)].max;

    Tree[t].rightmax=Tree[R(t)].max;

    Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);

}



void Query(int t,int l,int r,int m)

{

    int mid;

    if(Tree[t].left==l&&Tree[t].right==r&&l==r)  //       l==r

    {

        if(Tree[t].max>=m)

        {

            Tree[t].max-=m;                      //    ，  

            kk=Tree[t].left;

            pd=1;

        }

        return ;

    }

    mid=MID(Tree[t].left,Tree[t].right);

    if(Tree[t].max<m)                            // MAX  m   ，     

        return ;

    if(Tree[t].leftmax>=m)                       //            

        Query(L(t),l,mid,m);

    else if(Tree[t].rightmax>=m)                 //      ，      

        Query(R(t),mid+1,r,m);

    else

        return ;

    Tree[t].leftmax=Tree[L(t)].max;

    Tree[t].rightmax=Tree[R(t)].max;

    Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);

}



int main()

{

    int i,m;

    while(scanf("%d%d%d",&h,&w,&n)!=EOF)

    {

        if(h>n)

            h=n;

        memset(Tree,0,sizeof(Tree));    //      

        Build(1,1,h);                   //  

        for(i=0;i<n;i++)

        {

            scanf("%d",&m);

            pd=0;

            Query(1,1,h,m);             //  [1,h]  MAX>=n   

            if(pd)

                printf("%d
",kk);

            else

                printf("-1
");

        }

    }

    return 0;

}

비고: 오리지널 글, 전재 출처 를 밝 혀 주 십시오.