模板——数据结构2

发表于 分类于 ， 阅读次数： 作者 Pomelorin

模板——数据结构2

线段树，树状数组，动态开点线段树，主席树，树套树，树链剖分，平衡树。

线段树

  1. 维护哪些信息？区间和。
  2. 维护哪些标记？区间加标记。
  3. 如何合并区间信息？直接相加。
  4. 如何快速修改区间信息？加上 增量乘区间长度。
  5. 如何合并标记？直接相加。

单点修改，区间查询

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
#define ll long long
#define lson (root*2)
#define rson ((root*2)+1)
#define mid ((l+r)/2)

struct SGT {
    ll t[N * 4];

    void update(ll root,ll l,ll r,ll pos,ll data) {
        if (l == r) {
            t[root] += data;
            return;
        }
        if (pos <= mid)
            update(lson, l,mid, pos, data);
        if (pos > mid)
            update(rson,mid + 1, r, pos, data);
        t[root] = t[lson] + t[rson];
    }

    ll query(ll root,ll l,ll r,ll x,ll y) {
        if (x <= l && y >= r)
            return t[root];
        ll ansl = 0, ansr = 0;
        if (x <= mid)
            ansl = query(lson, l,mid, x, y);
        if (y > mid)
            ansr = query(rson,mid + 1, r, x, y);
        return ansl + ansr;
    }

    void build(ll root,ll l,ll r,ll d[]) {
        if (l == r) {
            t[root] = d[l];
            return;
        }
        build(lson, l,mid, d);
        build(rson,mid + 1, r, d);
        t[root] = t[lson] + t[rson];
        return;
    }
} Tree;

区间修改，区间查询

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
#define ll long long
#define lson (root*2)
#define rson ((root*2)+1)
#define mid ((l+r)/2)

struct SGT {
    struct Node {
        ll data, tag;
    } t[N * 4];

    void pushdown(ll root,ll l,ll r) {
        ll tag = t[root].tag;
        if (t[root].tag == 0)
            return;
        t[lson].data += tag * (mid - l + 1);
        t[rson].data += tag * (r - mid);
        t[lson].tag += tag;
        t[rson].tag += tag;
        t[root].tag = 0;
        return;
    }

    void update(ll root,ll l,ll r,ll x,ll y,ll data) {
        if (x <= l && y >= r) {
            t[root].data += data * (r - l + 1);
            t[root].tag += data;
            return;
        }
        pushdown(root, l, r);
        if (x <= mid)
            update(lson, l,mid, x, y, data);
        if (y > mid)
            update(rson,mid + 1, r, x, y, data);
        t[root].data = t[lson].data + t[rson].data;
    }

    ll query(ll root,ll l,ll r,ll x,ll y) {
        if (x <= l && y >= r)
            return t[root].data;
        pushdown(root, l, r);
        ll ansl = 0, ansr = 0;
        if (x <= mid)
            ansl = query(lson, l,mid, x, y);
        if (y > mid)
            ansr = query(rson,mid + 1, r, x, y);
        return ansl + ansr;
    }

    void build(ll root,ll l,ll r,ll d[]) {
        if (l == r) {
            t[root].data = d[l];
            return;
        }
        build(lson, l,mid, d);
        build(rson,mid + 1, r, d);
        t[root].data = t[lson].data + t[rson].data;
        return;
    }
} Tree;

树状数组

树状数组每个节点管理的是一段区间。利用数的二进制分解，每个前缀区间 \([1,x]\) 都可以使用 \(O(\log n)\) 个小区间覆盖。查询：找到这些小区间并相加，即求出区间和。更新：更新所有包含这个位置 \(x\) 的小区间。

普通

1
2
3
4
5
6
7
8
9
10
11
ll lb(ll x) { return x & (-x); }
void update(ll x, ll data) {
    while (x <= n)
        c[x] += data, x += lb(x);
}
ll query(ll x) {
    ll ans = 0;
    while (x >= 1)
        ans += c[x], x -= lb(x);
    return ans;
}//query(r)-query(l-1)

