【模板】文艺平衡树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。

最后输出这个数列

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
struct node{
    int s[2],p,v;
    int size,tag;
    void init(int p1,int v1){
        p = p1,v = v1,size = 1;
    }
}tr[N];
int root,idx;
void pushup(int x){
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void pushdown(int x){
    if(tr[x].tag){
        swap(tr[x].s[0],tr[x].s[1]);
        tr[tr[x].s[0]].tag ^= 1;
        tr[tr[x].s[1]].tag ^= 1;
        tr[x].tag = 0;
    }
}
void rotate(int x){
    int y = tr[x].p,z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1];
    tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;
    pushup(y),pushup(x);
}
void splay(int x,int k){
    while(tr[x].p != k){
        int y = tr[x].p,z = tr[y].p;
        if(z != k){
            (tr[y].s[0] == x) ^ (tr[z].s[0] == y) ? rotate(x) : rotate(y);
        }
        rotate(x);
    }
    if(k == 0) root = x;
}
void insert(int v){
    int x = root,p = 0;
    while(x) p = x,x = tr[x].s[v > tr[x].v];
    x = ++ idx;
    tr[p].s[v > tr[p].v] = x;
    tr[x].init(p,v);
    splay(x,0);
}
int get_k(int k){
    int x = root;
    while(1){
        pushdown(x);
        int y = tr[x].s[0];
        if(tr[y].size + 1 < k){
            k -= tr[y].size + 1;
            x = tr[x].s[1];
        }
        else if(tr[y].size >= k) x = y;
        else return x;
    }
}
void output(int x){
    pushdown(x);
    if(tr[x].s[0]) output(tr[x].s[0]);
    if(tr[x].v >= 1 && tr[x].v <= n)
        printf("%d ",tr[x].v);
    if(tr[x].s[1]) output(tr[x].s[1]);
}
int main(){
    insert(-1e6),insert(1e6);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) insert(i);
    while(m --){
        int l,r;
        scanf("%d%d",&l,&r);
        l = get_k(l),r = get_k(r + 2);
        splay(l,0),splay(r,l);
        tr[tr[r].s[0]].tag ^= 1;
    }
    output(root);
    return 0;
}