백준 13159번 배열

문제 요약

처음에 $a_i = i$인 크기가 N인 배열 $a$가 주어진다. 이 배열에 대해서 다음과 같은 쿼리를 수행하고 모든 쿼리를 수행한 뒤에 배열 $a$를 출력한다.

풀이

해당 문제는 스플레이 트리로 해결이 가능하다. 제일 처음에는 선형 모양의 스플레이 트리를 만들고 1부터 N까지를 차례대로 값에 넣어주도록 하자.

 

1번 쿼리는 각 노드 별로 최솟값, 최댓값, 합을 관리해줌으로 값은 구할 수 있고 구간을 뒤집는 연산은 Lazy Propagation으로 가능하다.

 

2번 쿼리는 k가 양수인 경우에는 [l,r]을 오른쪽으로 shift해야 되는데 이 경우는 구간을 뒤집는 연산을 세번 하면 가능하다.

[r-k+1, r]을 먼저 뒤집고, [l,r-k]를 뒤집고 그 다음엔 [l,r]을 뒤집으면 shift가 완료된다.

왼쪽으로 할 경우에는 [l, l+k-1]을 뒤집고, [l+k,r]을 뒤집고, [l, r]을 뒤집으면 완료된다.

 

3번 쿼리는 i번째 원소를 찾고 그 노드를 스플레이 해주면 된다.

 

4번 쿼리는 처음에 트리를 선형으로 만들어줄 때, i가 있는 노드의 포인터를 저장해주자. 그 포인터를 $p_i$라고 하면 이 노드를 스플레이 해주면 인덱스는 루트의 서브트리 크기 사이즈를 통해서 알 수 있다.

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

struct Node {
    Node *left, *right, *p;
    ll sz;
    ll val, mi, mx, sum;
    bool inv;
    Node() : left(nullptr), right(nullptr), p(nullptr) {};
} *root;
Node *indices[300005];
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;
    cur->mi = cur->mx = cur->sum = cur->val;
    if(cur->left) {
        cur->sz += cur->left->sz;
        cur->sum += cur->left->sum;
        cur->mi = min(cur->mi, cur->left->mi);
        cur->mx = max(cur->mx, cur->left->mx);
    }
    if(cur->right) {
        cur->sz += cur->right->sz;
        cur->sum += cur->right->sum;
        cur->mi = min(cur->mi, cur->right->mi);
        cur->mx = max(cur->mx, cur->right->mx);
    }
}

void rotate(Node *cur) {
    Node *p, *b;
    p = cur->p;
    if(!p) return ;
    push(p); push(cur);
    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;
    indices[0] = p;
    for(int i=1;i<=N;++i) {
        p->right = new Node;
        p->right->p = p;
        p = p->right;
        p->val = i;
        p->inv = false;
        indices[i] = p;
    }
    p->right = new Node;
    p->right->p = p;
    p = p->right;
    p->val = 0;
    p->inv = false;
    indices[N+1] = p;
    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 inorder(Node *cur) {
    push(cur);
    if(cur->left) inorder(cur->left);
    if(cur->val) cout << cur->val << ' ';
    if(cur->right) inorder(cur->right);
}

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,x;
        cin >> a;
        if(a == 1) {
            cin >> b >> c;
            segment(b,c);
            Node *p = root->right->left;
            cout << p->mi << ' ' << p->mx << ' ' << p->sum << '\n';
            p->inv = !p->inv;
        }
        else if(a == 2) {
            cin >> b >> c >> x;
            segment(b,c);
            Node *p = root->right->left;
            cout << p->mi << ' ' << p->mx << ' ' << p->sum << '\n';
            if(b == c) continue;
            int k = c-b+1;
            if(x > 0) {
                x %= k;
                if(x == 0) continue ;
                flip(c-x+1,c);
                flip(b,c-x);
                flip(b,c);
            }
            else if (x < 0) {
                x = -x;
                x %= k;
                if(x == 0) continue ;
                flip(b,b+x-1);
                flip(b+x,c);
                flip(b,c);
            }
        }
        else if(a == 3) {
            cin >> b;
            findKth(b); cout << root->val << '\n';
        }
        else {
            cin >> b;
            splay(indices[b]); cout << root->left->sz << '\n';
        }
    }
    inorder(root);
    cout << '\n';
    return 0;
}