二维

1
2
3
4
5
6
7
8
9
10
11
12
13
int lb(int x) { return x & -x; }
void update(int x, int y, int data) {
    for (int i = x; i <= n; i += lb(i))
        for (int j = y; j <= m; j += lb(j))
            t[i][j] += data;
}
int query(int x, int y) {
    int ret = 0;
    for (int i = x; i; i -= lb(i))
        for (int j = y; j; j -= lb(j))
            ret += t[i][j];
    return ret;
}

动态开点线段树

普通

通常没有 build 操作。

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
typedef long long ll;
const ll N = 35 * 500000 + 10;
ll cnt = 0;

struct SGT {
    struct node {
        int lson, rson, data;
    } t[N];

#define lson t[root].lson
#define rson t[root].rson
#define mid ((l+r)/2)

    ll update(ll root, ll l, ll r, ll pos, ll data) {
        if (root == 0)
            root = ++cnt; //开辟新节点
        if (l == r) {
            t[root].data += data;
            return root;
        }
        if (pos <= mid)
            lson = update(lson, l, mid, pos, data);
        else
            rson = update(rson, mid + 1, r, pos, data);
        t[root].data = t[lson].data + t[rson].data;
        return root; //返回地址
    }

    ll query(ll root, ll l, ll r, ll x, ll y) {
        ll ret = 0;
        if (root == 0)
            return 0;
        if (x <= l && r <= y)
            return t[root].data;
        if (x <= mid)
            ret += query(lson, l, mid, x, y);
        if (y >= mid + 1)
            ret += query(rson, mid + 1, r, x, y);
        return ret;
    }
} Tree;//root[i] = Tree.update(root[i], 1, n, l, r);

可持久化数组

通常有 build 操作。一次单点修改，最多会让一个线段树上 \(\log ⁡n\) 个节点发生改变，相邻历史版本其余的点可以共用。这样一次更改的时间复杂度是 \(\log ⁡n\)，所用空间也是 \(\log ⁡n\)。

新产生的节点中，只有一个儿子是新的，另一个儿子一定指向上一版本的儿子，从而实现共享。 虽然每个节点可能出现多个父亲，但线段树中，我们都是找儿子节点，不会出现错误。

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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N = 1000000 + 10;
ll n, m, a[N], root[N], cnt;

struct SGT {
    struct node {
        int lson, rson, data;
    } t[N * 30];

#define lson t[root].lson
#define rson t[root].rson
#define mid ((l+r)/2)

    int clone(int pos) {
        t[++cnt] = t[pos];
        return cnt;
    }

    int build(int root, int l, int r, int a[]) {
        root = ++cnt;
        if (l == r) {
            t[root].data = a[l];
            return root;
        }
        lson = build(lson, l,mid, a);
        rson = build(rson,mid + 1, r, a);
        return root;
    }

    int update(int root, int l, int r, int pos, int data) {
        root = clone(root); //克隆一个点，现在它们暂时左右儿子公有
        if (l == r) {
            t[root].data = data;
            return root;
        }
        if (pos <= mid)
            lson = update(lson, l,mid, pos, data);
        else
            rson = update(rson,mid + 1, r, pos, data);
        return root;
    }

    int query(int root, int l, int r, int pos) {
        if (l == r)
            return t[root].data;
        if (pos <= mid)
            return query(lson, l,mid, pos);
        else
            return query(rson,mid + 1, r, pos);
    }
} Tree;

int main() {
    int t1, t2, t3, t4;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    root[0] = Tree.build(root[0], 1, n, a);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &t1, &t2, &t3);
        if (t2 == 1) {
            scanf("%d", &t4);
            root[i] = Tree.update(root[t1], 1, n, t3, t4);
        } else {
            printf("%d\n", Tree.query(root[t1], 1, n, t3));
            root[i] = root[t1];
        }
    }
    return 0;
}

