Luogu 文艺平衡树（Splay）

题解

题意

一段序列，每次翻转一段区间，输出最后的序列

解

显然要维护下标，不可以维护 key[], 然而在这道题中应该是一样的
首先将 1 - n 插入平衡树
将区间 [l, r] 进行翻转考虑如何操作
找到 l 的前驱 pre, 也就是下标为 l - 1 的数，将 pre Rotate 到根
找到 r 的后继 nxt, 也就是下标为 r + 1 的数，将 nxt Rotate 到根的儿子（右儿子）
此时 nxt 的左子树就是区间 [l, r]
对区间打旋转标记
以后用到该节点就要下放旋转标记
就可以完美的解决这道题

Code

#include <bits/stdc++.h>
const int N = 1e5 + 10;
const int oo = 1e9;
int Root, Size, ch[N][2], fa[N], size[N], flag[N], key[N], A[N];
int n, T;
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
void Update(int x) {size[x] = size[ch[x][1]] + size[ch[x][0]] + 1;}
bool Get(int x) {return x == ch[fa[x]][1];}
void Pushup(int x) {
    if(x && flag[x]) {
        flag[ch[x][1]] ^= 1;
        flag[ch[x][0]] ^= 1;
        std:: swap(ch[x][1], ch[x][0]);
        flag[x] = 0;
    }
} 
void Rotate(int x) {
    Pushup(fa[x]);
    Pushup(x);
    int fax = fa[x], grfa = fa[fax], w = Get(x);
    ch[fax][w] = ch[x][w ^ 1];
    fa[ch[x][w ^ 1]] = fax;
    ch[x][w ^ 1] = fax;
    fa[fax] = x;
    fa[x] = grfa;
    ch[grfa][ch[grfa][1] == fax] = x;
    Update(x);
    Update(fax);
}
void Splay(int x, int y) {
    for(int fax = 1; (fax = fa[x]) && (fax != y); Rotate(x))
        if(fa[fax] != y)
            Rotate((Get(fax) == Get(x)) ? fax : x);
    if(!y) Root = x;
}
void Insert(int x) {
    if(!Size) {
        Size ++;
        Root = 1;
        size[Root] = 1;
        key[Root] = x;
        return ;
    }
    int now = Root, fanow = 0;
    while(1) {
        fanow = now;
        now = ch[now][x > key[fanow]];
        if(!now) {
            Size ++;
            ch[fanow][x > key[fanow]] = Size;
            key[Size] = x;
            fa[Size] = fanow;
            size[Size] = 1;
            Update(fanow);
            Splay(Size, 0);
            break;
        }
    }
}
inline int Find(int x) {
    int now = Root;
    while(1) {
        Pushup(now);
        if(x <= size[ch[now][0]]) now = ch[now][0];
        else {
            x -= size[ch[now][0]] + 1;
            if(!x) return now;
            now = ch[now][1];
        }
    }
}
void Dfs(int x) {
    Pushup(x);
    if(ch[x][0]) Dfs(ch[x][0]);
    if(key[x] != oo && key[x] != - oo) std:: cout << key[x] << " ";
    if(ch[x][1]) Dfs(ch[x][1]);
}
int main() {
    n = read(); T = read();
    A[1] = - oo; A[n + 2] = oo;
    for(int i = 1; i <= n; i ++) A[i + 1] = i;
    for(int i = 1; i <= n + 2; i ++) Insert(A[i]);
    Splay(1, 0);
    for(; T; T --) {
        int l = read(), r = read();
        int pre = Find(l), nxt = Find(r + 2);
        Splay(pre, 0), Splay(nxt, pre);
        flag[ch[nxt][0]] ^= 1;
    }
    Dfs(Root);
    return 0;
}