跳转至

平衡树模板

平衡树是一种数据结构，可以维护序列和集合。普通平衡树的空间复杂度为 \(O(n)\)。平衡树可以在 \(O(\log V)\) 的时间复杂度内实现各种操作：

  • 插入；
  • 单点删除（Treap）；
  • 区间删除（Splay，FHQ）；
  • 区间打 tag、区间翻转（Splay，FHQ）；
  • 求排名、下标；
  • 求给定下标、排名位置的数字；

主流平衡树有 \(3\) 种：带旋 Treap、Splay、FHQ Treap。三者的实现方法不同，常数不同，额外的附加功能也不同。

FHQ Treap 可以可持久化，可以快速带交合并，而且码量小，但是常数稍大。

带旋 Treap 常数和码量都较小，但不能进行区间操作。

P6136 【模板】普通平衡树（数据加强版）

代码 
  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
#include<bits/stl_algobase.h>
#include<ctype.h>
#include<cstdio>
#include<random>
using namespace std;
const int N = 1.1e6 + 10;
const int INF = 0x7fffffff;

#define endl '\n'
namespace io {
    struct istream {
        char ch;
        inline istream &operator>>(int &x) {
            while(!isdigit(ch = getchar_unlocked()));
            x = ch - '0';
            while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
            return *this;
        }
    } cin;
    struct ostream {
        char buf[60], top;
        inline ostream() : top(0) {}
        inline ostream &operator<<(int x) {
            do buf[++top] = x % 10 + '0', x /= 10; while(x);
            while(top) putchar_unlocked(buf[top--]);
            return *this;
        }
        inline ostream &operator<<(char c) {
            putchar_unlocked(c);
            return *this;
        }
        inline ostream &operator<<(const char s[]) {
            for(int i = 0; s[i]; i++) putchar_unlocked(s[i]);
            return *this;
        }
    } cout;
}

using io::cin;
using io::cout;

namespace Treap {
    mt19937 rng((random_device){}());
    int val[N], pri[N], sz[N], chd[N][2], nn, rt;
    inline int addNode(int v) {
        val[++nn] = v;
        pri[nn] = rng();
        sz[nn] = 1; 
        return nn;
    }
    inline void push_up(int p) {
        sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
    }
    inline void rotate(int &x, int d) {
        int y = chd[x][d], z = chd[y][d ^ 1];
        chd[x][d] = z;
        chd[y][d ^ 1] = x;
        push_up(x);
        push_up(y);
        x = y;
    }
    void insert(int &p, int v) {
        if(!p) { p = addNode(v); return; }
        int d = v > val[p];
        insert(chd[p][d], v);
        if(pri[chd[p][d]] < pri[p]) rotate(p, d);
        else push_up(p);
    }
    void erase(int &p, int v) {
        if(val[p] == v) {
            if(!chd[p][0]) { p = chd[p][1]; return; }
            if(!chd[p][1]) { p = chd[p][0]; return; }
            if(pri[chd[p][0]] < pri[chd[p][1]]) { rotate(p, 0); erase(chd[p][1], v); }
            else { rotate(p, 1); erase(chd[p][0], v); }
        } else {
            erase(chd[p][v > val[p]], v);
        }
        push_up(p);
    }
    int queryRank(int &p, int v) {
        if(!p) return 0;
        if(val[p] < v) return sz[chd[p][0]] + 1 + queryRank(chd[p][1], v);
        else return queryRank(chd[p][0], v);
    }
    int queryKth(int &p, int k) {
        if(k == sz[chd[p][0]] + 1) return val[p];
        if(k <= sz[chd[p][0]]) return queryKth(chd[p][0], k);
        return queryKth(chd[p][1], k - sz[chd[p][0]] - 1);
    }
    int queryPre(int &p, int v) {
        if(!p) return -INF;
        if(val[p] < v) return max(val[p], queryPre(chd[p][1], v));
        return queryPre(chd[p][0], v);
    }
    int querySuc(int &p, int v) {
        if(!p) return INF;
        if(val[p] > v) return min(val[p], querySuc(chd[p][0], v));
        return querySuc(chd[p][1], v);
    }
    inline void insert(int v) { insert(rt, v); }
    inline void erase(int v) { erase(rt, v); }
    inline int queryRank(int v) { return queryRank(rt, v); }
    inline int queryKth(int k) { return queryKth(rt, k); }
    inline int queryPre(int v) { return queryPre(rt, v); }
    inline int querySuc(int v) { return querySuc(rt, v); }
}