主席树

静态区间第 \(k\) 小。对于原序列的每一个前缀 $ [1…i]$ 建立出一棵值域线段树维护各个数出现次数，则其树是可减的。主席树的每个节点保存的是一棵线段树，维护的区间信息，结构相同，具有可加减性（关键），利用可加减性同时行动。充分利用共同数据来减少时间和内存消耗。

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
#include<bits/stdc++.h>
#define mid ((l+r)/2)
using namespace std;

const int N = 1000000 + 10;
int n, m, a[N], rnk[N], root[N], cnt = 0, end;

struct SGT {
    struct node {
        int lson, rson, size;
    } t[N * 30];

    int clone(int pos) //继承上一个历史版本节点，再更新本次历史版本的信息
    {
        t[++cnt] = t[pos];
        t[cnt].size++; //树节点维护元素个数
        return cnt;
    }

    int build(int root, int l, int r) {
        root = ++cnt;
        if (l == r)
            return root;
        t[root].lson = build(t[root].lson, l,mid);
        t[root].rson = build(t[root].rson,mid + 1, r);
        return root;
    }

    int update(int pre, int l, int r, int pos) {
        int root = clone(pre);
        if (l == r)
            return root;
        if (pos <= mid)
            t[root].lson = update(t[root].lson, l,mid, pos);
        else
            t[root].rson = update(t[root].rson,mid + 1, r, pos);
        return root;
    }

    int query(int x, int y, int l, int r, int rnk) {
        //线段树上二分
        if (l == r)
            return l;//返回坐标 l
        int Lsize = t[t[y].lson].size - t[t[x].lson].size;
        if (rnk <= Lsize)
            return query(t[x].lson, t[y].lson, l, mid, rnk);
        else
            return query(t[x].rson, t[y].rson, mid + 1, r, rnk - Lsize);
    }
} Tree;

int main() {
    int t1, t2, t3;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        rnk[i] = a[i];
    }
    sort(rnk + 1, rnk + 1 + n);
    end = unique(rnk + 1, rnk + 1 + n) - (rnk + 1); //离散化
    root[0] = Tree.build(root[0], 1, end); //建初始版本树
    for (int i = 1; i <= n; i++) //建各历史版本树
    {
        int t1 = lower_bound(rnk + 1, rnk + 1 + end, a[i]) - rnk;
        root[i] = Tree.update(root[i - 1], 1, end, t1);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &t1, &t2, &t3);
        t3 = Tree.query(root[t1 - 1], root[t2], 1, end, t3);
        printf("%d\n", rnk[t3]); //注意输出对象
    }
    return 0;
}

树套树

现在给出 \(1∼n\) 的一个排列，按照某种顺序依次删除 \(m\) 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

每个树状数组的节点都是一棵权值线段树，可以维护树状数组管辖的区间中，大小范围处于 \([L,R]\) 的数字个数。

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
#include<bits/stdc++.h>
using namespace std;

//树状数组套动态开点线段树
typedef int ll;
const ll N = 100000 + 10, M = 1000000000;
ll cnt = 0, n, m, pos[N], root[N];
long long ans = 0, del = 0;

struct SGT {
    struct node {
        int lson, rson, data;
    } t[N * 30 * 30];

#define lson t[root].lson
#define rson t[root].rson
#define mid ((l+r)/2)

    ll update(ll root, ll l, ll r, ll pos, ll data) {
        if (root == 0)
            root = ++cnt;
        if (l == r && r == pos) {
            t[root].data += data;
            return root;
        }
        if (pos <= mid)
            lson = update(lson, l,mid, pos, data);
        else
            rson = update(rson,mid + 1, r, pos, data);
        t[root].data = t[lson].data + t[rson].data;
        return root;
    }

