洛谷P3391 【模板】文艺平衡树题解

题意：

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

其中需要提供以下操作：翻转一个区间。

例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。

输入格式：

第一行两个正整数 $n,m$，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$。

接下来 $m$ 行，每行两个正整数 $l,r$，表示翻转的区间。

输出格式：

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

数据范围：

对于 $100\%$ 的数据，$1 \le n, m \leq 100000 $，$1 \le l \le r \le n$。

文艺平衡树其实蛮好理解的。它和平衡树的区别在于，维护的是每个权值的编号。

也就是说我们不关心权值（权值不就是输出用么），我们只关心他们编号的顺序。

那么翻转一个区间只需要把 $l$ 的前驱 splay 到根节点，再把 $r$ 的后继 splay 到 $l$ 的儿子

这样 $l$ 的左儿子的子树就是我们要的区间，每次像线段树一样打个标记，然后 push_down 就搞定啦。

对了，代码里的 kth 不是 k 大值的意思，是指它 splay 到根后左子树有 $k-1$ 个节点。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n;
namespace Splay
{
    int tot, rt; 
    #define ls(at) t[at].ch[0]
    #define rs(at) t[at].ch[1]
    struct node { int ch[2], num, fa, cnt, sz, tag; } t[N];
    int New(int x, int f)
    {
        t[++tot] = {0, 0, x, f, 1, 1, 0};
        if(f) t[f].ch[x > t[f].num] = tot;
        return tot;
    }
    void push_up(int at) {
        t[at].sz = t[ls(at)].sz + t[rs(at)].sz + t[at].cnt;
    }
    void push_down(int at)
    {
        if(t[at].tag)
        {
            t[ls(at)].tag ^= 1; t[rs(at)].tag ^= 1;
            t[at].tag = 0; swap(ls(at), rs(at));
        }
    }
    void rotate(int x)
    {
        int y = t[x].fa, z = t[y].fa, k = rs(y) == x;
        t[z].ch[rs(z) == y] = x; t[x].fa = z;
        t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;
        t[x].ch[k ^ 1] = y; t[y].fa = x;
        push_up(y); push_up(x);
    }
    void splay(int x, int goal)
    {
        while(t[x].fa != goal)
        {
            int y = t[x].fa, z = t[y].fa;
            if(z != goal) ((rs(y) == x) ^ (rs(z) == y)) ? rotate(x) : rotate(y);
            rotate(x);
        }
        if(!goal) rt = x;
    }
    void insert(int x)
    {
        int at = rt, f = 0;
        while(at && x != t[at].num) {
            f = at; at = t[at].ch[x > t[at].num];
        }
        if(at) ++t[at].cnt; else at = New(x, f);
        splay(at, 0);
    }
    int kth(int x)
    {
        int at = rt; if(t[at].sz < x) return INF;
        while(1)
        {
            push_down(at); int p = ls(at);
            if(x > t[p].sz + t[at].cnt)
            {
                x -= t[p].sz + t[at].cnt;
                at = t[at].ch[1];
            }else
            {
                if(x <= t[p].sz) at = p;
                else return t[at].num;
            }
        }
    }
}using namespace Splay;
void work(int l, int r)
{
    l = kth(l); r = kth(r + 2);
    splay(l, 0); splay(r, l);
    t[ls(rs(rt))].tag ^= 1;
}
void output(int at)
{
    push_down(at);
    if(ls(at)) output(ls(at));
    if(t[at].num > 1 && t[at].num < n + 2) cout << t[at].num - 1 << ' ';
    if(rs(at)) output(rs(at));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q; cin >> n >> q;
    for(int i = 1; i <= n + 2; i++) insert(i);
    while(q--) { int l, r; cin >> l >> r; work(l, r); }
    return output(rt), 0;
}