백준3444 Robotic Sort

작성일 | In

문제 링크

  • http://icpc.me/3444

문제 출처

  • 2007 CERC S번

사용 알고리즘

  • Splay Tree

시간복잡도

  • $O(N \log N)$

풀이

구간을 flip하는 연산과 임의의 수가 몇 번째에 있는지 찾는 연산이 필요합니다. Splay Tree는 이런 연산을 amortized $O(\log N)$에 할 수 있습니다.

구간을 뒤집는 것은 단순히 Splay Tree에서 Lazy Propagation을 해주면 됩니다.
임의의 수가 몇 번째에 있는지 찾는 것이 어려울 수 있는데, 처음에 Splay Tree를 만들 때 각 정점의 포인터를 미리 저장해놓고, 원하는 정점을 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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n;
int a[101010];
vector<int> comp;
vector<int> g[101010];

struct SplayTree{
    struct Node{
        Node *l, *r, *p;
        int sz, v, flip, dummy;
        Node() : Node(0, nullptr) {}
        Node(int v) : Node(v, nullptr) {}
        Node(int v, Node *p) : v(v), p(p) { l = r = nullptr; sz = flip = dummy = 0; }
        ~Node(){
            if(l) delete l;
            if(r) delete r;
        }
    };

    Node *root, *ptr[101010];
    SplayTree() : root(nullptr) { memset(ptr, 0, sizeof ptr); }
    ~SplayTree(){ if(root) delete root; }
    void init(){
        if(root) delete root;
        ptr[0] = root = new Node(-1e9); //left dummy node
        auto now = root;
        for(int i=1; i<=n; i++){
            ptr[a[i]] =  now->r = new Node(a[i], now);
            now = now->r;
        }
        ptr[n+1] = now->r = new Node(1e9, now); //right dummy node
        root->dummy = now->r->dummy = 1;
        for(int i=n+1; ~i; i--) update(ptr[i]);
    }

    // basic operation
    void rotate(Node *x){
        auto p = x->p;
        Node *y;
        push(p); push(x);
        if(x == p->l) p->l = y = x->r, x->r = p;
        else p->r = y = x->l, x->l = p;
        x->p = p->p; p->p = x;
        if(y) y->p = p;
        if(x->p){
            if(p == x->p->l) x->p->l = x;
            else x->p->r = x;
        }
        else root = x;
        update(p); update(x);
    }
    void splay(Node *x, Node *g = nullptr){
        Node *y;
        while(x->p != g){
            Node *p = x->p;
            if(p->p == g){ rotate(x); break; }
            auto pp = p->p;
            if((p->l == x) == (pp->l == p)) rotate(p);
            else rotate(x);
            rotate(x);
        }
        if(!g) root = x;
    }
    void update(Node *x){
        x->sz = 1;
        if(x->l) x->sz += x->l->sz;
        if(x->r) x->sz += x->r->sz;
    }
    void push(Node *x){
        if(!x->flip) return;
        swap(x->l, x->r);
        if(x->l) x->l->flip = !x->l->flip;
        if(x->r) x->r->flip = !x->r->flip;
        x->flip = 0;
    }

    // additional operation
    Node* gather(int s, int e){ //gather [s, e]
        kth(e+1);
        auto tmp = root;
        kth(s-1);
        splay(tmp, root);
        return root->r->l;
    }
    void flip(int s, int e){
        Node *x = gather(s, e);
        x->flip = !x->flip;
    }
    int getidx(int k){
        splay(ptr[k]);
        return root->l->sz;
    }

    void kth(int k){ //1-based
        auto now = root;
        push(now);
        while(1){
            while(now->l && now->l->sz > k) now = now->l, push(now);
            if(now->l) k -= now->l->sz;
            if(!k) break; k--;
            now = now->r;
            push(now);
        }
        splay(now);
    }
};

void input(){
    comp.clear(); comp.reserve(n);
    for(int i=1; i<=n; i++) cin >> a[i], comp.push_back(a[i]);
    compress(comp);
    for(int i=0; i<comp.size(); i++) g[i].clear();
    for(int i=1; i<=n; i++){
        a[i] = lower_bound(all(comp), a[i]) - comp.begin();
        g[a[i]].push_back(i);
    }
    int pv = 0;
    for(int i=0; i<comp.size(); i++){
        for(auto j : g[i]) a[j] = ++pv;
    }
}

void solve(){
    input();
    SplayTree tree;
    tree.init();
    for(int i=1; i<=n; i++){
        int t = tree.getidx(i);
        cout << t << " ";
        tree.flip(i, t);
    }
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    while(1){
        cin >> n; if(!n) return 0;
        solve();
    }
}