    ll query(ll root, ll l, ll r, ll x, ll y) {
        ll ret = 0;
        if (root == 0)
            return 0;
        if (x <= l && r <= y)
            return t[root].data;
        if (x <= mid)
            ret += query(lson, l,mid, x, y);
        if (y >= mid + 1)
            ret += query(rson,mid + 1, r, x, y);
        return ret;
    }
} Tree;

ll lb(ll x) { return x & -x; }

ll query(ll rt, ll x, ll y) {
    ll ret = 0;
    while (rt >= 1) {
        ret += Tree.query(root[rt], 1, n, x, y);
        rt -= lb(rt);
    }
    return ret;
}

void update(ll rt, ll x, ll data) {
    while (rt <= n) {
        root[rt] = Tree.update(root[rt], 1, n, x, data);
        rt += lb(rt);
    }
}

int main() {
    ll tmp, root;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tmp);
        pos[tmp] = i;
        ans += query(i - 1, tmp + 1, n);
        update(i, tmp, 1);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &tmp);
        printf("%lld\n", ans);
        root = pos[tmp];
        del = 0;
        del += query(root - 1, tmp + 1, n);
        del += query(n, 0, tmp - 1); //由于树状数组维护的是前缀和，
        del -= query(root, 0, tmp - 1); //所以这样搞。
        ans -= del;
        update(root, tmp, -1);
    }
    return 0;
}

树链剖分

对一棵树分成几条链，把树形变为线性，减少处理难度。链加、链查询，子树加、子树查询。

只有链可以倍增，只有子树可以 dfs 序。

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
#include <bits/stdc++.h>
using namespace std;
// #define int long long
//树链剖分

int p;
const int N = 100005;
int nn, a[N], sum[4 * N], lz[4 * N];
vector<int> m[N];
//父亲 深度 子树大小 重儿子
int father[N], dep[N], siz[N], son[N]; //第一次dfs处理的数据
//重链顶端 dfs序 用来记录dfs序的数
int top[N], dfn[N], num = 1; //第二次dfs处理的数据

void build(int n, int l, int r) {
    if (l == r) {
        sum[n] = a[r];
        return;
    }
    int mid = (l + r) >> 1;
    build(2 * n, l, mid);
    build(2 * n + 1, mid + 1, r);
    sum[n] = sum[2 * n] + sum[2 * n + 1];
    sum[n] %= p;
    return;
}

int search(int n, int l, int r, int x, int y) {
    if (x <= l && y >= r) { return sum[n]; }
    int mid = (l + r) >> 1;
    lz[2 * n] += lz[n];
    lz[2 * n + 1] += lz[n];
    sum[2 * n] += lz[n] * (mid - l + 1);
    sum[2 * n + 1] += lz[n] * (r - mid);
    lz[n] = 0;
    int ans = 0;
    if (x <= mid) {
        ans += search(2 * n, l, mid, x, y);
    }
    if (y > mid) {
        ans += search(2 * n + 1, mid + 1, r, x, y);
    }
    return ans % p;
}

void update(int n, int l, int r, int x, int y, int k) {
    if (x <= l && y >= r) {
        lz[n] += k;
        sum[n] += k * (r - l + 1);
        return;
    }
    int mid = (l + r) >> 1;
    lz[2 * n] += lz[n];
    lz[2 * n + 1] += lz[n];
    sum[2 * n] += lz[n] * (mid - l + 1);
    sum[2 * n + 1] += lz[n] * (r - mid);
    lz[n] = 0;
    if (x <= mid) {
        update(2 * n, l, mid, x, y, k);
    }
    if (y > mid) {
        update(2 * n + 1, mid + 1, r, x, y, k);
    }
    sum[n] = sum[2 * n] + sum[2 * n + 1];
    sum[n] %= p;
    return;
}

