ZOJ 2985 Robotic Sort

事实证明这不是一道太难的题，只要能把伸展树(Splay Tree)写好，并且能在上面做一些拓展的操作。

之前想法比较简单，想建个笛卡尔树(Cartesian Tree)，由笛卡尔树的性质来保证整棵树的有序性(左儿子的下标小，右儿子的下标大，父亲节点的关键字大于儿子节点的关键字)。后来越想越复杂，因为reverse操作在笛卡尔树上面做起来很麻烦，时间效率肯定暴低，所以放弃了使用笛卡尔树，还是老老实实写伸展树。

伸展树的问题在于如何在整棵树上很快地找到最小值，答案是预处理。先把序列读入进来，然后排序预处理一下，复杂度为O(nlogn)，然后用伸展树进行操作。而伸展树的splay操作复杂度也是O(nlogn)，reverse操作可以由一个简单的标记解决，认真分析一下，发现问题可以得到完美的解决。

几个要点需要注意：

1.预处理

想到用伸展树之后还是卡了一会儿，没想到预处理，这个比较失败。

2.reverse操作

reverse操作可以直接标记在一个节点上，表示以这个节点为根的子树需要reverse。而对一棵树reverse就是交换左右儿子，然后把自身的标记抹掉，并传递给儿子节点。注意在将一个节点splay到根节点的时候，给它的左儿子打上reverse标记的时候不要直接赋值，而是要用异或操作，因为它的左儿子可能已经有了一个reverse标记。

3.rotate操作

在进行rotate操作的时候，需要保证需要旋转的节点reverse标记已经被抹除，否则会出错。而相关节点的儿子节点，由于他们之间的相对关系以及各个子树的结构并不会受到rotate操作的影响，所以只需要将reverse标记传到子树上就可以了。因为多次reverse操作效果可能一样，所以用标记就快多啦。

差不多就是这些，先写到这儿吧。写伸展树需要细心。

ZOJ 2985 Robotic Sort

  1 #include < stdio.h >
  2 #include < stdlib.h >
  3
  4 #define DEBUG 0
  5
  6 const int MaxN = 100010 ;
  7
  8 struct Node {
  9      int size, reverse, remove;
10      struct Node * l, * r, * f;
11     Node()
12         :size( 0 ), reverse( 0 ), remove( 0 ), l(NULL), r(NULL), f(NULL)
13     {}
14 }node[MaxN];
15
16 typedef struct Node * NP;
17
18 struct SplayTree {
19     NP root;
20      void calc_size(NP p) {
21         p -> size = 0 ;
22          if ( ! p -> remove) p -> size ++ ;
23          if (p -> l) p -> size += p -> l -> size;
24          if (p -> r) p -> size += p -> r -> size;
25     }
26      void clean_reverse(NP p) {
27          if (p -> reverse == 0 )
28              return ;
29         p -> reverse = 0 ;
30          if (p -> l) p -> l -> reverse ^= 1 ;
31          if (p -> r) p -> r -> reverse ^= 1 ;
32         NP t;
33         t = p -> l; p -> l = p -> r; p -> r = t;
34     }
35      void rot_left(NP p) {
36         NP y = p -> r;
37         p -> r = y -> l;
38          if (y -> l) y -> l -> f = p;
39         y -> l = p;
40         y -> f = p -> f;
41          if (p -> f) {
42              if (p == p -> f -> l)
43                 p -> f -> l = y;
44              else if (p == p -> f -> r)
45                 p -> f -> r = y;
46         }
47          else {
48             root = y;
49         }
50         p -> f = y;
51         calc_size(p);
52         calc_size(y);
53     }
54      void rot_right(NP p) {
55         NP y = p -> l;
56         p -> l = y -> r;
57          if (y -> r) y -> r -> f = p;
58         y -> r = p;
59         y -> f = p -> f;
60          if (p -> f) {
61              if (p == p -> f -> l)
62                 p -> f -> l = y;
63              else if (p == p -> f -> r)
64                 p -> f -> r = y;
65         }
66          else {
67             root = y;
68         }
69         p -> f = y;
70         calc_size(p);
71         calc_size(y);
72     }
73      void splay( const NP & p) {
74          if (p == root)
75              return ;
76          else {
77             NP fa = p -> f;
78              if (fa == root) {
79                 clean_reverse(fa);
80                 clean_reverse(p);
81                  if (p == fa -> l)
82                     rot_right(root);
83                  else
84                     rot_left(root);
85                  return ;
86             }
87              else {
88                 NP gf = fa -> f;
89                 clean_reverse(gf);
90                 clean_reverse(fa);
91                 clean_reverse(p);
92                  if (fa == gf -> l && p == fa -> l) {
93                     rot_right(gf);
94                     rot_right(fa);
95                 }
96                  else if (fa == gf -> r && p == fa -> r) {
97                     rot_left(gf);
98                     rot_left(fa);
99                 }
100                  else if (fa == gf -> l && p == fa -> r) {
101                     rot_left(fa);
102                     rot_right(gf);
103                 }
104                  else if (fa == gf -> r && p == fa -> l) {
105                     rot_right(fa);
106                     rot_left(gf);
107                 }
108             }
109         }
110         splay(p);
111     }
112 }tree;
113
114 int N, mtp;
115 int num[MaxN], buf[MaxN], idxn[MaxN];
116 NP idx[MaxN];
117
118 int cmp( const void * a, const void * b) {
119      int va = * ( int * )a;
120      int vb = * ( int * )b;
121      if (num[va] != num[vb])
122          return num[va] - num[vb];
123      return va - vb;
124 }
125
126 int do_reverse(NP t) {
127     tree.splay(t);
128     t -> remove = 1 ;
129      if (t -> l == NULL) {
130          return 0 ;
131     }
132     t -> l -> reverse ^= 1 ;
133      return t -> l -> size;
134 }
135
136 void work() {
137      for ( int i = 0 ; i < N; ++ i) {
138         buf[i] = i;
139     }
140     qsort(buf, N, sizeof ( int ), cmp);
141 #if DEBUG
142      for ( int i = 0 ; i < N; ++ i) {
143         printf( " %d%c " , num[i], i + 1 == N ? ' \n ' : ' ' );
144     }
145      for ( int i = 0 ; i < N; ++ i) {
146         printf( " %d%c " , buf[i], i + 1 == N ? ' \n ' : ' ' );
147     }
148 #endif
149     mtp = 0 ;
150      for ( int i = 0 ; i < N; ++ i) {
151         node[i] = Node();
152         node[i].size = i + 1 ;
153          if (i)
154             node[i].l = node + i - 1 ;
155          if (i + 1 < N)
156             node[i].f = node + i + 1 ;
157     }
158     tree.root = node + N - 1 ;
159 #if DEBUG
160     printf( " ans = " );
161 #endif
162      for ( int i = 0 ; i < N; ++ i) {
163         printf( " %d%c " , do_reverse(node + buf[i]) + i + 1 , i + 1 == N ? ' \n ' : ' ' );
164     }
165 }
166
167 int main() {
168 #if DEBUG
169     freopen( " test.in " , " r " , stdin);
170     freopen( " test.out " , " w " , stdout);
171 #endif
172      while (scanf( " %d " , & N) && N) {
173          for ( int i = 0 ; i < N; ++ i) {
174             scanf( " %d " , num + i);
175         }
176         work();
177     }
178      return 0 ;
179 }
180

转载于:https://www.cnblogs.com/destinydesigner/archive/2010/11/25/1888145.html