[HDU2871]Memory Control

题目大意

给定拥有n个单元的内存,有以下操作:

  • Reset 清空内存,输出 Reset
  • New x 在尽量左端插入一个长度为x的块,输出 New at ...Reject New
  • Free x 清空单元x所在块的整个块,输出 Free from ... to ...Reject Free
  • Get x 找到第x个内存块的起始地址,输出 Get at ...Reject Get

题解

据网上说是线段树,但是我是在平衡树练习题里面看到的,所以就打 Splay 练习一下。

平衡树表示

因为有询问第x个块的操作,所以我们把一整个块 [L, R] 作为平衡树的一个节点。注意到因为每个内存单元只会被一个块包含,所以完全可以当作只有 L 是平衡树的 key 。因为会需要查询第k大,所以顺便记下以每个平衡树节点为根的子树大小 size

New

如何找到最左边能容得下x的空间?每个节点可以维护两个值:当前节点和其前驱的距离差 dist 以及以当前平衡树节点为根的子树中最大的连续空间大小 maxspare

接下来就非常愉悦了,对于 New x 从根开始遍历平衡树。如果当前节点的 maxspare >= x 那么就考虑:向左走( left->maxspare >= x )或者取自己( dist >= x )或者向右走。

最终我们找到了一个节点 node ,满足这个节点和它前驱之间的空隙能够容得下新建的块。现在我们要进行插入,那就先把 node 旋到根,然后找到 node 的前驱,在前驱的右子树新建节点。新建节点的同时,需要注意更新父亲节点的 size maxspare dist ### Free

首先当然是找到包含x的块,这个就是基本的二叉排序树做的事情。接下来,删掉,维护父亲节点信息。

Get

就是找第k大的数。

实现

因为这道题几乎是我第一题有维护额外信息的Splay,所以打得很纠结,特别记下来具体的实现。

删除节点

一开始用的方法是论文里面的合并子树,发现很麻烦。经ygy神牛指点,采取比较科学的方法:

先找到 node 的前驱 prev 和后继 succ ,然后把 succ 旋转到根,把 prev 旋转到根的左边。现在, node 就以叶子节点的形式,非常愉悦地出现在了 prev 的右边。现在要做的只是剪掉指针即可。

维护父亲节点信息

新建时找到的节点是中间的节点,如果直接插入的话,父亲节点的 maxsparesize 都会乱掉。因此,应该在新增的时候,扣除其后继(也就是 Root )的 dist ,并且从新增节点开始,一路向上更新每个父节点的信息。

删除时也一样。

一些错误