void dfs1(int x, int f, int d) {
    father[x] = f;
    dep[x] = d;
    siz[x] = 1;
    for (int c: m[x]) {
        if (c != f) {
            dfs1(c, x, d + 1);
            siz[x] += siz[c];
            if (siz[c] > siz[son[x]]) {
                son[x] = c;
            }
        }
    }
    return;
}

void dfs2(int x, int t) {
    top[x] = t;
    dfn[x] = num++;
    if (son[x] == 0)return;
    dfs2(son[x], t);
    for (int c: m[x]) {
        if (c != son[x] && c != father[x]) {
            dfs2(c, c);
        }
    }
    return;
}

void updRange(int x, int y, int k) {
    while (top[x] != top[y]) {
        //直到两点在同一条链
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        update(1, 1, nn, dfn[top[x]], dfn[x], k);
        x = father[top[x]];
    }
    if (dep[x] > dep[y])swap(x, y);
    update(1, 1, nn, dfn[x], dfn[y], k);
    return;
}

int qRange(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        //直到两点在同一条链
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        ans += search(1, 1, nn, dfn[top[x]], dfn[x]);
        x = father[top[x]];
    }
    if (dep[x] > dep[y])swap(x, y);
    ans += search(1, 1, nn, dfn[x], dfn[y]);
    return ans % p;
}

void updSon(int x, int k) {
    update(1, 1, nn, dfn[x], dfn[x] + siz[x] - 1, k);
}

int qSon(int x) {
    return search(1, 1, nn, dfn[x], dfn[x] + siz[x] - 1) % p;
}

signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int n, t, r;
    cin >> n >> t >> r >> p;
    nn = n;
    int aa[n + 1]; //用来临时储存点权，因为dfn序还没排好
    for (int i = 1; i <= n; i++) {
        cin >> aa[i];
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        m[x].push_back(y);
        m[y].push_back(x);
    }
    dfs1(r, 0, 1);//r是根节点
    dfs2(r, r);
    //把aa的数据给到a
    for (int i = 1; i <= n; i++) {
        a[dfn[i]] = aa[i] % p;
    }
    build(1, 1, n);
    //初始化over
    while (t--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            //从x到y的路劲+k
            int x, y, k;
            cin >> x >> y >> k;
            updRange(x, y, k % p);
        } else if (opt == 2) {
            //查询从x到y的路劲的和
            int x, y;
            cin >> x >> y;
            cout << qRange(x, y) << endl;
        } else if (opt == 3) {
            //x的子树都+k
            int x, k;
            cin >> x >> k;
            updSon(x, k % p);
        } else if (opt == 4) {
            //查询x的子树的和
            int x;
            cin >> x;
            cout << qSon(x) << endl;
        }
    }
    return 0;
}

平衡树

这里使用的是 FHQ-Treap。

split 实现集合操作

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 2e6 + 10;

struct Node {
    ll l, r; // 左右儿子编号
    ll val;  // 权值（BST 关键字）
    ll pri;  // 随机优先级（堆关键字）
    ll sz;   // 子树大小
} t[N];

ll tot = 0, root = 0;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 新建一个值为 v 的结点，返回它的编号
ll newNode(ll v) {
    ++tot;
    t[tot].l = t[tot].r = 0;
    t[tot].val = v;
    t[tot].pri = rng() & 0x7fffffff;
    t[tot].sz = 1;
    return tot;
}

// 用左右儿子的信息更新当前结点 p 的子树大小
void pushup(ll p) { t[p].sz = t[t[p].l].sz + t[t[p].r].sz + 1; }

// ============ 核心操作一：split（按值分裂） ============
// 把以 p 为根的子树拆成两棵：
//   a 中所有结点的 val <= v
//   b 中所有结点的 val >  v
// p: 当前子树根,  v: 分界值,  a/b: 输出参数
void split(ll p, ll v, ll &a, ll &b) {
    if (!p) {
        a = b = 0;
        return;
    } // 空树，两边都空
    if (t[p].val <= v) { // 根 <= v，根属于 a
        a = p;
        split(t[p].r, v, t[p].r, b); // 但右子树里可能还有 > v 的，继续拆
    } else {                         // 根 > v，根属于 b
        b = p;
        split(t[p].l, v, a, t[p].l); // 但左子树里可能还有 <= v 的，继续拆
    }
    pushup(p); // 更新子树大小
}

