[HNOI2004]宠物收养所 Bzoj1208

也是赤裸裸的Splay,和前面两题平衡树的一样,都是求最小插值。因为加了绝对值,所以往根左右两棵子树考虑。

因为在收养所里面的只能都是人或者都是宠物,所以在平衡树里面加一个TreeType表示树里面存的是什么,0就是宠物,1就是人,2就是空。如果进来的类型跟树的类型相同,那就插入节点,否则从树中找到一个差值最小的节点并删除。

删除操作很容易错,因为这个调了半天,整体上的思路就是把待删除节点提到根,然后合并左右子树。麻烦的就是一定要把跟待删除节点的联系全部切断,否则经过旋转平衡树会“很没有节操”,也就是不满足BST的性质,而且你会发现这个被删除的节点又出现了,而且有的节点六亲不认……

Splay要注意,每个操作之后都要旋转到根,这样效率差很多,一开始我把Max()和Min()中旋转的两句话给去掉了,结果TLE,加上去后明显快多了。

基本上这题还是被用来熟悉Splay,确实写了这三题对Splay就熟悉多了,哪天写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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

class SplayTree
{
public:
  struct Node
  {
    int Value;
    Node *Parent, *Child[2];
    Node(const int v = 0, Node* const p = NULL, Node* const l = NULL, Node* const r = NULL):
    Value(v), Parent(p) { Child[0] = l, Child[1] = r; }
  };
  static const int MAXLEN = 80000*2;
  int TreeType;
  Node *Root;
private:
  int node_size;
  Node g[MAXLEN];
  void rotate(Node* x, const int c)
  {
    Node* y = x->Parent;
    y->Child[c^1] = x->Child[c];
    if (x->Child[c] != NULL)
      x->Child[c]->Parent = y;
    x->Parent = y->Parent;
    if (y->Parent != NULL)
      y->Parent->Child[y == y->Parent->Child[1]] = x;
    y->Parent = x;
    x->Child[c] = y;
  }
  void splay(Node* x, Node* const goal = NULL)
  {
    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);
    }
    if (goal == NULL)
      Root = x;
  }
public:
  SplayTree(): Root(NULL), TreeType(2) { }
  Node* Insert(const int x, bool &exist)
  {
    exist = false;
    if (Root == NULL)
    {
      g[0] = Node(x);
      node_size = 1;
      Root = g;
      return g;
    }
    Node *t = Root, *p;
    while (t != NULL)
    {
      p = t;
      if (x == t->Value)
      {
        splay(t);
        exist = true;
        return t;
      }
      t = (x < t->Value ? t->Child[0] : t->Child[1]);
    }
    Node *node = g+node_size++;
    *node = Node(x, p);
    (x < p->Value ? p->Child[0] : p->Child[1]) = node;
    splay(node);
    return node;
  }
  Node* Max(Node* t, const bool rotate = true)
  {
    if (t == NULL) return NULL;
    Node* p;
    while (t)
    {
      p = t;
      t = t->Child[1];
    }
    if (rotate) splay(p);
    return p;
  }
  Node* Min(Node* t, const bool rotate = true)
  {
    if (t == NULL) return NULL;
    Node* p;
    while (t)
    {
      p = t;
      t = t->Child[0];
    }
    if (rotate) splay(p);
    return p;
  }
  Node* Max(const bool rotate = true) { return Max(Root, rotate); }
  Node* Min(const bool rotate = true) { return Min(Root, rotate); }
  Node* Join(Node* const sl, Node* const sr)
  {
    if (sl == NULL) return sr;
    if (sr == NULL) return sl;
    Node* p = Max(sl);
    p->Child[1] = sr;
    sr->Parent = p;
    splay(p);
    return p;
  }
  void Delete(Node* const x)
  {
    splay(x);
    Root = Join(x->Child[0], x->Child[1]);
    if (Root == NULL)
      TreeType = 2;
    else
    {
      Root->Parent = NULL;
      splay(Root);
    }
  }
};

int n;
long long ans;
bool exist;
SplayTree S;
int main()
{
  scanf("%d", &n);
  for (int a, b; n > 0; --n)
  {
    scanf("%d%d", &a, &b);
    if (S.TreeType != (a^1))
    {
      S.Insert(b, exist);
      S.TreeType = a;
    }
    else
    {
      SplayTree::Node *node = S.Insert(b, exist);
      if (!exist)
      {
        SplayTree::Node *l = S.Max(node->Child[0], false), *r = S.Min(node->Child[1]);
        if (l != NULL && (r == NULL || b-l->Value <= r->Value-b))
        {
          ans += b-l->Value;
          S.Delete(l);
        }
        else
        {
          ans += r->Value-b;
          S.Delete(r);
        }
      }
      S.Delete(node);
    }
  }
  printf("%dn", static_cast<int>(ans%1000000));
}

Comments