using namespace Treap;

int n, m;
int lastans, ans;

inline void addAns(int res) {
    lastans = res;
    ans ^= res;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        Treap::insert(x);
    }

    while(m--) {
        int op, x;
        cin >> op >> x;
        x ^= lastans;
        if(op == 1) Treap::insert(x);
        else if(op == 2) Treap::erase(x);
        else if(op == 3) addAns(Treap::queryRank(x) + 1);
        else if(op == 4) addAns(Treap::queryKth(x));
        else if(op == 5) addAns(Treap::queryPre(x));
        else if(op == 6) addAns(Treap::querySuc(x));
    }

    cout << ans << '\n';

    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
160
161
162
163
164
165
166
#include<bits/stl_algobase.h>
#include<ctype.h>
#include<cstdio>
#include<random>
#define int long long
using namespace std;
const int N = 1.1E6 + 10;

#define endl '\n'
namespace io {
    struct istream {
        char ch;
        inline istream &operator>>(int &x) {
            while(!isdigit(ch = getchar_unlocked()));
            x = ch - '0';
            while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
            return *this;
        }
    } cin;
    struct ostream {
        char buf[60], top;
        inline ostream() : top(0) {}
        inline ostream &operator<<(int x) {
            do buf[++top] = x % 10 + '0', x /= 10; while(x);
            while(top) putchar_unlocked(buf[top--]);
            return *this;
        }
        inline ostream &operator<<(char c) {
            putchar_unlocked(c);
            return *this;
        }
        inline ostream &operator<<(const char s[]) {
            for(int i = 0; s[i]; i++) putchar_unlocked(s[i]);
            return *this;
        }
    } cout;
}

using io::cin;
using io::cout;

int n, m, nn;
int val[N], son[N][2], pri[N], sz[N], a[N];

mt19937 rng((random_device){}());

int addNode(int v) {
    val[++nn] = v;
    pri[nn] = rng();
    sz[nn] = 1;
    return nn;
}

void push_up(int u) {
    sz[u] = sz[son[u][0]] + sz[son[u][1]] + 1;
}

void split(int cur, int v, int &x, int &y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    if(val[cur] <= v) {
        x = cur;
        split(son[cur][1], v, son[cur][1], y);
    } else {
        y = cur;
        split(son[cur][0], v, x, son[cur][0]);
    }
    push_up(cur);
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        son[x][1] = merge(son[x][1], y);
        push_up(x);
        return x;
    } else {
        son[y][0] = merge(x, son[y][0]);
        push_up(y);
        return y;
    }
}

int root = 0;
int insert(int v) {
    int x, y, z;
    y = addNode(v);
    split(root, v, x, z);
    return root = merge(merge(x, y), z);
}

int del(int v) {
    int x, y, z, w;
    split(root, v - 1, x, z);
    split(z, v, w, y);
    return root = merge(x, merge(merge(son[w][0], son[w][1]), y));
}

int queryRank(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int res = sz[x] + 1;
    root = merge(x, y);
    return res;
}

int queryKth(int u, int x) {
    int cur = u;
    while(cur) {
        if(sz[son[cur][0]] + 1 == x) {
            return val[cur];
        } else if(x <= sz[son[cur][0]]) {
            cur = son[cur][0];
        } else {
            x -= sz[son[cur][0]] + 1;
            cur = son[cur][1];
        }
    }
    return -1;
}