// ============ 核心操作二：merge（合并） ============
// 把 a、b 两棵树合并成一棵，前提：a 中所有值都小于 b 中所有值
// 做法：比较两个根的 pri，谁大谁当新根，然后递归合并
ll merge(ll a, ll b) {
    if (!a || !b)
        return a ? a : b;          // 有一边空，直接返回另一边
    if (t[a].pri > t[b].pri) {     // a 的优先级大，a 当根
        t[a].r = merge(t[a].r, b); // b 整体去和 a 的右子树合并
        pushup(a);
        return a;
    } else {                       // b 的优先级大，b 当根
        t[b].l = merge(a, t[b].l); // a 整体去和 b 的左子树合并
        pushup(b);
        return b;
    }
}

// ============ 六大操作：全部用 split / merge 拼出来 ============

// 1. 插入 v
void insert(ll v) {
    ll a, b;
    split(root, v, a, b); // a: <= v, b: > v
    root = merge(merge(a, newNode(v)), b);
}

// 2. 删除一个 v
void erase(ll v) {
    ll a, b, c;
    split(root, v, a, b);      // a: <= v, b: > v
    split(a, v - 1, a, c);     // a: < v,  c: == v
    c = merge(t[c].l, t[c].r); // 丢掉 c 的根节点（即删掉一个 v）
    root = merge(merge(a, c), b);
}

// 3. 查询 v 的排名（比 v 小的个数 + 1）
ll getRank(ll v) {
    ll a, b;
    split(root, v - 1, a, b); // a: < v
    ll ans = t[a].sz + 1;
    root = merge(a, b);
    return ans;
}

// 4. 查询第 k 小（不需要 split，直接在树上走，像 BST 上找第 k 小）
ll kth(ll k) {
    ll p = root;
    while (p) {
        ll ls = t[t[p].l].sz;
        if (k <= ls)
            p = t[p].l; // 在左子树
        else if (k == ls + 1)
            return t[p].val; // 就是根
        else {
            k -= ls + 1;
            p = t[p].r;
        } // 在右子树
    }
    return -1;
}

// 5. 前驱（小于 v 的最大值）
ll getPre(ll v) {
    ll a, b;
    split(root, v - 1, a, b); // a: < v
    ll p = a;
    while (t[p].r)
        p = t[p].r; // 一直往右走就是最大值
    ll ans = t[p].val;
    root = merge(a, b);
    return ans;
}

// 6. 后继（大于 v 的最小值）
ll getNxt(ll v) {
    ll a, b;
    split(root, v, a, b); // b: > v
    ll p = b;
    while (t[p].l)
        p = t[p].l; // 一直往左走就是最小值
    ll ans = t[p].val;
    root = merge(a, b);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n, m, last = 0, ans = 0;
    cin >> n >> m;
    for (ll i = 1, a; i <= n; i++) {
        cin >> a;
        insert(a);
    }
    while (m--) {
        ll op, x;
        cin >> op >> x;
        x ^= last;
        if (op == 1) {
            insert(x);
        } else if (op == 2) {
            erase(x);
        } else if (op == 3) {
            last = getRank(x);
            ans ^= last;
        } else if (op == 4) {
            last = kth(x);
            ans ^= last;
        } else if (op == 5) {
            last = getPre(x);
            ans ^= last;
        } else {
            last = getNxt(x);
            ans ^= last;
        }
    }
    cout << ans << endl;
    return 0;
}

splitK 实现区间操作

这里实现的是区间翻转，需要类似于线段树的懒标记和 pushdown 操作。

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 <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 1e5 + 10;

