一天一道算法题——hdu1890 Robotic Sort（splay树）

  1 #include<iostream>
  2 #include<algorithm>
  3 #define maxn 100010
  4 using namespace std;
  5 
  6 int n, root,len[maxn], pre[maxn], child[maxn][2],rev[maxn];//rev是标记——表示是否翻转过，如果每次都翻转那么会超时
  7 struct node {
  8     int val, id;
  9     bool const operator <(node &a)const{
 10         if (val == a.val)return id < a.id;
 11         return val < a.val;
 12     }
 13 }nodes[maxn];
 14 
 15 void pushUp(int x) {//计算长度，不知道为什么要叫pushUp，明明在treap和bst里还叫update的( ?◇?)？
 16     len[x] = len[child[x][0]] + len[child[x][1]]+1;
 17 }
 18 void update_rev(int x) {
 19     if (!x)return;
 20     swap(child[x][0], child[x][1]);
 21     rev[x] ^= 1;
 22 }
 23 void push_down(int x) {
 24     if (rev[x]) {//如果这个节点翻转过，那么把它的孩子节点也需要翻转。
 25         update_rev(child[x][0]);
 26         update_rev(child[x][1]);
 27         rev[x] = 0;
 28     }
 29 }
 30 void rotate(int x, int d) {//d为0左旋，1右旋
 31     int y = pre[x];
 32     push_down(y);
 33     push_down(x);
 34     //以下就是把父节点和旋转方向的孩子交换
 35     child[y][!d] = child[x][d];
 36     pre[child[x][d]] = y;
 37     if (pre[y])//如果父节点有父节点，别忘了把自己换上去
 38         child[pre[y]][child[pre[y]][1] == y] = x;
 39     pre[x] = pre[y];
 40     child[x][d] = y;
 41     pre[y] = x;
 42     pushUp(y);
 43 }
 44 void splay(int r, int goal) {//r是要旋转的节点，goal是要旋转到的地方的父亲
 45     push_down(r);
 46     while (pre[r] != goal) {
 47         if (pre[pre[r]] == goal) {
 48             push_down(pre[r]);
 49             push_down(r);
 50             rotate(r, child[pre[r]][0] == r);
 51         }
 52         else {
 53             push_down(pre[pre[r]]);
 54             push_down(pre[r]);
 55             push_down(r);
 56             int y = pre[r];
 57             int d = child[pre[y]][0] == y;
 58             if (child[y][d] == r)//不共线
 59                 rotate(r, !d);
 60             else
 61                 rotate(y, d);
 62             rotate(r, d);
 63         }
 64     }
 65     pushUp(r);
 66     if (goal == 0)
 67         root = r;
 68 }
 69 void newNode(int &x, int f, int v) {//int &x会直接把传入的x给修改了，这样就不需要重复再给father的左右孩子赋值了
 70     x = v;
 71     len[x] = 1;
 72     pre[x] = f;
 73     rev[x] = 0;
 74     child[x][0] = child[x][1] = 0;
 75 }
 76 void buildTree(int &x, int l, int r, int f) {
 77     //二分保证深度最小
 78     if (l > r)return;
 79     int mid = (l + r) >> 1;
 80     newNode(x,f,mid);
 81     buildTree(child[x][0], l, mid - 1,x);
 82     buildTree(child[x][1], mid + 1, r, x);
 83     pushUp(x);
 84 }
 85 void init() {
 86     root = 0;
 87     child[root][0] = child[root][1] = pre[root] = len[root] = 0;
 88     buildTree(root, 1, n, 0);//以【1，n】为序列建造一棵splaytree
 89 }
 90 void remove(int &x) {
 91     int r = child[x][0];
 92     if (!r) {//没有左孩子
 93         x = child[x][1];
 94         pre[root] = 0;
 95     }
 96     else {
 97         push_down(r);
 98         while(child[r][1]){
 99             r = child[r][1];
100             push_down(r);
101         }
102         splay(r, root);
103         child[r][1] = child[x][1];
104         pre[child[x][1]] = r;
105         x = r;
106         pre[x] = 0;
107         pushUp(x);
108     }
109 }
110 int main() {
111     while (cin >> n && n) {
112         init();
113         for (int i = 1; i <= n; i++) {
114             scanf_s("%d", &nodes[i].val); nodes[i].id = i;//记住位置
115         }
116         sort(nodes + 1, nodes + n + 1);
117         for (int i = 1; i < n; i++) {
118             splay(nodes[i].id, 0);//将第i小的节点splay到根节点（父节点为0）
119             update_rev(child[root][0]);
120             printf("%d ", len[child[root][0]]+i);
121             remove(root);//删除根节点
122         }
123         printf_s("%d\n", n);//易得
124     }
125     return 0;
126 }