int queryPre(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int res = queryKth(x, sz[x]);
    root = merge(x, y);
    return res;
}

int querySuc(int v) {
    int x, y;
    split(root, v, x, y);
    int res = queryKth(y, 1);
    root = merge(x, y);
    return res;
}

signed main() {

    cin >> n >> m;
    for(int i = 1, ai; i <= n; i++) {
        cin >> ai;
        insert(ai);
    }

    int last = 0, ans = 0;
    while(m--) {
        int op, x;
        cin >> op >> x;
        x ^= last;
        if(op == 1) insert(x);
        else if(op == 2) del(x);
        else if(op == 3) ans ^= (last = queryRank(x));
        else if(op == 4) ans ^= (last = queryKth(root, x));
        else if(op == 5) ans ^= (last = queryPre(x));
        else ans ^= (last = querySuc(x));
    }

    cout << ans << endl;

    return 0;
}

P2042 [NOI2005] 维护数列

代码 
  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N = 5E5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int a[N];

int root, nn;
int val[N], chd[N][2], sz[N], sum[N], pri[N];
int lans[N], rans[N], ans[N], Max[N];;
int tag_rev[N], tag_mdf[N];

int pool[N], top;

void push_up(int p) {
    int lc = chd[p][0], rc = chd[p][1];
    sz[p] = sz[lc] + sz[rc] + 1;
    sum[p] = sum[lc] + sum[rc] + val[p];
    Max[p] = max(max(Max[chd[p][0]], Max[chd[p][1]]), val[p]);
    lans[p] = max(lans[lc], sum[lc] + val[p] + lans[rc]);
    rans[p] = max(rans[rc], sum[rc] + val[p] + rans[lc]);
    lans[p] = max(lans[p], 0ll);
    rans[p] = max(rans[p], 0ll);
    ans[p] = max(max(ans[lc], ans[rc]), max(lans[p], rans[p]));
    ans[p] = max(ans[p], sum[p]);
    ans[p] = max(ans[p], rans[lc] + lans[rc] + val[p]);
    ans[p] = max(ans[p], 0ll);
}

void move_tag_rev(int p) {
    swap(chd[p][0], chd[p][1]);
    swap(lans[p], rans[p]);
    tag_rev[p] ^= 1;
}

void move_tag_mdf(int p, int tg) {
    sum[p] = sz[p] * tg;
    Max[p] = tg;
    val[p] = tg;
    tag_mdf[p] = tg;
    lans[p] = rans[p] = ans[p] = (sum[p] > 0) ? sum[p] : 0;
}

