백준 16586번 Linked List

문제 요약

처음에 $a_i = i$인 배열이 주어진다. 다음과 같은 쿼리를 처리해라.

a, b가 주어지면 a를 b의 오른쪽으로 옮기는 것이다. 그리고 a의 이동거리를 출력한다.

모든 쿼리를 처리한 다음에는 전체 배열을 출력해야 한다.

 

배열의 길이랑 쿼리 수는 최대 10만개다.

풀이

쿼리를 이렇게 생각할 수 있다. a, b가 주어지면 먼저 $a$의 위치를 찾고 $a$를 배열에서 지운다.

그 뒤에 $b$의 위치를 찾고 그 뒤에 $a$를 넣어준다.

이동거리는 빼기 전 $a$위치랑 넣은 후에 $a$위치를 알면 바로 계산할 수 있다.

 

문제는 이걸 효율적으로 관리할 수 있는 방법이 무엇이냐인데 스플레이트리를 사용하면 빠르게 관리할 수 있다.

배열을 트리로 만들어 줄 때, $i$가 적혀있는 노드의 포인터를 저장해놓는다. 쿼리가 들어오면 $a$가 적혀있는 노드를 스플레이 해줘서 $a$의 인덱스를 확인하고 $a$를 트리에서 뺀다.

 

그리고 $b$가 적힌 노드를 스플레이한 다음에 $b$ 다음에 오도록 삽입한다. 이동거리를 다시 $a$를 스플레이 해주면 계산할 수 있다.

이걸로 문제를 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    Node *l, *r, *p;
    int sz, val;
    bool inv;
    // declare extra variables
    bool dummy;
    Node() : l(nullptr), r(nullptr), p(nullptr) {};
    Node(int _val) {
        l = r = p = nullptr;
        sz = 1;
        val = _val;
        inv = false;
        // init extra variables
        dummy = false;
    }
} *root, *pos[100005];

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

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;
    }
}

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, Q;
int a[100005];

void init_tree() {
    Node *p = root = new Node(0);
    p->dummy = true;
    for(int i=1;i<=N;++i) {
        p->r = pos[i] = new Node(i);
        p->r->p = p;
        p = p->r;
    }
    p->r = new Node(0);
    p->r->p = p;
    p = p->r;
    p->dummy = true;
    while(p) {
        pull(p);
        p = p->p;
    }
}

void print(Node *cur) {
    if(cur->l) print(cur->l);
    if(!cur->dummy) cout << cur->val << ' ';
    if(cur->r) print(cur->r);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> Q;
    init_tree();
    for(int i=0;i<Q;++i) {
        int a, b; cin >> a >> b;
        splay(pos[a]);
        int ans = root->l->sz;
        auto p = split(root);
        p.first = p.first->l;
        p.first->p = nullptr;
        merge(p.first, p.second);
        splay(pos[b]);
        Node *tmp = pos[b]->r;
        while(tmp->l) tmp = tmp->l;
        tmp->l = pos[a];
        pos[a]->p = tmp;
        pos[a]->l = pos[a]->r = nullptr;
        pos[a]->sz = 1;
        splay(pos[a]);
        ans = root->l->sz - ans;
        cout << ans << '\n';
    }
    print(root); cout << '\n';
    return 0;
}