HDU:2795 Billboard

선분 나무의 위력 을 다시 한 번 배 웠 다.최대 값 을 유지 하고 왼쪽 을 우선 선택 하 며 업데이트 작업 은 검색 에 적 혀 있 습 니 다.
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
#define INF 2139062143
#define MAXN 105
using namespace std;
const int MAX_N= 1<<19;
int mxn,n,h,w;
int dat[MAX_N];
void build(int k,int l,int r)
{
    dat[k]=w;
    if(l==r) return;
    build(2*k,l,(l+r)/2);
    build(2*k+1,(l+r)/2+1,r);
}
void Init()
{
    mxn=1;
    while(mxn<h) mxn*=2;
    memset(dat,0,sizeof(dat));
    build(1,1,h);

}
int query(int x,int k,int l,int r)
{
    if(l==r)
    {
        dat[k]-=x;
        return l;
    }
    else
    {
        int ans=0;
        if(dat[2*k]>=x) ans=query(x,2*k,l,(l+r)/2);
        else  ans=query(x,2*k+1,(l+r)/2+1,r);
        dat[k]=max(dat[2*k],dat[2*k+1]);
        return ans;
    }
}
int main()
{
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        h=min(h,n);
        Init();
        int t;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&t);
            if(dat[1]<t) printf("-1
");
            else printf("%d
",query(t,1,1,h));
        }
    }
    return 0;
}

 나중에 다시 썼어 요.
먼저 h = min (h, 200000), h 를 결점 으로 선분 수 를 만 들 고 나무 에 특정한 구간 내 너비 의 최대 치 를 저장 합 니 다.이렇게 매번 조 회 는 t 보다 큰 잎 결점 을 찾 는 것 과 같 으 며 우선 왼쪽 에서 찾 는 것 이다.찾 은 잎의 결점 은 동시에 t 를 빼 고 아버지의 결점 을 갱신 해 야 한다.존재 하지 않 을 때 되 돌아 오기 - 1.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#define ll  long long
#define INF 2139062143
#define inf -2139062144
#define MOD 20071027
#define MAXN  500005
#define LEN 222222<<2
using namespace std;
int h,w,n;
struct Segment_tree
{
private:
    int data[LEN],sz;
    void pushup(int o)
    {
        data[o]=max(data[o<<1],data[o<<1|1]);
    }
    int myquery(int o,int L,int R,int v)
    {
        if(L==R)
        {
            data[o]-=v;
            return L;
        }
        int M=(L+R)/2;
        int res=-1;
        if(v<=data[o<<1])  res=myquery(o<<1,L,M,v);
        else if(v<=data[o<<1|1])res= myquery(o<<1|1,M+1,R,v);
        pushup(o);
        return res;
    }
public:
    void clear()
    {
        sz=h;
    }
    void build(int o,int L,int R)
    {
        if(L==R) data[o]=w;
        else
        {
            int M=(L+R)/2;
            build(o<<1,L,M);
            build(o<<1|1,M+1,R);
            data[o]=w;
        }
    }
    int query(int p)
    {
        return myquery(1,1,sz,p);
    }
};
Segment_tree tree;
int main()
{

    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        int t;
        h=min(h,200000);
        tree.clear();
        tree.build(1,1,h);
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&t);
            printf("%d
",tree.query(t));
        }
    }
    return 0;
}