UVa 1402 - Robotic Sort | Sengxian's Blog

UVa 1402 - Robotic Sort

#数据结构 #伸展树

Published on 2016-01-13

描述

给定一个长度为 $n(n\le100000)$ 的序列，每一次将第 $i$ 小元素（如果值相同，则规定初始序列中靠前的为更小）放置到位置 $i$ ，这一操作只能通过翻转区间 $[i, P_{i}]$ 来解决。
请你输出 $n$ 个值，分别为对应的 $P_{i}$ 的值。注意，如果 $i = P_{i}$ ，也应该输出。

样例输入

6 
3 4 5 1 6 2 
4 
3 3 2 1 
0

样例输出

4 6 4 5 6 6 
4 2 4 4

附加输入

10
5 18 19 12 7 12 0 2 11 9
1
4
19
5 17 8 10 13 18 10 5 3 15 2 19 12 10 2 14 18 0 6
12
15 13 7 14 15 7 12 15 4 10 6 3
15
18 7 5 6 5 5 10 9 2 4 9 10 7 13 19
5
3 4 1 1 3
6
8 0 6 2 6 16
7
17 5 12 1 3 9 13
1
8
10
15 19 17 19 17 18 2 12 0 10
10
5 1 14 6 7 12 15 17 5 11
0

附加输出

7 8 3 7 10 6 10 10 9 10
1
18 8 6 10 18 12 19 15 16 19 14 15 14 17 19 18 17 18 19
12 4 4 10 7 10 8 11 10 12 12 12
9 10 5 7 8 8 8 13 11 10 12 12 14 14 15
3 4 3 5 5
2 4 3 5 5 6
4 5 4 6 5 7 7
1
9 3 10 10 10 7 9 10 9 10
2 2 9 8 5 10 10 10 10 10

分析

伸展树的裸题啦，每个节点维护区间的最小值，以及最小值在序列的第几个，每次查询翻转即可。
伸展树有一个很重要的思想就是，进行任何操作，不管是打标，还是旋转，都必须保证操作的那个节点的信息被及时更新。如果要反转区间 $[l, r)$ ，那么原来最小值在序列的第 $k$ 个，现在就在序列的第 $r - l + 1 - k$ 个，只要翻转，就必须更新，否则就是错误的。训练指南的第一道例题的翻转操作是延迟作用的，但那个题每个节点只维护区间大小，与翻不翻转无关，所以可行，不要被迷惑了。
下面的代码在头尾加了两个虚拟节点，如果对伸展树不熟悉，强烈建议学习这个版本，最简洁有力。这种高级数据结构一般出一点小错就容易 RE，所以大家写的时候注意点（别问我怎么知道的。。。

分析

//  Created by Sengxian on 1/13/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1402 伸展树
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int INF = 0x3f3f3f3f, maxn = 100000 + 3;
typedef pair<int, int> type;
const type vINF = type(INF, INF);
struct Node *null;
struct Node {
    Node* ch[2];
    type val, minVal;
    int minPos, s, reversed;
    Node(type x = vINF): val(x), minVal(x), minPos(INF), s(0), reversed(0) {ch[0] = ch[1] = null;}
    void maintain() {
        s = ch[0] -> s + ch[1] -> s + 1;
        minVal = min(min(ch[0] -> minVal, ch[1] -> minVal), val);
        if(minVal == ch[0] -> minVal) minPos = ch[0] -> minPos;
        else if(minVal == ch[1] -> minVal) minPos = ch[0] -> s + 1 + ch[1] -> minPos;
        else minPos = ch[0] -> s + 1;
    }
    int cmp(int x) {return x <= ch[0] -> s ? 0 : (x == ch[0] -> s + 1 ? -1 : 1);}
    void reverse() {
        reversed ^= 1;
        swap(ch[0], ch[1]);
        minPos = s + 1 - minPos; //立刻维护！
    }
    void pushdown() {
        if(reversed) {
            reversed = false;
            if(ch[0] != null) ch[0] -> reverse();
            if(ch[1] != null) ch[1] -> reverse();
        }
    }
}*root;
void init_null() {
    null = new Node();
    null -> s = 0;
}
void rotate(Node* &o, int d) {
    Node* k = o -> ch[d ^ 1]; o -> ch[d ^ 1] = k -> ch[d]; k -> ch[d] = o;
    o -> maintain(); k -> maintain(); o = k;
}
void splay(Node* &o, int k) {
    o -> pushdown();
    int d = o -> cmp(k);
    if(d == 1) k -= o -> ch[0] -> s + 1;
    if(d != -1) {
        Node* p = o -> ch[d];
        p -> pushdown();
        int d2 = p -> cmp(k);
        if(d2 == 1) k -= p -> ch[0] -> s + 1;
        if(d2 != -1) {
            splay(p -> ch[d2], k);
            if(d == d2) rotate(o, d ^ 1); else rotate(o -> ch[d], d);
        }
        rotate(o, d ^ 1);
    }
}
int n;
type a[maxn];
void maintain() {
    root -> ch[1] -> maintain();
    root -> maintain();
}
Node* build(int l, int r) {
    if(r <= l) return null;
    int mid = (l + r) / 2;
    Node* o = new Node(a[mid]);
    o -> ch[0] = build(l, mid); o -> ch[1] = build(mid + 1, r);
    o -> maintain();
    return o;
}
void build() {
    root = new Node();
    root -> ch[1] = new Node();
    root -> ch[1] -> ch[0] = build(0, n);
    maintain(); //任何对区间的修改，都需要进行maintain
}
//返回区间 [l, r)
Node* &range(int l, int r) {
    splay(root, l); //有虚拟节点，所以不是 l - 1，也避免了 l - 1 = 0
    splay(root -> ch[1], r - l + 1);
    return root -> ch[1] -> ch[0];
}

void print(Node* o, int reversed) {
    if(o == null) return;
    if(!reversed) { print(o->ch[0], o->reversed); printf("%d ", o->val.first); print(o->ch[1], o->reversed); }
    else { print(o->ch[1], o->reversed); printf("%d ", o->val.first); print(o->ch[0], o->reversed); }
}

void print() {
    print(root, 0);
    printf("\n");
}

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return n;
}
int main() {
    init_null();
    while(n = ReadInt(), n) {
        for(int i = 0; i < n; ++i) a[i] = type(ReadInt(), i);
        build();
        int pos = 1;
        while(pos <= n) {
            Node* &o = range(pos, n + 1);
            int minPos = o -> minPos;
            Node* &k = range(pos, pos + minPos);
            k -> reverse();
            maintain(); //注意要 maintain，因为修改了区间！
            printf("%d%c", pos + minPos - 1, pos == n ? '\n' : ' ');
            pos++;
        }
    }
}

UVa 261 - The Window Property POJ、BZOJ 题目排序