[原创]POJ 3667 Hotel [线段树+区间更新]【数据结构】

2016-12-28 19:13:06 Tabris_ 阅读数：264

博客爬取于2020-06-14 22:42:29
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53912212

题目链接:http://poj.org/problem?id=3667

---------------------------------------------------------------------------------.
Hotel
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 16674 Accepted: 7234
Description

The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r…r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi …Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

Input

  • Line 1: Two space-separated integers: N and M
  • Lines 2…M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

Output

  • Lines 1…: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

Sample Input

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
Sample Output

1
4
7
0
5
Source

USACO 2008 February Gold
--------------------------------------------------------------------------------.

题目大意:
就是在[1,n][1,n]这个区间.
有两种操作

  1. x 问你有没有连续x个的空房,有的话就在最左面的住进去,输出最左边的房间号,没有的话就输出0;
  2. a b 就是从a开始接下来的b个房间的人退房 也就是[a,a+b−1][a,a+b-1]这个区间的房间都退房了.

解题思路:
还是基本的想到了线段树的区间更新.
不一样的就是这次要查找的是连续的x个长度,
这点想了好久,最后还是想到在节点上增加两个值,来代表区间中最左边有多少个连续的,最右边代表有多少个连续的,原本的值来代表区间内最大的连续的长度是多少.然后维护一下就行了.

思路构建的很容易 ,但是最后代码实现的时候发现好麻烦啊,因为一个rr写成了ll 硬是调试了2个小时有没有啊…

跟普通的区间更新差别也就是在pushup和pushdown两个操作上面.
pushup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
维护左右的最大值,
在维护区间内的最大值就好了
*/
void pushup(int rt){

    if(tree[ll].ls == tree[ll].len())
        tree[rt].ls = tree[ll].len() + tree[rr].ls;
    else tree[rt].ls = tree[ll].ls;

    if(tree[rr].rs == tree[rr].len())
        tree[rt].rs = tree[rr].len() + tree[ll].rs;
    else tree[rt].rs = tree[rr].rs;

    tree[rt].val = max(tree[ll].rs + tree[rr].ls,max(tree[rr].val,tree[ll].val));

}

pushdown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
这时候
0代表入房
1代表退房
维护的时候直接tree[ll].len()*tree[rt].lazy;就好了 方便  代码还短一点.
*/
void pushdown(int rt){
    if(tree[rt].lazy != -1){
        tree[ll].lazy = tree[rr].lazy = tree[rt].lazy;
        tree[ll].val  = tree[ll].ls   = tree[ll].rs = tree[ll].len()*tree[rt].lazy;
        tree[rr].val  = tree[rr].ls   = tree[rr].rs = tree[rr].len()*tree[rt].lazy;
        tree[rt].val  = tree[rt].ls   = tree[rt].rs = tree[rt].len()*tree[rt].lazy;
        tree[rt].lazy = -1;
    }
}

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
# include <map>
# include <queue>
using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    MOD = 1e9+7;
const int    N   = 50000+5;
const double eps = 1e-6;
const double PI  = acos(-1.0);

/***********************************************************************/

struct node {
    int l,r;
    int val;
    int ls,rs;
    int lazy;
    int md(){return (l+r)>>1;}
    int len(){return (r-l+1);}
}tree[N<<2];

# define ll  (rt<<1)
# define rr  (rt<<1|1)
# define mid (tree[rt].md())

void pushup(int rt){

    if(tree[ll].ls == tree[ll].len())
        tree[rt].ls = tree[ll].len() + tree[rr].ls;
    else tree[rt].ls = tree[ll].ls;

    if(tree[rr].rs == tree[rr].len())
        tree[rt].rs = tree[rr].len() + tree[ll].rs;
    else tree[rt].rs = tree[rr].rs;

    tree[rt].val = max(tree[ll].rs + tree[rr].ls,max(tree[rr].val,tree[ll].val));
}

void build(int rt,int l,int r){
    tree[rt].l  =l,tree[rt].r=r,tree[rt].lazy=-1;
    tree[rt].val=tree[rt].ls=tree[rt].rs=tree[rt].len();
    if(l==r) return ;
    build(ll,l,mid);
    build(rr,mid+1,r);
}

void pushdown(int rt){
    if(tree[rt].lazy != -1){
        tree[ll].lazy = tree[rr].lazy = tree[rt].lazy;
        tree[ll].val  = tree[ll].ls   = tree[ll].rs = tree[ll].len()*tree[rt].lazy;
        tree[rr].val  = tree[rr].ls   = tree[rr].rs = tree[rr].len()*tree[rt].lazy;
        tree[rt].val  = tree[rt].ls   = tree[rt].rs = tree[rt].len()*tree[rt].lazy;
        tree[rt].lazy = -1;
    }
}

void update(int rt,int L,int R,int op){  //update 就是将 所有的 [a,a+b-1] 清一下
    if(L<=tree[rt].l&&tree[rt].r<=R){
        if(1 == op){ //入住
            tree[rt].val = tree[rt].ls   = tree[rt].rs = 0;
            tree[rt].lazy = 0;
        }
        else {  //退房
            tree[rt].val  = tree[rt].ls   = tree[rt].rs = tree[rt].len();
            tree[rt].lazy = 1;
        }
        return ;
    }
    pushdown(rt);
    if(L<=mid) update(ll,L,R,op);
    if(R> mid) update(rr,L,R,op);
    pushup(rt);
}

int query(int rt,int val){

    if(tree[rt].l==tree[rt].r){
        if(val == tree[rt].val) return tree[rt].l;
        return 0;
    }

    pushdown(rt);
    if(tree[ll].val>=val)
        return query(ll,val);
    else if(tree[rr].ls+tree[ll].rs >= val)
        return tree[ll].r-tree[ll].rs+1;
    else if(tree[rr].val >= val)
        return query(rr,val);

    return 0;
}

int main()
{
	int n,m;
    int op,a,b;
    while(~s1(n)){
        s1(m);
        build(1,1,n);
        Rep(i,1,m){
            s1(op);
            if(1==op){
                s1(a);
                int tem = query(1,a);
                if(tem)   update(1,tem,a+tem-1,op);
                printf("%d\n",tem);
            }
            else {
                s1(a),s1(b);
                update(1,a,a+b-1,op);
            }
        }
    }
    return 0;
}