写的时候犯了一些错误,弄得我调了好久。

  • 忘记扣掉新增节点后继的 dist
  • 删除节点的时候,给后继节点加上的 dist 少掉了删除节点的 dist (也就是应该是 succ->dist += (node->R - node->L + 1) + node->dist
  • Reset忘记插入前后哨兵

代码

我打splay一向很长。

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 50003;
struct Block
{
  int lef, rig;
  Block() { }
  Block(const int l, const int r): lef(l), rig(r) { }
};
inline bool operator<(const Block& lhs, const Block& rhs) { return lhs.lef < rhs.lef; }
struct Node
{
  Block value;
  int dist, maxspare, size;
  Node *parent, *child[2];
  Node() { }
  Node(const Block& v, const int d): value(v), dist(d), maxspare(d), size(1) { }
};
Node _memory[MAXN], *EMPTY = _memory;
int _memory_size = 1;
struct SplayTree
{
  Node *Root;
private:
  void update(Node* const x)
  {
    x->maxspare = std::max(x->dist, std::max(x->child[0]->maxspare, x->child[1]->maxspare));
    x->size = x->child[0]->size + 1 + x->child[1]->size;
  }
  void rotate(Node* const x, const int c)
  {
    Node* const y = x->parent;
    y->child[c^1] = x->child[c];
    if (x->child[c] != EMPTY)
      x->child[c]->parent = y;
    x->parent = y->parent;
    if (x->parent != EMPTY)
      x->parent->child[y == y->parent->child[1]] = x;
    y->parent = x;
    x->child[c] = y;
    update(y);
  }
  void splay(Node* const x, Node* const goal = EMPTY)
  {
    for (Node *y; (y = x->parent) != goal; )
    {
      if (y->parent == goal)
      {
        rotate(x, x == y->child[0]);
        break;
      }
      const int c = y == y->parent->child[0];
      if (x == y->child[c])
        rotate(x, c^1), rotate(x, c);
      else
        rotate(y, c), rotate(x, c);
    }
    update(x);
    if (goal == EMPTY)
      Root = x;
  }
//--------Special Operator:
  void update_parent(Node* x, const int size)
  {
    Root->dist -= size;
    for (; x != EMPTY; x = x->parent)
      update(x);
  }
public:
  SplayTree(): Root(EMPTY) { }
  Node* GetPrev(Node* x, const bool rotate = true)
  {
    if (rotate) splay(x);
    for (x = x->child[0]; x != EMPTY && x->child[1] != EMPTY; x = x->child[1]);
    return x;
  }
  Node* GetSucc(Node* x, const bool rotate = true)
  {
    if (rotate) splay(x);
    for (x = x->child[1]; x != EMPTY && x->child[0] != EMPTY; x = x->child[0]);
    return x;
  }
  void Erase(Node* x)
  {
    splay(x);
    Node* const succ = GetSucc(x, false);
    Node* const prev = GetPrev(x, false);
    splay(succ);
    splay(prev, succ);
    prev->child[1] = EMPTY;
    --succ->size, --prev->size;
  }
//--------Special Operator:
  Node* Insert(const Block& value, const int dist)
  {
    Node* const node = _memory+(_memory_size++);
    node->value = value, node->dist = dist, node->size = 1;
    node->child[0] = node->child[1] = node->parent = EMPTY;
    if (Root == EMPTY)
      return Root = node;
    Node *p;
    for (Node* x = Root; x != EMPTY; )
    {
      p = x;
      x = x->child[x->value < value];
    }
    node->parent = p;
    p->child[p->value < value] = node;
    splay(node);
    return node;
  }
  Node* MemoryNew(const int size)
  {
    Node* p = EMPTY;
    for (Node* x = Root; x != EMPTY && x->maxspare >= size; )
      if (x->child[0]->maxspare >= size)
        x = x->child[0];
      else if (x->dist >= size)
      {
        p = x;
        break;
      }
      else
        x = x->child[1];
    if (p == EMPTY)
      return EMPTY;
    splay(p);
    Node* const prev = GetPrev(p, false);
    Node* const node = _memory+(_memory_size++);
    *node = Node(Block(prev->value.rig+1, prev->value.rig+size), 0);
    node->size = 1, node->parent = prev;
    node->child[0] = node->child[1] = EMPTY;
    prev->child[1] = node;
    update_parent(node, size);
    splay(node);
    return node;
  }
  Node* MemoryFree(const int pos)
  {
    Node* p = EMPTY;
    for (Node* x = Root; x != EMPTY; )
    {
      const int lef = x->value.lef, rig = x->value.rig;
      if (pos < lef)
        x = x->child[0];
      else if (pos <= rig)
      {
        p = x;
        break;
      }
      else
        x = x->child[1];
    }
    if (p == EMPTY)
      return EMPTY;
    Erase(p);
    update(Root->child[0]);
    Root->dist += p->value.rig-p->value.lef+1 + p->dist;
    update(Root);
    return p;
  }
  Node* MemoryGet(int k)
  {
    ++k;
    Node *x = Root, *p = EMPTY;
    while (true)
    {
      const int lef = x->child[0]->size;
      if (lef+1 == k)
      {
        p = x;
        break;
      }
      if (k <= lef)
        x = x->child[0];
      else
      {
        k -= lef+1;
        x = x->child[1];
      }
    }
    if (p == _memory+2)
      return EMPTY;
    return p;
  }
};
void MemoryReset(SplayTree& s, const int n = 0)
{
  s.Root = EMPTY;
  _memory_size = 1;
  if (n)
  {
    s.Insert(Block(0, 0), 0);
    s.Insert(Block(n+1, n+1), n);
  }
}

SplayTree s;
int n, m;
int main()
{
  EMPTY->parent = EMPTY->child[0] = EMPTY->child[1] = EMPTY;

  while (scanf("%d%d", &n, &m) != EOF)
  {
    MemoryReset(s, n);
    for (int i = 0, x; i < m; ++i)
    {
      static char buf[10];
      scanf("\n%s", buf);
      if (buf[0] == 'N')
      {
        scanf("%d", &x);
        Node* const node = s.MemoryNew(x);
        if (node == EMPTY)
          printf("Reject New\n");
        else
          printf("New at %d\n", node->value.lef);
      }
      else if (buf[0] == 'F')
      {
        scanf("%d", &x);
        Node* const node = s.MemoryFree(x);
        if (node == EMPTY)
          printf("Reject Free\n");
        else
          printf("Free from %d to %d\n", node->value.lef, node->value.rig);
      }
      else if (buf[0] == 'G')
      {
        scanf("%d", &x);
        Node* const node = s.MemoryGet(x);
        if (node == EMPTY)
          printf("Reject Get\n");
        else
          printf("Get at %d\n", node->value.lef);
      }
      else
      {
        MemoryReset(s, n);
        printf("Reset Now\n");
      }
    }
    printf("\n");
  }
}

Comments