[PKU3667]Hotel [USACO 2008 Feb]

这题是线段树的经典应用:求区间左边连续最长空位。为了O(logn)的复杂度,得用lazy-tag,因此也增大了代码复杂度。

线段树中记录三个东西:lmax, rmax, sum,分别为区间左部起最长空位,从右边起最长空位,区间总共的空位。因为当sum==0时lmax=rmax=0;sum==rig-lef+1时,lmax=rmax=rig-lef+1;sum!=0且sum!=rig-lef+1的时候lmax/rmax不固定;且sum可以用来判断区间是否有足够的空位,因此用sum作tag再合适不过了。

根据这个定义,遗传和上传就确定了:

遗传:如果sum==0,那么其儿子的sum=lmax=max=0;sum==rig-lef+1,其儿子的sum=lmax=rmax=各自区间长度。

上传:lmax=left_son.lmax, rmax=right_son.rmax, sum=left_son.sum+right_son.sum。当然要特殊处理:如果left_son.lmax==left_son的区间,也就是左右孩子在左侧相连了,那么lmax+=right_son.lmax。rmax类似。

插入/删除:先遗传,如果区间包含在修改区间内,那么马上修改(插入就是清空,删除就是释放),否则从中间切开做左右子树。

查询:因为这题的查询总是伴随着插入,因此我们可以在查询成功后直接插入,因此query函数可以设计成返回bool值。查询也是要先遗传,然后按照:左子树、左子树+右子树、右子树的顺序依次查看各区间剩余大小,如果合适的话就在那个区间插入。插入之后一定要记得由孩子更新自己,也就是上传。
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
#include <cstdio>
#include <algorithm>
struct segment_tree
{
  int lmax, rmax, sum;
  void operator()(const int x) { lmax = rmax = sum = x; }
  void operator()(const int l, const int r, const int m)
  { lmax = l, rmax = r, sum = m; }
} s[50001*4];
int n, m, len, st, ed;
void build(const int p, const int lef, const int rig)
{
  s[p](rig-lef+1);
  if (lef == rig) return;
  const int mid((lef+rig)>>1);
  build(p*2, lef, mid);
  build(p*2+1, mid+1, rig);
}
void update_child(const int p, const int lef, const int rig)
{
  if (p*2 >= 50001*4)
    return;
  if (s[p].sum == 0)
    s[p*2](0), s[p*2+1](0);
  else if (s[p].sum == rig-lef+1)
  {
    const int mid((lef+rig)>>1);
    s[p*2](mid-lef+1);
    s[p*2+1](rig-mid);
  }
}
void update_self(const int p, const int lef, const int rig)
{
  if (p*2 >= 50001*4)
  {
    s[p](0, 0, 0);
    return;
  }
  s[p](s[p*2].lmax, s[p*2+1].rmax, s[p*2].sum+s[p*2+1].sum);
  const int mid((lef+rig)>>1);
  if (s[p*2].lmax == mid-lef+1)
    s[p].lmax += s[p*2+1].lmax;
  if (s[p*2+1].rmax == rig-mid)
    s[p].rmax += s[p*2].rmax;
}
void remove(const int p, const int lef, const int rig, const int st, const int ed)
{
  update_child(p, lef, rig);
  if (lef == st && ed == rig)
    s[p](rig-lef+1);
  else
  {
    const int mid((lef+rig)>>1);
    if (st <= mid) remove(p*2, lef, mid, st, std::min(mid, ed));
    if (mid+1 <= ed) remove(p*2+1, mid+1, rig, std::max(st, mid+1), ed);
    update_self(p, lef, rig);
  }
}
void insert(const int p, const int lef, const int rig, const int st, const int ed)
{
  update_child(p, lef, rig);
  if (lef == st && ed == rig)
    s[p](0);
  else
  {
    const int mid((lef+rig)>>1);
    if (st <= mid) insert(p*2, lef, mid, st, std::min(mid, ed));
    if (mid+1 <= ed) insert(p*2+1, mid+1, rig, std::max(st, mid+1), ed);
    update_self(p, lef, rig);
  }
}
bool query(const int p, const int lef, const int rig)
{
  update_child(p, lef, rig);
  if (s[p].sum < len) return false;
  if (s[p].sum == rig-lef+1)
  {
    insert(p, lef, rig, lef, lef+len-1);
    update_self(p, lef, rig);
    printf("%dn", lef);
    return true;
  }
  const int mid((lef+rig)>>1);
//From Left:
  if (query(p*2, lef, mid))
  {
    update_self(p, lef, rig);
    return true;
  }
//Left + Right:
  if (s[p*2].rmax+s[p*2+1].lmax >= len)
  {
    const int rmax = s[p*2].rmax;
    printf("%dn", mid-rmax+1);
    insert(p*2, lef, mid, mid-rmax+1, mid);
    insert(p*2+1, mid+1, rig, mid+1, mid+len-rmax);
    update_self(p, lef, rig);
    return true;
  }
//From Right:
  if (query(p*2+1, mid+1, rig))
  {
    update_self(p, lef, rig);
    return true;
  }
  return false;
}
int main()
{
  scanf("%d%d", &n, &m);
  build(1, 1, n);
  for (int i = 0, op, a; i < m; ++i)
  {
    scanf("%d%d", &op, &len);
    if (op == 1)
    {
      st = 1, ed = n;
      if (!query(1, 1, n))
        printf("0n");
    }
    else
    {
      scanf("%d", &a);
      remove(1, 1, n, len, len+a-1);
    }
  }
}

Comments