백준 19589번 카드 셔플

문제 요약

처음에 $a_i = i$인 길이 N짜리 배열 a가 주어진다. 다음 쿼리를 처리하자.

1. x y가 주어지면 [x, y]를 제일 앞으로 옮긴다.
2. x y가 주어지면 [x, y]를 제일 뒤로 옮긴다.
3. x y가 주어지면 [x, y]에 위치한 카드들에 대해서 리플셔플을 한다.

N은 최대 100만, 쿼리 수는 최대 20만이다. 3번 쿼리는 구간의 길이가 1000을 넘지 않는다.

풀이

1, 2번은 스플레이트리로 쉽게 가능하다.

3번 쿼리고 [x, y]구간을 잘 모아준다음에 해당 서브트리를 inorder로 탐색해줘서 배열을 만들어준 다음에 잘 섞어준 뒤에 다시 inorder로 탐색하면서 노드의 값들을 바꿔주면 된다.

다행이 3번 쿼리에 들어오는 구간은 길이가 1000이 최대라서 위 방식으로 처리해도 된다.

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

struct Node {
    Node *left, *right, *p;
    ll sz;
    int val;
    bool inv;
    Node() : left(nullptr), right(nullptr), p(nullptr) {};
} *root;

void push(Node *cur) {
    if(!cur->inv) return ;
    swap(cur->left, cur->right);
    if(cur->left) cur->left->inv = !cur->left->inv;
    if(cur->right) cur->right->inv = !cur->right->inv;
    cur->inv = false;
}

void update(Node *cur) {
    cur->sz = 1;
    if(cur->left) {
        cur->sz += cur->left->sz;
    }
    if(cur->right) {
        cur->sz += cur->right->sz;
    }
}

void rotate(Node *cur) {
    Node *p, *b;
    p = cur->p;
    if(!p) return ;
    Node *pp = p->p;
    if(p->left == cur) {
        p->left = b = cur->right;
        cur->right = p;
    }
    else {
        p->right = b = cur->left;
        cur->left = p;
    }
    p->p = cur;
    cur->p = pp;
    if(b) b->p = p;
    if(!pp) root = cur;
    else {
        if(pp->left == p) pp->left = cur;
        else pp->right = cur;
    }
    update(p); update(cur);
}

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

void findKth(ll k) {
    Node *p = root;
    push(p);
    while(1) {
        while(p->left && p->left->sz > k) {
            p = p->left;
            push(p);
        }
        if(p->left) k -= p->left->sz;
        if(!k) break;
        else --k;
        p = p->right;
        push(p);
    }
    splay(p);
}

void segment(int l, int r) {
    findKth(l-1);
    Node *p = root;
    root = p->right;
    root->p = nullptr;
    findKth(r-l+1);
    root->p = p;
    p->right = root;
    root = p;
}

int N, Q;

void init() {
    Node *p;
    root = p = new Node;
    p->val = 0;
    p->inv = false;
    for(int i=1;i<=N;++i) {
        p->right = new Node;
        p->right->p = p;
        p = p->right;
        p->val = i;
        p->inv = false;
    }
    p->right = new Node;
    p->right->p = p;
    p = p->right;
    p->val = 0;
    p->inv = false;
    while(p) {
        update(p); p = p->p;
    }
}

void flip(int l, int r) {
    segment(l,r);
    Node *p = root->right->left;
    p->inv = !p->inv;
}

void moveFront(int l, int r) {
    if(l == 1) return ;
    flip(l,r);
    flip(1,l-1);
    flip(1,r);
}

void moveBack(int l, int r) {
    if(r == N) return ;
    flip(l,r);
    flip(r+1,N);
    flip(l,N);
}

vector<int> a, odd, even;
int idx;
void get_num(Node *cur) {
    if(!cur) return ;
    push(cur);
    get_num(cur->left);
    a.push_back(cur->val);
    get_num(cur->right);
}

void push_num(Node *cur) {
    if(!cur) return ;
    push(cur);
    push_num(cur->left);
    if(idx & 1) cur->val = odd[idx/2];
    else cur->val = even[idx/2];
    ++idx;
    push_num(cur->right);
}

void print(Node *cur) {
    if(!cur) return ;
    push(cur);
    print(cur->left);
    if(cur->val) cout << cur->val << ' ';
    print(cur->right);
}

void shuffle(int b, int c) {
    segment(b,c);
    Node *p = root->right->left;
    a.clear();
    get_num(p);
    int n = a.size();
    int thr = (n+1)/2;
    even = vector<int>(a.begin(), a.begin()+thr);
    odd = vector<int>(a.begin()+thr, a.end());
    idx = 0;
    push_num(p);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> Q;
    init();
    for(int i=0;i<Q;++i) {
        int a,b,c;
        cin >> a;
        if(a == 1) {
            cin >> b >> c;
            moveFront(b,c);
        }
        else if(a == 2) {
            cin >> b >> c;
            moveBack(b,c);
        }
        else {
            cin >> b >> c;
            shuffle(b,c);
        }
    }
    print(root);
    cout << '\n';
    return 0;
}