void push_down(int p) {
    if(tag_rev[p] != 0) {
        move_tag_rev(chd[p][0]);
        move_tag_rev(chd[p][1]);
        tag_rev[p] = 0;
    }
    if(tag_mdf[p] != INF) {
        move_tag_mdf(chd[p][0], tag_mdf[p]);
        move_tag_mdf(chd[p][1], tag_mdf[p]);
        tag_mdf[p] = INF;
    }
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

void split(int cur, int v, int& x, int& y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    push_down(cur);
    if(sz[chd[cur][0]] + 1 <= v) {
        x = cur;
        split(chd[x][1], v - (sz[chd[cur][0]] + 1), chd[x][1], y);
    } else {
        y = cur;
        split(chd[y][0], v, x, chd[y][0]);
    }
    push_up(cur);
}

int addNode(int v) {
    int pos;
    if(top != 0) {
        pos = pool[top--];
    } else {
        pos = ++nn;
    }
    val[pos] = sum[pos] = v;
    chd[pos][0] = chd[pos][1] = 0;
    Max[pos] = v;
    sz[pos] = 1;
    pri[pos] = rand();
    tag_rev[pos] = 0;
    lans[pos] = rans[pos] = ans[pos] = max(v, 0ll);
    return pos;
}

int makeTree(int l, int r, int* v) {
    if(l == r) {
        return addNode(v[l]);
    }
    int mid = (l + r) >> 1;
    return merge(makeTree(l, mid, v), makeTree(mid + 1, r, v));
}

void delTree(int p) {
    if(p == 0) return;
    delTree(chd[p][0]);
    delTree(chd[p][1]);
    pool[++top] = p;
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(tag_mdf, 0x3f, sizeof(tag_mdf));
    memset(Max, -0x3f, sizeof(Max));

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    root = makeTree(1, n, a);

    while(m--) {
        string op;
        cin >> op;
        if(op == "INSERT") {
            int pos, tot;
            cin >> pos >> tot;
            int c[tot + 10];
            for(int i = 1; i <= tot; i++) {
                cin >> c[i];
            }
            int y = makeTree(1, tot, c);
            int x, z;
            split(root, pos, x, z);
            root = merge(merge(x, y), z);
        } else if(op == "DELETE") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            delTree(y);
            root = merge(x, z);
        } else if(op == "MAKE-SAME") {
            int pos, tot, c;
            cin >> pos >> tot >> c;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            move_tag_mdf(y, c);
            root = merge(merge(x, y), z);
        } else if(op == "REVERSE") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            move_tag_rev(y);
            root = merge(merge(x, y), z);
        } else if(op == "GET-SUM") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            cout << sum[y] << endl;
            root = merge(merge(x, y), z);
        } else if(op == "MAX-SUM") {
            if(ans[root] == 0) {
                cout << Max[root] << endl;
            } else cout << ans[root] << endl;
        }
    }

    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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include<iostream>
#define int long long
using namespace std;
const int INF = (int)0x3f3f3f3f3f3f3f3f;
const int N = 5E5 + 10;

struct Node {
    int lans, rans, ans, sum, mx;
};

int n, q;

int nn, root;
int val[N], sz[N], chd[N][2], fa[N];
int tag_inv[N], tag_mdf[N];
Node tr[N];

inline void push_up(int p) {
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
    Node &cur = tr[p];
    const Node &l = tr[chd[p][0]], &r = tr[chd[p][1]];
    cur.sum = l.sum + r.sum + val[p];
    cur.lans = max(l.lans, l.sum + val[p] + r.lans);
    cur.rans = max(r.rans, r.sum + val[p] + l.rans);
    cur.ans = max(max(l.ans, r.ans), l.rans + val[p] + r.lans);
    cur.mx = max(max(l.mx, r.mx), val[p]);
}

int sta[N], top;

inline int addNode(int v) {
    int nw;
    if(top) nw = sta[top--];
    else nw = ++nn;
    sz[nw] = 1;
    chd[nw][0] = chd[nw][1] = 0;
    val[nw] = v;
    fa[nw] = tag_inv[nw] = 0;
    tag_mdf[nw] = -INF;
    tr[nw] = {max(v, 0ll), max(v, 0ll), max(v, 0ll), v, v};
    return nw;
}

inline void move_tag_inv(int p) {
    tag_inv[p] ^= 1;
    swap(chd[p][0], chd[p][1]);
    swap(tr[p].lans, tr[p].rans);
}

inline void move_tag_mdf(int p, int tg) {
    tag_mdf[p] = tg;
    val[p] = tg;
    tr[p] = {max(tg, 0ll) * sz[p], max(tg, 0ll) * sz[p], max(tg, 0ll) * sz[p], tg * sz[p], tg};
}

inline void push_down(int p) {
    if(tag_mdf[p] != -INF) {
        move_tag_mdf(chd[p][0], tag_mdf[p]);
        move_tag_mdf(chd[p][1], tag_mdf[p]);
        tag_mdf[p] = -INF;
    }
    if(tag_inv[p]) {
        move_tag_inv(chd[p][0]);
        move_tag_inv(chd[p][1]); 
        tag_inv[p] = 0;
    }
}

