程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3667(線段樹區間合並)

poj3667(線段樹區間合並)

編輯:C++入門知識

題目鏈接:poj3667

/*poj 3667 Hotel 線段樹區間合並
題意:
操作1:詢問是否有連續x間房間可以住,輸出最左端的房間位置
操作2:顧客退房,將房間清空,表示沒有人住

思路:
利用線段樹建立模型,維護最大連續區間長度,其中區間長度就是對應的房間數目,
並且對應區間中最左邊的端點就是ans,同時因為需要求出連續區間的最大長度,
因此每次PushUp時都將左右區間合並,lsum維護左區間的最大長度,rsum維護右區間的最大長度,
sum維護區間1…N中的最大連續區間長度,cover標志對應區間是否為空(沒有住客)
*/
#include
#include
#include
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 150000;

int cover[N<<2];
int llen[N<<2],rlen[N<<2],mlen[N<<2];
void build(int l, int r, int rt)
{
    llen[rt] = rlen[rt] = mlen[rt] = r - l + 1;
    cover[rt] = -1;
    if(l == r) return;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
}
void pushdown(int rt, int m)//更新子節點
{
    if(cover[rt] != -1)
    {
        llen[rt<<1] = rlen[rt<<1] = mlen[rt<<1] = cover[rt] ? 0 : m - (m>>1);
        llen[rt<<1|1] = rlen[rt<<1|1] = mlen[rt<<1|1] = cover[rt] ? 0 : (m>>1);
        cover[rt<<1] = cover[rt<<1|1] = cover[rt];
        cover[rt] = -1;
    }
}
void pushup(int rt, int m)//更新父節點
{
    llen[rt] = llen[rt<<1];
    rlen[rt] = rlen[rt<<1|1];
    if(llen[rt] == m - (m>>1)) llen[rt] += llen[rt<<1|1];
    if(rlen[rt] == (m>>1)) rlen[rt] += rlen[rt<<1];
    mlen[rt] = max(llen[rt<<1|1] + rlen[rt<<1], max(mlen[rt<<1], mlen[rt<<1|1]));
}
void update(int L, int R, int c, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        llen[rt] = rlen[rt] = mlen[rt] = c?0:r-l+1;
        cover[rt] = c;
        return ;
    }
    pushdown(rt, r-l+1);
    int m = (l + r) >> 1;
    if(L <= m) update(L, R, c, lson);
    if(m < R) update(L, R, c, rson);
    pushup(rt, r-l+1);
}
int query(int num, int l, int r, int rt)
{
    if(l == r) return l;
    pushdown(rt, r-l+1);
    int m = (l+r) >> 1;
    if(mlen[rt<<1] >= num)  // 左連續區間長度
        return query(num, lson);
    else if(rlen[rt<<1] + llen[rt<<1|1] >= num) // 左區間右半部分與右區間左半部分長度
        return m - rlen[rt<<1] + 1;
    return query(num, rson);
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        build(1, n ,1);
        while(m--)
        {
            int op,x,y;
            scanf("%d",&op);
            if(op == 1)
            {
                scanf("%d",&x);
                if(mlen[1] < x) puts("0");
                else
                {
                    int ans = query(x, 1, n, 1);
                    printf("%d\n",ans);
                    update(ans, ans + x - 1, 1, 1, n, 1);
                }
            }
            if(op == 2)
            {
                scanf("%d%d",&x,&y);
                update(x, x+y-1, 0, 1, n, 1);
            }
        }
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved