백준 3444번 Robotic Sort

문제 요약

길이가 N인 배열에 대해서 정렬을 진행한다. 정렬 과정은 다음과 같다.

$i$번째 과정에서 배열에서 $i$번째로 작은 원소를 $i$에 위치시키려고 한다. 이를 위해서 매 과정마다 $i$번째로 작은 원소를 $[i, N]$에서 찾고 그 위치를 $p$라고 하면 $[i,p]$를 뒤집어서 정렬을 수행한다.

여기서 숫자가 같더라도 원래 배열에서 더 앞에 있는 것을 작은 것으로 친다.

이 때, 각 과정마다 $i$번째로 작은 원소의 위치인 $p$를 모두 출력하라.

 

N은 최대 10만이다.

풀이

먼저 각 배열의 원소에 대해서 제시한 방법대로 정렬을 했을 때 해당 원소가 어디에 위치하는지를 계산한다. 이는 $O(NlogN)$에 가능하다.

위에서 계산한 값을 $pos_i$라고 하자. 그러면 각 과정에서의 $a_p = pos_i$인 $p$를 찾아야 한다.

 

일단 구간을 뒤집은 상태의 배열을 계속 다뤄야 한다. 이를 위해서 선형 배열을 스플레이 트리로 관리 하자.

원래 배열에서 $pos_i$로 바꾼 다음에 $pos_i = i$인 노드들의 포인터들을 미리 저장해놓읍시다.

 

그러면 각 과정에서 할 일은 $pos_i = i$인 노드를 스플레이 해줍니다. 그리고 $p$는 루트의 왼쪽 서브트리의 사이즈가 됩니다.

$p$를 구했으니 $[i,p]$를 뒤집습니다. 이 과정을 반복하면 답을 구할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
struct Node {
    Node *l, *r, *p;
    int sz, val;
    bool inv;
    // declare extra variables
    int idx;
    int m_idx, m_val;
    Node() : l(nullptr), r(nullptr), p(nullptr) {};
    Node(int _val, int _idx) {
        l = r = p = nullptr;
        sz = 1;
        val = _val;
        inv = false;
        // init extra variables
        idx = _idx;
        m_idx = idx;
        m_val = val;
    }
} *root, pool[100005], *pos[100005];

void reverse(Node *cur) {
    // reverse process
    swap(cur->l, cur->r);
}

// push into children(lazy, inv etc)
void push(Node *cur) {
    // pushing process
    if(cur->inv) {
        reverse(cur);
        if(cur->l) cur->l->inv = !cur->l->inv;
        if(cur->r) cur->r->inv = !cur->r->inv;
        cur->inv = false;
    }
}

// pull from children(size, sum etc)
void pull(Node *cur) {
    // pulling process
    cur->sz = 1;
    cur->m_idx = cur->idx;
    cur->m_val = cur->val;
    if(cur->l) {
        push(cur->l);
        cur->sz += cur->l->sz;
        if(cur->l->m_val < cur->m_val) {
            cur->m_val = cur->l->m_val;
            cur->m_idx = cur->l->m_idx;
        }
    }
    if(cur->r) {
        push(cur->r);
        cur->sz += cur->r->sz;
        if(cur->r->m_val < cur->m_val) {
            cur->m_val = cur->r->m_val;
            cur->m_idx = cur->r->m_idx;
        }
    }
}

void rotate(Node *cur) {
    Node* p = cur->p;
    if(!p) return ; // cur is root
    push(p);
    push(cur);
    Node *tmp;
    if(p->l == cur) {
        tmp = cur->r;
        p->l = cur->r;
        cur->r = p;
    }
    else {
        tmp = cur->l;
        p->r = cur->l;
        cur->l = p;
    }
    Node *pp = p->p;
    cur->p = pp;
    p->p = cur;
    if(tmp) tmp->p = p;
    if(cur->p) {
        if(pp->l == p) pp->l = cur;
        else if(pp->r == p) pp->r = cur;
    }
    else root = cur;
    pull(p);
    pull(cur);
}

void splay(Node *cur) {
    while(cur->p) {
        Node *p = cur->p;
        Node *pp = p->p;
        if(pp) {
            if((pp->l == p) == (p->l == cur)) rotate(p);
            else rotate(cur);
        }
        rotate(cur);
    }
}

// split tree first <= cur, second > cur
pair<Node*, Node*> split(Node *cur) {
    splay(cur);
    Node *left = cur;
    Node *right = cur->r;
    if(left) left->p = nullptr;
    if(right) right->p = nullptr;
    return {left, right};
}

Node* merge(Node *left, Node *right) {
    if(left == nullptr) return right;
    if(right == nullptr) return left;
    Node *p = left;
    while(p->r) p = p->r;
    push(p);
    splay(p);
    p->r = right;
    right->p = p;
    pull(p);
    return p;
}

Node* kth(Node *cur, int k) {
    Node *p = cur;
    push(p);
    while(1) {
        while(p->l && p->l->sz > k) {
            p = p->l;
            push(p);
        }
        if(p->l) k -= p->l->sz;
        if(!k) break;
        else --k;
        p = p->r;
        push(p);
    }
    splay(p);
    return p;
}

// p->r->l represents [l,r]
Node* interval(Node *cur, int l, int r) {
    Node *p = kth(cur, l-1);
    Node *right = p->r;
    right->p = nullptr;
    right = kth(right, r-l+1);
    right->p = p;
    p->r = right;
    root = p;
    pull(p);
    return p;
}

int N;
int a[100005];

Node* init_node(Node *cur, int val, int idx) {
    cur->l = cur->r = cur->p = nullptr;
    cur->val = cur->m_val = val;
    cur->idx = cur->m_idx = idx;
    cur->inv = false;
    cur->sz = 1;
    return cur;
}

void init_tree() {
    int node_idx = 0;
    Node *p = root = init_node(pool + node_idx++, INF, 0);
    for(int i=1;i<=N;++i) {
        pos[a[i]] = p->r = init_node(pool + node_idx++, a[i], i);
        p->r->p = p;
        p = p->r;
    }
    p->r = init_node(pool + node_idx++, INF, N+1);
    p->r->p = p;
    p = p->r;
    while(p) {
        pull(p);
        p = p->p;
    }
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    while(1) {
        cin >> N;
        if(!N) break;
        vector<int> v;
        for(int i=1;i<=N;++i) {
            cin >> a[i];
            v.push_back(a[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        vector<vector<int>> tmp(v.size());
        for(int i=1;i<=N;++i) {
            a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
            tmp[a[i]].push_back(i);
        }
        int idx = 0;
        for(int i=0;i<v.size();++i) {
            for(int j:tmp[i]) a[j] = ++idx;
        }
        init_tree();
        for(int i=1;i<=N;++i) {
            splay(pos[i]);
            int ans = root->l->sz;
            cout << ans << " \n"[i==N];
            Node *p = interval(root, i, ans);
            p = p->r->l;
            p->inv = !p->inv;
            push(p);
        }
    }
    return 0;
}