inline bool get(int x) {
    return chd[fa[x]][1] == x;
}

inline void rotate(int x) {
    int y = fa[x], z = fa[y], d = get(x), w = chd[x][d ^ 1];
    fa[w] = y;
    chd[y][d] = w;
    fa[x] = z;
    if(z) chd[z][get(y)] = x;
    fa[y] = x;
    chd[x][d ^ 1] = y;
    push_up(y);
    push_up(x); 
} 

inline void splay(int x, int lim = 0) {
    for( ; fa[x] != lim; rotate(x)) {
        if(fa[fa[x]] != lim) {
            if(get(x) == get(fa[x])) rotate(fa[x]);
            else rotate(x); 
        }
    }
    if(lim == 0) root = x;
}

inline void insert(int pos, int v) {
    int cur = root, old = 0, d = 0;
    while(cur != 0) {
        push_down(cur); 
        old = cur;
        if(pos <= sz[chd[cur][0]]) {
            cur = chd[cur][0];
            d = 0;
        } else {
            pos -= sz[chd[cur][0]] + 1;
            cur = chd[cur][1];
            d = 1;
        }
    }
    cur = addNode(v);
    fa[cur] = old;
    if(old) chd[old][d] = cur;
    splay(cur);
}

inline int queryKth(int k) {
    int cur = root;
    while(cur != 0) {
        push_down(cur); 
        if(k <= sz[chd[cur][0]]) {
            cur = chd[cur][0];
        } else if(k == sz[chd[cur][0]] + 1) {
            splay(cur);
            return cur;
        } else {
            k -= sz[chd[cur][0]] + 1;
            cur = chd[cur][1];
        }
    }
    throw -1;
    return -1;
}

void rm_pt(int &p) {
    if(p == 0) return;
    rm_pt(chd[p][0]);
    rm_pt(chd[p][1]);
    sta[++top] = p;
    p = 0;
}

inline void del(int l, int r) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    rm_pt(chd[y][0]);
    push_up(y);
    splay(y);
} 

inline void make_same(int l, int r, int v) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    move_tag_mdf(chd[y][0], v);
    push_up(y);
    push_up(x);
}

inline void make_inv(int l, int r) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    move_tag_inv(chd[y][0]);
    push_up(y);
    push_up(x);
}

inline int query_sum(int l, int r) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    int res = tr[chd[y][0]].sum;
    return res;
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    tr[0].mx = -INF;

    insert(0, -INF);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        insert(i, x);
    } 

    insert(n + 1, -INF);

    while(q--) {
        string op;
        cin >> op;
        if(op == "INSERT") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            for(int i = l; i <= r; i++) {
                int x;
                cin >> x;
                insert(i + 1, x);
            } 
        } else if(op == "DELETE") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            del(l + 1, r + 1);
        } else if(op == "MAKE-SAME") {
            int l, r, c;
            cin >> l >> r >> c;
            r = l + r - 1;
            make_same(l + 1, r + 1, c);
        } else if(op == "REVERSE") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            make_inv(l + 1, r + 1);
        } else if(op == "GET-SUM") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            cout << query_sum(l + 1, r + 1) << '\n'; 
        } else {
            if(tr[root].ans == 0) {
                cout << tr[root].mx << '\n';
            } else cout << tr[root].ans << '\n';
        }
    }

    return 0;
}

P3391 【模板】文艺平衡树

代码 
  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
#include<iostream>
using namespace std;
const int N = 1E5 + 10;

int n, m, root, nn;
int val[N], chd[N][2], sz[N], tag[N], fa[N];

void push_up(int p){
    if(p != 0) sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void push_down(int p){
    if(tag[p] == 0) return;
    swap(chd[p][0], chd[p][1]);
    if(chd[p][0]) tag[chd[p][0]] ^= 1;
    if(chd[p][1]) tag[chd[p][1]] ^= 1;
    tag[p] = 0;
}

int build_tree(int l, int r, int f){
    if(l > r) return 0;
    int mid = (l + r) >> 1, p;
    val[++nn] = mid;
    p = nn;
    fa[p] = f;
    chd[p][0] = build_tree(l, mid - 1, p);
    chd[p][1] = build_tree(mid + 1, r, p);
    push_up(p);
    return p;
}

bool get(int x){
    return x == chd[fa[x]][1];
}

void rotate(int x){
    int y = fa[x], z = fa[y], d = get(x), w = chd[x][d ^ 1];
    fa[w] = y;
    chd[y][d] = w;
    fa[x] = z;
    if(z) chd[z][get(y)] = x;
    fa[y] = x;
    chd[x][d ^ 1] = y;
    push_up(y);
    push_up(x);
}

void splay(int x, int goal = 0){
    while(fa[x] != goal){
        int y = fa[x], z = fa[y];
        if(z != goal){
            if(get(x) == get(y)){
                rotate(y);
            } else{
                rotate(x);
            }
        }
        rotate(x);
    }
    if(goal == 0) root = x;
}

int kth(int x){
    int cur = root;
    while(1){
        push_down(cur);
        if(x <= sz[chd[cur][0]]){
            cur = chd[cur][0];
        } else if(x == sz[chd[cur][0]] + 1){
            splay(cur);
            return cur;
        } else{
            x -= sz[chd[cur][0]] + 1;
            cur = chd[cur][1];
        }
    }
    return 0;
}

void turn(int l, int r){
    int x = kth(l);
    int y = kth(r + 2);
    splay(x);
    splay(y, x);
    tag[chd[y][0]] ^= 1;
}

void inOrder(int x){
    push_down(x);
    if(chd[x][0]) inOrder(chd[x][0]);
    if(1 <= val[x] && val[x] <= n) cout << val[x] << ' ';
    if(chd[x][1]) inOrder(chd[x][1]);
}

int main(){

    cin >> n >> m;
    root = build_tree(0, n + 1, 0);
    while(m--){
        int l, r;
        cin >> l >> r;
        turn(l, r);
    }
    inOrder(root);
    cout << endl;

    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
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N = 1E5 + 10;

int n, m;

int root, nn;
int val[N], chd[N][2], pri[N], tag[N], sz[N];

int addNode(int v) {
    val[++nn] = v;
    pri[nn] = rand();
    sz[nn] = 1;
    return nn;
}

void push_up(int p) {
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void move_tag(int p) {
    tag[p] ^= 1;
    swap(chd[p][0], chd[p][1]);
}

void push_down(int p) {
    if(!tag[p]) return;
    move_tag(chd[p][0]);
    move_tag(chd[p][1]);
    tag[p] = 0;
}

void split(int cur, int v, int &x, int &y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    push_down(cur);
    if(sz[chd[cur][0]] + 1 <= v) {
        x = cur;
        split(chd[x][1], v - (sz[chd[cur][0]] + 1), chd[x][1], y);
    } else {
        y = cur;
        split(chd[y][0], v, x, chd[y][0]);
    }
    push_up(cur);
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

int dfs(int l, int r) {
    if(l == r) {
        return addNode(l);
    }
    int mid = (l + r) >> 1;
    return merge(dfs(l, mid), dfs(mid + 1, r));
}

void rever(int l, int r) {
    int x, y, z, w;
    split(root, r, w, z);
    split(w, l - 1, x, y);
    tag[y] ^= 1;
    swap(chd[y][0], chd[y][1]);
    root = merge(merge(x, y), z);
}

void print(int cur) {
    if(cur == 0) {
        return;
    }
    push_down(cur);
    print(chd[cur][0]);
    cout << val[cur] << ' ';
    print(chd[cur][1]);
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    srand(time(NULL));

    cin >> n >> m;
    root = dfs(1, n);

    for(int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        rever(l, r);
    }

    print(root);

    cout << endl;

    return 0;
}