Splay(区间翻转)

题目：https://www.acwing.com/problem/content/2439/

题意：给定一个长度为 n 的整数序列，初始时序列为 {1,2,…,n−1,n}，序列中的位置从左到右依次标号为 1∼n。在要对该序列进行 m 次操作，每次操作选定一个子序列 [l,r]，并将该子序列中的所有数字进行翻转，最后输出翻转完后的序列。

题解：用splay去维护整个数组的信息，splay维护的永远都是中序遍历，这个中序遍历就是现在这个数组1-n分别存的信息。

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#include <unordered_map>
//#include <unordered_set>
//#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define pii pair<int, int>
#define mpr make_pair
#define ms(a, b) memset((a), (b), sizeof(a))
#define x first
#define y second
typedef long long ll;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
inline int read() {
    char ch = getchar();
    int s = 0, w = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0', ch = getchar();
    }
    return s * w;
}

const int N = 100010;

int n, m;
// splay维护的永远是中序遍历，中序遍历就是数组的顺序
struct node {        
    int s[2], p, v;  //p是父亲节点，v是价值-没多大用处-只在建数和输出的时候用到了-因为要输出它
    int size, flag;  //size来记录它的子树有多少个数包含它自己，用size来体现它在数组中是第几个数
    //初始化v，p，size
    void init(int _v, int _p) {
        v = _v, p = _p;
        size = 1;
    }
} tr[N];
int root, idx; //root是根
//idx是代表这个splay用到了数组中多少个数-也是申请新的节点，也没多大实际用处

//每次旋转都要更新的信息
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].flag) {
        swap(tr[x].s[0], tr[x].s[1]);//翻转左右子树
        tr[tr[x].s[0]].flag ^= 1;   //并向下传递信息
        tr[tr[x].s[1]].flag ^= 1;
        tr[x].flag = 0;
    }
}

//旋转板子
void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;  // k=0表示x是y的左儿子；k=1表示x是y的右儿子
    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);
}

//splay板子，将x放到k的下面
void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y))
                rotate(x);
            else
                rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}
void insert(int v) {
    int u = root, p = 0;
    //找它该放置的位置(这里是搜索树的放法)
    while (u) p = u, u = tr[u].s[v > tr[u].v];
    u = ++idx;
    if (p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, p);
    //然后把它移动到根节点，这个时候移动过程中遇到的点size都会更新
    splay(u, 0);
}
//得到第数组中k个数在splay中的下标
int get_k(int k) {
    int u = root;
    while (true) {
        pushdown(u);
        if (tr[tr[u].s[0]].size >= k)
            u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 == k)
            return u;
        else
            k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    return -1;
}
void output(int u) {
    pushdown(u);//输出之前将交换的全部传递完，交换完
    if (tr[u].s[0]) output(tr[u].s[0]);
    if (tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v);
    if (tr[u].s[1]) output(tr[u].s[1]);
}
signed main() {
    //splay的所有操作，看似可能很复杂，但经过严格的证明，它的均摊时间复杂度是log(n)的

    //splay维护的永远都是这个序列的中序遍历，也就说它的中序遍历就是数组的顺序
    //所以也是围绕下标来操作的和v这个价值或者权值没关系
    //下标用什么体现，用它的左子树的数量size来体现这个数是第几个下标
    scanf("%d%d", &n, &m);
    //先把树建好，设置两个哨兵，0和n+1，因为对区间进行操作的时候，操作l-r找的是(l-1)-(r+1)
    //把l-1放到根节点，把r+1放到l-1的下面，这样r+1的左子树就是这个区间
    for (int i = 0; i <= n + 1; i++) insert(i);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);  
        //翻转l-1到r+1这个区间
        //因为加了个左边界0，所以应该找l+1个数而不是l了
        //翻转l---r其实就是翻转l+1---r+1

        //找到数组中第l个数在splay中的下标
        l = get_k(l), r = get_k(r + 2);
        //先将左端点转到根，再将右端点转到左端点下面
        splay(l, 0), splay(r, l);
        //这个时候右端点的左子树就是这个区间了，将这个左子树进行标记，代表要进行翻转
        //这个左子树的可能是千奇百怪的，但它的中序遍历一定就是目前数组l-r直接的数
        //这个翻转的标记会下传到每一个数，但是它也是相当于懒惰标记，如果同一个区间翻转
        //两次，其实也相当于没有翻转，异或以后就为0了，相当于不翻转
        tr[tr[r].s[0]].flag ^= 1;
    }
    output(root);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159