struct Node {
    ll l, r;
    ll val;
    ll pri;
    ll sz;
    bool rev;
} t[N];

ll tot = 0, root = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll newNode(ll v) {
    ++tot;
    t[tot].l = t[tot].r = 0;
    t[tot].val = v;
    t[tot].pri = rng() & 0x7fffffff;
    t[tot].sz = 1;
    t[tot].rev = false;
    return tot;
}

void pushup(ll p) { t[p].sz = t[t[p].l].sz + t[t[p].r].sz + 1; }

void pushdown(ll p) {
    if (!t[p].rev)
        return;
    swap(t[p].l, t[p].r);
    if (t[p].l)
        t[t[p].l].rev ^= 1;
    if (t[p].r)
        t[t[p].r].rev ^= 1;
    t[p].rev = false;
}

void splitK(ll p, ll k, ll &a, ll &b) {
    if (!p) {
        a = b = 0;
        return;
    }
    pushdown(p);
    if (t[t[p].l].sz < k) {
        a = p;
        splitK(t[p].r, k - t[t[p].l].sz - 1, t[p].r, b);
    } else {
        b = p;
        splitK(t[p].l, k, a, t[p].l);
    }
    pushup(p);
}

ll merge(ll a, ll b) {
    if (!a || !b)
        return a ? a : b;
    if (t[a].pri > t[b].pri) {
        pushdown(a);
        t[a].r = merge(t[a].r, b);
        pushup(a);
        return a;
    } else {
        pushdown(b);
        t[b].l = merge(a, t[b].l);
        pushup(b);
        return b;
    }
}

// 如果要在任意位置 k 插入（1-indexed，插到第 k 个位置）
void insertAt(ll k, ll v) {
    ll a, b;
    splitK(root, k - 1, a, b);
    root = merge(merge(a, newNode(v)), b);
}

void reverse(ll l, ll r) {
    ll a, b, c;
    splitK(root, l - 1, a, b);
    splitK(b, r - l + 1, b, c);
    t[b].rev ^= 1;
    root = merge(merge(a, b), c);
}

void inorder(ll p) {
    if (!p)
        return;
    pushdown(p);
    inorder(t[p].l);
    cout << t[p].val << ' ';
    inorder(t[p].r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    for (ll i = 1; i <= n; i++) {
        root = merge(root, newNode(i)); // 每次接到末尾
    }
    while (m--) {
        ll l, r;
        cin >> l >> r;
        reverse(l, r);
    }

    inorder(root);
    cout << '\n';
    return 0;
}

这里实现的是动态数组（增、删、访问都是 \(O(\log n)\)）。

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
// 随机访问 a[i]
int get(int i) {
    int p = root;
    while (p) {
        int ls = t[t[p].l].sz;
        if (i == ls + 1) return t[p].val;
        if (i <= ls) p = t[p].l;
        else { i -= ls + 1; p = t[p].r; }
    }
    return -1;
}

// a[i] = v
void set(int i, int v) {
    int a, b, c;
    splitK(root, i - 1, a, b);
    splitK(b, 1, b, c);
    t[b].val = v;
    root = merge(merge(a, b), c);
}

// 在位置 i 处插入 v（v 成为第 i 个元素）
void insert(int i, int v) {
    int a, b;
    splitK(root, i - 1, a, b);
    root = merge(merge(a, newNode(v)), b);
}

// 删除位置 i 的元素
void erase(int i) {
    int a, b, c;
    splitK(root, i - 1, a, b);
    splitK(b, 1, b, c);
    root = merge(a, c);
}

// 末尾追加
void push_back(int v) {
    root = merge(root, newNode(v));
}

int size() { return t[root].sz; }

// 输出整个数组（中序遍历）
void print(int p, vector<int>& out) {
    if (!p) return;
    print(t[p].l, out);
    out.push_back(t[p].val);
    print(t[p].r, out);
}