POJ 3667 Hotel

发表于 | 分类于 ，

题意：排成一行的旅馆房间
checkin时找到最靠左的空闲的长度>=d的连续区间，输出区间的左端点\(r\)并入住
checkout时把从x开始的长度为d的区间变为空闲

线段树的区间合并问题？
空闲0\1表示，区间置0\1可以用打标记来实现。
如何找到满足条件的区间端点\(r\)呢？线段树每个结点维护的信息为从区间左端点开始的全0序列的长度ls，从区间右端点开始的全0序列的长度rs，区间中最长的全0序列长度ms。如果线段树某个结点ms>=d，那么最长的区间可以来入住，最长区间有三种情况：完全在左儿子的区间，横跨左右儿子的区间，完全在右儿子的区间。因为\(r\)要满足最靠左，所以依次尝试上面三种可能情况。

注意在查询的时候下传标记。由于query函数写法的原因，如果某个区间被置为全0\1，那么这个区间一定满足ms[k] == ls[k]，因此一定满足ms[k] < d、ls[k] >= d其中之一而退出。如果继续向下执行，那么结点k一定是没有标记的，不需要向下传标记。这也是为什么第一次交的时候没有push_down也过了。

有了宏定义后代码精简了好多…
刚开始接触这类区间问题，还比较生疏…

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

#define lc (2 * k + 1)
#define rc (2 * k + 2)
#define m ((l + r) / 2)

const int MAX_N = 50000 + 10;
const int ST_SIZE = 1 << 17;

int N, M;
int ls[ST_SIZE], rs[ST_SIZE], ms[ST_SIZE], check[ST_SIZE];

void set_tag(int k, int l, int r, int x) {
  if (x == 0) {
    ls[k] = rs[k] = ms[k] = r - l;
  } else {
    ls[k] = rs[k] = ms[k] = 0;
  }
  check[k] = x;
}

void push_up(int k, int l, int r) {
  ls[k] = ls[lc] == m - l ? ls[lc] + ls[rc] : ls[lc];
  rs[k] = rs[rc] == r - m ? rs[rc] + rs[lc] : rs[rc];
  ms[k] = max(max(ms[lc], ms[rc]), rs[lc] + ls[rc]);
}

void push_down(int k, int l, int r) {
  if (check[k] != -1) {
    set_tag(lc, l, m, check[k]);
    set_tag(rc, m, r, check[k]);
    check[k] = -1;
  }
}

void build(int k, int l, int r) {
  if (l == r - 1) {
    ls[k] = rs[k] = ms[k] = 1;
  } else {
    build(lc, l, m);
    build(rc, m, r);
    push_up(k, l, r);
  }
  check[k] = -1;
}

void update(int k, int l, int r, int a, int b, int x) {
  if (b <= l || r <= a) {
    return;
  } else if (a <= l && r <= b) {
    set_tag(k, l, r, x);
  } else {
    push_down(k, l, r);
    update(lc, l, m, a, b, x);
    update(rc, m, r, a, b, x);
    push_up(k, l, r);
  }
}

int query(int k, int l, int r, int d) {
  if (ms[k] < d) return 0;
  if (ls[k] >= d) return l;
  else {
    // if go down, then there is no tag on k
    push_down(k, l, r);
    if (ms[lc] >= d) return query(lc, l, m, d);
    else if (rs[lc] + ls[rc] >= d) return m - rs[lc];
    else return query(rc, m, r, d);
  }
}

int main() {
  scanf("%d %d", &N, &M);
  build(0, 1, N + 1);
  while (M--) {
    int req, d, x;
    scanf("%d", &req);
    if (req == 1) {
      scanf("%d", &d);
      int res = query(0, 1, N + 1, d);
      if (res) update(0, 1, N + 1, res, res + d, 1);
      printf("%d\n", res);
    } else {
      scanf("%d %d", &x, &d);
      update(0, 1, N + 1, x, x + d, 0);
    }
  }
  return 0;
}