bzoj 3223: Tyvj 1729 文艺平衡树 (splay）

链接： https://www.lydsy.com/JudgeOnline/problem.php?id=3223

题面：

3223: Tyvj 1729 文艺平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 7451  Solved: 4657
[Submit][Status][Discuss]

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n)  m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字，表示原始序列经过m次变换后的结果

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

实现代码：

#include<bits/stdc++.h>
using namespace std;
const int M = 2e5+;
const int inf = 0x3f3f3f;
int n,m,sz,rt;
int c[M][],fa[M],v[M],siz[M];
bool rev[M];

inline void up(int k){
    int l = c[k][],r = c[k][];
    siz[k] = siz[l] + siz[r] + ;
}

void pushdown(int k){
    int l = c[k][],r = c[k][];
    if(rev[k]){
        rev[k] = ; rev[l]^=; rev[r]^=;
        swap(c[k][],c[k][]);
    }
}

void rotate(int x,int &k){
    int y = fa[x],z = fa[y],l,r;
    if(c[y][] == x) l = ;
    else l = ;
    r = l^;
    if(y == k) k = x;
    else {
        if(c[z][]==y) c[z][]=x;
        else c[z][] = x;
    }
    fa[x] = z;fa[y] = x;fa[c[x][r]]=y;
    c[y][l]=c[x][r]; c[x][r]=y;
    up(y); up(x);
}

void splay(int x,int &k){
    while(x != k){
        int y = fa[x],z = fa[y];
        if(y != k){
            if(c[y][]==x^c[z][]==y)rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}

int find(int k,int rk){
    if(rev[k]) pushdown(k);
    int l = c[k][],r = c[k][];
    if(siz[l] +  == rk) return k;
    else if(siz[l] >= rk) return find(l,rk);
    else return find(r,rk-siz[l]-);
}

inline void reve(int l,int r){
    int x = find(rt,l),y = find(rt,r+);
    splay(x,rt); splay(y,c[x][]);
    int z = c[y][];
    rev[z] ^= ;
}

inline void build(int l,int r,int f)
{
    if(l>r)return;
    int now=l,last=f;
    if(l==r)
    {
        v[now]=l;siz[now]=;fa[now]=last;
        if(l<f)c[last][]=now;
        else c[last][]=now;
        return;
    }
    int mid=(l+r)>>;now=mid;
    build(l,mid-,mid);build(mid+,r,mid);
    v[now]=mid;fa[now]=last;
    if(mid<f)c[last][]=now;
    else c[last][]=now;
    up(now);
}

int main()
{
    ios::sync_with_stdio();
    cin.tie(); cout.tie();
    int x,y;
    cin>>n>>m;
    build(,n+,); rt = (n+) >> ;
    for(int i = ;i <= m;i ++){
        cin>>x>>y;
        reve(x,y);
    }
    for(int i = ;i <= n;i ++){
        cout<<find(rt,i+)-<<" ";
    }
    cout<<endl;
}