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

· · 题解

发一篇为数不多的 Splay。看到很多大佬写的，完全看不懂 QwQ。
题意其实已经很清晰了，就是对一个长度为 n 的序列进行 m 次区间翻转，最后输出最终的序列。

时间复杂度分析：

若暴力执行，很明显时间复杂度为 O(nm)，这显然过不了，所以我们就得考虑如何用 Splay 去维护。

思路：

根据 Splay 的性质，它能维护一个序列（就是它的中序遍历）。我们将每一次的翻转操作用懒标记代替，每次父节点下传时，将父节点的左右子树交换，再把自己的懒标记标为 0。这样难题就集中在如何每次做翻转操作时如何将翻转的区间集中在一起。

聚集区间的实现：

想要把翻转的区间集中在一起，我们需要找出它们的前一个数的位置和后一个数的位置。接着，先将区间前一个数转到根节点上，再把区间后一个数转到根节点的右孩子上，这样就保证所翻转区间的左边都聚集在根节点的左子树，右边都聚集再根节点的右孩子的右子树上，所翻转区间全聚集在根节点的右孩子的左子树（该子树不包含根节点）上。

注意：

以上代码中，我们要注意两个哨兵节点，在查询区间左边的数和右边的数时，要考虑一下，即： 

l = get_k(l), r = get_k(r + 2);

还有，在每次执行查找位置的操作时，记住为了保证翻转的正确性，每次到一个节点 x 时，一定要下传懒标记，即： 

int x = root;
while(true) {
  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;
}

最后的中序遍历时，由于不一定所有懒标记都下传了，所以要每遍历到一个节点时，都要下穿懒标记，使当前节点的左右儿子都处于正确位置（因为每次下传只会影响当前节点的左右子树）。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5, INF = 1e6;

struct Node {
    int s[2], p, v;
    int tag, size;
    void init(int p1, int v1) {
        p = p1, v = v1, size = 1;
    }
} tr[N];

int n, m, root, idx;

void pushup(int x) {
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}

void rotate(int x) {
    int k = tr[y].s[1] == x;
    tr[tr[x].s[k ^ 1]].p = y;
    tr[y].s[k] = tr[x].s[k ^ 1];
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    pushup(y), pushup(x);//别忘了pushup
}

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)
        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);
}

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;//别忘了置0
    }
}

int get_k(int k) {//查找第k个数
    int x = root;
    while(true) {
        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)
        cout << tr[x].v << " ";
    if(tr[x].s[1])
        output(tr[x].s[1]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    insert(-INF), insert(INF);//先插入两个哨兵
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        insert(i);
    while(m--) {
        int l, r;
        cin >> 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;
}

这样，就将每次操作的时间复杂度就降到了 O(\log{n})，比 O(n) 快了许多。