主页
归档
朋友
关于

fhq Treap与区间操作

​ 前段时间在机房里几个大爷的墙裂安利下学了发fhq treapfhq\ treap 于是就顺带着把fhq treapfhq\ treap的区间操作给学了（比SplaySplay的好理解多了）

似乎这么一点字太少了？那我放张图=-=

Ⅰ前置芝士 —— fhq Treap （非旋Treap）

我这篇文章是来讲区间操作的

不是来教你fhq treap的

所以你如果不会fhq treap的话自己找别的讲稿把

其实主要是因为我自己一大半也是感性理解的啦

好吧还是贴个代码把

咳咳咳，没错，所以这个部分就是让你们来背代码的

mergemerge

merge(a,b)merge(a, b)的作用就是把根为b的树向根为a的树合并，并且返回合并出来的树的根。

1
2
3
4
5
6
7
8
9
10
11
12
13
int merge(int a, int b){
    if(a == 0 || b == 0)
        return a + b;
    if(t[a].w > t[b].w){
        t[a].rc = merge(t[a].rc, b);
        push_up(a);
        return a;
    } else {
        t[b].lc = merge(a, t[b].lc);
        push_up(b);
        return b;
    }
}

恩，就这么短。

splitsplit

split(a,b,c,d)split(a, b, c, d)的作用是把根为a的子树分裂成两棵树c,dc, d，并且cc子树中是前bb个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void split(int cur, int k, int &a, int &b){
    if(cur == 0){
        a = b = 0;
        return ;
    }
    if(k <= t[t[cur].lc].size){
        b = cur;
        split(t[cur].lc, k, a, t[b].lc);
        push_up(b);
    } else {
        a = cur;
        split(t[cur].rc, k - t[t[cur].lc].size - 1, t[a].rc, b);
        push_up(a);
    }
}

其他核心操作？tan⁡90o\tan 90^{\text{o}}。

因为fhq treapfhq\ treap 的核心操作就这俩玩意儿。

Ⅱ 如何操作

显然，如果你要对一个区间进行操作，你就得先从它的根节点开始搞事情

那么你如何获得它的根节点呢？

如果你要操作一个[l,r][l, r]的区间

不管你怎么操作

肯定存在一个很方便的办法：弄出来一个表示[l,r][l, r]这个区间的子树。

说到子树，如果你学懂了fhqfhq，那么你肯定能想到splitsplit操作

说到split，我就想到了唐僧与世俗split开去西天取经，明年年初，中美合拍，文体两开花，关注，谢谢支持。

在前一行，你什么都没看到，恩，就这样。

（瞬间正经）好，我们考虑如何splitsplit出来表示[l,r][l , r]区间的子树。

首先，我们首先splitsplit出来一个sizesize为l−1l - 1的子树，那剩下了第二棵子树，那么第二棵子树代表的显然就是[l,n][l, n]，然后你再splitsplit出来一个sizesize为r−l+1r - l + 1的子树，那么你这次splitsplit出来的子树代表的区间就是[l,r][l, r]啦

操作完之后我们就会得到3棵子树，你在第二棵上面做玩你想要的操作之后把子树mergemerge回去就行了

比方说区间翻转的代码长这样↓

1
2
3
4
5
6
7
8
void reverse(int l, int r){
    int x, y, z;
    split(root, l - 1, x, y);
    int rt = y;
    split(rt, r - l + 1, y, z);
    t[y].lazy ^= 1;
    root = merge(x, merge(y, z));
}

关于区间翻转的操作我会在下面讲↓

Ⅲ 例题

洛谷P3391 【模板】文艺平衡树（Splay）

原题：>Here<

这边的区间翻转我们应当用打懒标的方式实现，然后每次操作的时候记得pushdownpushdown一下就行啦

怎么得到区间刚刚已经讲过了

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

#define ll long long
#define INF 2147483647

inline int inp(){
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum;
}

struct fhq_Treap{
    struct T{
        int lc;
        int rc;
        bool lazy;
        int size;
        int w;
        int v;
    }t[100010];
    int root;
    int cnt;
    void init(){
        root = cnt = 0;
        t[0].lc = t[0].rc = t[0].lazy = t[0].size = 0;
    }

    inline void push_up(int cur){
        t[cur].size = t[t[cur].lc].size + t[t[cur].rc].size + 1;
    }

    inline void push_down(int cur){
        if(!t[cur].lazy)
            return ;
        std::swap(t[cur].lc, t[cur].rc);
        t[t[cur].lc].lazy ^= 1;
        t[t[cur].rc].lazy ^= 1;
        t[cur].lazy = false;
    }

    void split(int cur, int k, int &x, int &y){
        push_down(cur);
        if(cur == 0){
            x = y = 0;
            return ;
        }
        if(t[t[cur].lc].size >= k){
            y = cur;
            split(t[cur].lc, k, x, t[y].lc);
            push_up(y);
        } else {
            x = cur;
            split(t[cur].rc, k - t[t[cur].lc].size - 1, t[x].rc, y);
            push_up(x);
        }
    }

    int merge(int x, int y){
        if(x == 0)
            return y;
        if(y == 0)
            return x;
        push_down(x);
        push_down(y);
        if(t[x].w > t[y].w){
            t[x].rc = merge(t[x].rc, y);
            push_up(x);
            return x;
        } else {
            t[y].lc = merge(x, t[y].lc);
            push_up(y);
            return y;
        }
    }

    void reverse(int l, int r){
        int x, y, z;
        split(root, l - 1, x, y);
        int rt = y;
        split(rt, r - l + 1, y, z);
        t[y].lazy ^= 1;
        // printf("finished split phase.\n");
        // printf("%d %d, %d\n", x, y, z);
        rt = merge(y, z);
        // print(rt);
        root = merge(x, rt);
        // printf("completed reverse.\n");
    }

    inline void insert(int x){
        t[++cnt].lazy = false;
        t[cnt].size = 1;
        t[cnt].w = rand();
        t[cnt].v = x;
        t[cnt].lc = t[cnt].rc = 0;
        root = merge(root, cnt);
    }

    void print(int cur){
        if(cur == 0)
            return ;
        push_down(cur);
        print(t[cur].lc);
        printf("%d ", t[cur].v);
        print(t[cur].rc);
    }
}t;

int main(){
    t.init();
    int n = inp();
    int m = inp();
    for(int i = 1; i <= n; i++)
        t.insert(i);
    for(int i = 1; i <= m; i++){
        int l = inp();
        int r = inp();
        // t.print(t.root);
        // putchar('\n');
        t.reverse(l, r);
    }
    t.print(t.root);
}

SP4350 QMAX3VN - Giá trị lớn nhất 3

原题：>Here<

这题luogu上面没法用C艹交

但是fhq treap 这种一堆取址的东西用C弄超级麻烦

于是我贡献了大量的CE与UKE

好的，这题要求资瓷插入以及查询区间最大值

然后插入的话我们split两棵子树，mergemerge的时候把新加的元素当做一棵子树并在中间就行了

节点上维护区间最大值就OK了

还是很简单的

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

#define ll long long
#define INF 2147483647

inline ll inp(){
    char c = getchar();
    ll neg = 1;
    while(c < '0' || c > '9'){
        if(c == '-')
            neg = -1;
        c = getchar();
    }
    ll sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum * neg;
}

struct fhq_Treap{
    struct T{
        ll max;
        ll lc;
        ll rc;
        ll size;
        ll v;
        ll w;
    }t[200010];
    ll cnt, root;
    void init(){
        root = cnt = 0;
        t[0] = {-INF, 0, 0, 0, 0, 0};
    }

    ll create(ll v){
        ll v0 = std::max(v, 0ll);
        t[++cnt] = {v, 0, 0, 1, v, rand()};
        return cnt;
    }

    void push_up(ll cur){
        t[cur].max = std::max(t[cur].v, std::max(t[t[cur].lc].max, t[t[cur].rc].max));
        t[cur].size = t[t[cur].lc].size + t[t[cur].rc].size + 1;
        // printf("cur = %lld, max = %lld\n", cur, t[cur].max);
    }

    ll merge(ll a, ll b){
        if(a == 0 || b == 0)
            return a + b;
        if(t[a].w > t[b].w){
            t[a].rc = merge(t[a].rc, b);
            push_up(a);
            return a;
        } else {
            t[b].lc = merge(a, t[b].lc);
            push_up(b);
            return b;
        }
    }

    void split(ll cur, ll k, ll &a, ll &b){
        if(cur == 0){
            a = b = 0;
            return ;
        }
        if(k <= t[t[cur].lc].size){
            b = cur;
            split(t[cur].lc, k, a, t[b].lc);
            push_up(b);
        } else {
            a = cur;
            split(t[cur].rc, k - t[t[cur].lc].size - 1, t[a].rc, b);
            push_up(a);
        }
    }

    void insert(ll pos, ll v){
        ll x, y;
        split(root, pos - 1, x, y);
        // printf("Insert x = %lld, y = %lld\n", x, y);
        root = merge(merge(x, create(v)), y);
    }

    void del(ll pos){
        ll x, y, z;
        split(root, pos - 1, x, y);
        split(y, 1, y, z);
        root = merge(x, z);
    }

    void prll(ll cur){
        if(cur == 0)
            return ;
        prll(t[cur].lc);
        // printf("t[%lld] v = %lld ls= %lld rs= %lld sum= %lld tot= %lld lc= %lld rc= %lld\n", cur, t[cur].v, t[cur].ls, t[cur].rs, t[cur].sum, t[cur].tot, t[cur].lc, t[cur].rc);
        printf("t[%lld] = lc = %lld, rc = %lld, max = %lld, v = %lld\n", cur, t[cur].lc, t[cur].rc, t[cur].max, t[cur].v);
        prll(t[cur].rc);
    }

    ll query(ll l, ll r){
        ll x, y, z;
        split(root, l - 1, x, y);
        split(y, r - l + 1, y, z);
        // prll(y);
        ll ret = t[y].max;
        root = merge(merge(x, y), z);
        return ret;
    }

    void build(ll x){
        root = merge(root, create(x));
    }
}t;

int main(){
    t.init();
    ll m = inp();
    // printf("%d\n", m);
    // t.prll(t.root);
    for(ll i = 1; i <= m; i++){
        char type = getchar();
        while(type != 'A' && type != 'Q')
            type = getchar();
        if(type == 'A'){
            ll x = inp();
            ll pos = inp();
            t.insert(pos, x);
        } else {
            ll l = inp();
            ll r = inp();
            printf("%lld\n", t.query(l, r));
        }
        // printf("i = %lld, finished %c\n", i, type);
    }
}

SP4487 GSS6 - Can you answer these queries VI

原题：>Here<

这题就比较毒瘤啦

资瓷区间查询最大子段和，插入，删除，修改。

区间最大字段和的话我们可以参照线段树做法，一个节点上维护左端点开始的，右端点开始的还有整个的最大字段和，以及区间的和。

pushuppushup因为两段元素中间还多了个自己这个节点，所以会麻烦不少

删除的时候只要splitsplit出来之后中间那段不mergemerge回去就行了

修改的时候只要把中间那段修改权值一下就行了

只是写完之后修锅要好长时间呢…

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

#define ll long long
#define INF 2147483647
#define int long long

inline int inp(){
    char c = getchar();
    int neg = 1;
    while(c < '0' || c > '9'){
        if(c == '-')
            neg = -1;
        c = getchar();
    }
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum * neg;
}

struct fhq_Treap{
    struct T{
        int ls;
        int rs;
        int sum;
        int tot;
        int lc;
        int rc;
        int size;
        int v;
        int w;
    }t[200010];
    int cnt, root;
    void init(){
        root = cnt = 0;
        t[0] = {0, 0, -INF, 0, 0, 0, 0, 0};
    }

    int create(int v){
        int v0 = std::max(v, 0ll);
        t[++cnt] = {v0, v0, v, v, 0, 0, 1, v, rand()};
        return cnt;
    }

    void push_up(int cur){
        if(t[cur].lc == 0 && t[cur].rc == 0){
            int v2 = std::max(t[cur].v, 0ll);
            t[cur].sum = t[cur].tot = t[cur].v;
            t[cur].ls = t[cur].rs = v2;
            t[cur].size = 1;
            return ;
        }
        t[cur].tot = t[t[cur].lc].tot + t[t[cur].rc].tot + t[cur].v;
        t[cur].ls = std::max(t[t[cur].lc].tot + t[cur].v + t[t[cur].rc].ls, t[t[cur].lc].ls);
        t[cur].rs = std::max(t[t[cur].rc].tot + t[cur].v + t[t[cur].lc].rs, t[t[cur].rc].rs);

        t[cur].sum = std::max(std::max(t[t[cur].lc].sum, t[t[cur].rc].sum), t[t[cur].lc].rs + t[cur].v + t[t[cur].rc].ls);
        t[cur].size = t[t[cur].lc].size + t[t[cur].rc].size + 1;
        // printf("push up %lld | max{%lld %lld %lld} = %d\n", cur, t[t[cur].lc].sum, t[t[cur].rc].sum, t[t[cur].lc].rs + t[cur].v + t[t[cur].rc].ls, t[cur].sum);
    }

    int merge(int a, int b){
        if(a == 0 || b == 0)
            return a + b;
        if(t[a].w > t[b].w){
            t[a].rc = merge(t[a].rc, b);
            push_up(a);
            return a;
        } else {
            t[b].lc = merge(a, t[b].lc);
            push_up(b);
            return b;
        }
    }

    void split(int cur, int k, int &a, int &b){
        if(cur == 0){
            a = b = 0;
            return ;
        }
        if(k <= t[t[cur].lc].size){
            b = cur;
            split(t[cur].lc, k, a, t[b].lc);
            push_up(b);
        } else {
            a = cur;
            split(t[cur].rc, k - t[t[cur].lc].size - 1, t[a].rc, b);
            push_up(a);
        }
    }

    void insert(int pos, int v){
        int x, y;
        split(root, pos - 1, x, y);
        // printf("Insert x = %lld, y = %lld\n", x, y);
        root = merge(merge(x, create(v)), y);
    }

    void modify(int pos, int v){
        int x, y, z;
        split(root, pos - 1, x, y);
        split(y, 1, y, z);
        int v0 = std::max(v, 0ll);
        t[y] = {v0, v0, v, v, 0, 0, 1, v, t[y].w};
        root = merge(merge(x, y), z);
    }

    void del(int pos){
        int x, y, z;
        split(root, pos - 1, x, y);
        split(y, 1, y, z);
        root = merge(x, z);
    }

    void print(int cur){
        if(cur == 0)
            return ;
        print(t[cur].lc);
        printf("t[%lld] v = %lld ls= %lld rs= %lld sum= %lld tot= %lld lc= %lld rc= %lld\n", cur, t[cur].v, t[cur].ls, t[cur].rs, t[cur].sum, t[cur].tot, t[cur].lc, t[cur].rc);
        print(t[cur].rc);
    }

    int query(int l, int r){
        int x, y, z;
        split(root, l - 1, x, y);
        split(y, r - l + 1, y, z);
        // print(y);
        int ret = t[y].sum;
        root = merge(merge(x, y), z);
        return ret;
    }

    void build(int x){
        root = merge(root, create(x));
    }
}t;

signed main(){
    t.init();
    int n = inp();
    for(int i = 1; i <= n; i++)
        t.build(inp());
    int m = inp();
    // printf("%d\n", m);
    // t.print(t.root);
    for(int i = 1; i <= m; i++){
        char type = getchar();
        while(type != 'I' && type != 'D' && type != 'R' && type != 'Q')
            type = getchar();
        if(type == 'I'){
            int pos = inp();
            int x = inp();
            t.insert(pos, x);
        } else if(type == 'D'){
            t.del(inp());
        } else if(type == 'R'){
            int pos = inp();
            int x = inp();
            t.modify(pos, x);
        } else {
            int l = inp();
            int r = inp();
            printf("%lld\n", t.query(l, r));
        }
        // printf("i = %lld, finished %c\n", i, type);
    }
}

[NOI2005]维护数列

原题：>Here<

这题可以认为就是前三题加起来了

不过有一点要注意

在维护最大字段和的时候如果左右子树是反的那么会导致错误

所以我们不能像我给的文艺平衡树板子那样子写区间翻转

具体怎么做还是看代码把（

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

#define ll long long
#define INF 2147483647

inline int inp(){
    char c = getchar();
    int neg = 1;
    while(c < '0' || c > '9'){
        if(c == '-')
            neg = -1;
        c = getchar();
    }
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum * neg;
}

struct fhq_Treap{
    struct T{
        int ls;
        int rs;
        int sum;
        int tot;
        int lc;
        int rc;
        int size;
        int v;
        int w;
        int lazy;
        bool reverse;
    }t[5000010];
    int cnt, root;
    void init(){
        root = cnt = 0;
        t[0] = (T){0, 0, -INF, 0, 0, 0, 0, 0, -INF, false};
    }

    int create(int v){
        int v0 = std::max(v, 0);
        t[++cnt] = (T){v0, v0, v, v, 0, 0, 1, v, rand(), -INF, false};
        return cnt;
    }

    void push_up(int cur){
        if(t[cur].lc == 0 && t[cur].rc == 0){
            int v2 = std::max(t[cur].v, 0);
            t[cur].sum = t[cur].tot = t[cur].v;
            t[cur].ls = t[cur].rs = v2;
            t[cur].size = 1;
            return ;
        }
        t[cur].tot = t[t[cur].lc].tot + t[t[cur].rc].tot + t[cur].v;
        t[cur].ls = std::max(t[t[cur].lc].tot + t[cur].v + t[t[cur].rc].ls, t[t[cur].lc].ls);
        t[cur].rs = std::max(t[t[cur].rc].tot + t[cur].v + t[t[cur].lc].rs, t[t[cur].rc].rs);

        t[cur].sum = std::max(std::max(t[t[cur].lc].sum, t[t[cur].rc].sum), t[t[cur].lc].rs + t[cur].v + t[t[cur].rc].ls);
        t[cur].size = t[t[cur].lc].size + t[t[cur].rc].size + 1;
        // printf("push up %d | max{%d %d %d} = %d\n", cur, t[t[cur].lc].sum, t[t[cur].rc].sum, t[t[cur].lc].rs + t[cur].v + t[t[cur].rc].ls, t[cur].sum);
    }

    inline void push_down(int cur){
		if(t[cur].lazy != -INF){
			int v0 = std::max(t[cur].lazy, 0);
			t[t[cur].lc].ls = t[t[cur].lc].rs = v0 * t[t[cur].lc].size;
			t[t[cur].rc].ls = t[t[cur].rc].rs = v0 * t[t[cur].rc].size;
			t[t[cur].lc].sum = std::max(t[cur].lazy, t[cur].lazy * t[t[cur].lc].size);
			t[t[cur].rc].sum = std::max(t[cur].lazy, t[cur].lazy * t[t[cur].rc].size);
			
			t[t[cur].lc].tot = t[cur].lazy * t[t[cur].lc].size;
			t[t[cur].rc].tot = t[cur].lazy * t[t[cur].rc].size;
			
			t[t[cur].lc].lazy = t[cur].lazy; 
			t[t[cur].rc].lazy = t[cur].lazy;
			t[t[cur].lc].v = t[t[cur].rc].v = t[cur].lazy;
			
			t[cur].lazy = -INF;
			t[cur].reverse = false; 
		}
		if(t[cur].reverse){
	        std::swap(t[t[cur].lc].lc, t[t[cur].lc].rc);
	        std::swap(t[t[cur].rc].lc, t[t[cur].rc].rc);
	        std::swap(t[t[cur].lc].ls, t[t[cur].lc].rs);
	        std::swap(t[t[cur].rc].ls, t[t[cur].rc].rs);
			t[t[cur].lc].reverse ^= 1;
	        t[t[cur].rc].reverse ^= 1;
	        t[cur].reverse = false;
		} 
        t[0] = (T){0, 0, -INF, 0, 0, 0, 0, 0, -INF, false};
    }

    int merge(int a, int b){
        if(a == 0 || b == 0)
            return a + b;
        push_down(a);
        push_down(b);
        if(t[a].w > t[b].w){
            t[a].rc = merge(t[a].rc, b);
            push_up(a);
            return a;
        } else {
            t[b].lc = merge(a, t[b].lc);
            push_up(b);
            return b;
        }
    }

    void split(int cur, int k, int &a, int &b){
        if(cur == 0){
            a = b = 0;
            return ;
        }
        push_down(cur);
        if(k <= t[t[cur].lc].size){
            b = cur;
            split(t[cur].lc, k, a, t[b].lc);
            push_up(b);
        } else {
            a = cur;
            split(t[cur].rc, k - t[t[cur].lc].size - 1, t[a].rc, b);
            push_up(a);
        }
    }

    void insert(int pos, int rt){
        int x, y;
        split(root, pos, x, y);
        root = merge(merge(x, rt), y);
    }

    void modify(int pos, int len, int v){
        int x, y, z;
        split(root, pos - 1, x, y);
        split(y, len, y, z);
        t[y].ls = t[y].rs = std::max(v, 0) * t[y].size;
        t[y].tot = t[y].size * v;
    	t[y].sum = std::max(v, v * t[y].size);
    	t[y].lazy = v;
    	t[y].v = v;
        root = merge(merge(x, y), z);
    }

    void del(int pos, int len){
        int x, y, z;
        split(root, pos - 1, x, y);
        split(y, len, y, z);
        root = merge(x, z);
    }

    void print(int cur){
        if(cur == 0)
            return ;
        push_down(cur);
        print(t[cur].lc);
        printf("t[%d] v = %d ls= %d rs= %d sum= %d tot= %d lc= %d rc= %d\n", cur, t[cur].v, t[cur].ls, t[cur].rs, t[cur].sum, t[cur].tot, t[cur].lc, t[cur].rc);
        print(t[cur].rc);
        push_up(cur);
    }

    int query(int l, int len){
        int x, y, z;
        split(root, l - 1, x, y);
        split(y, len, y, z);
        // print(y);
        int ret = t[y].tot;
        root = merge(merge(x, y), z);
        return ret;
    }

    void build(int x){
        root = merge(root, create(x));
    }
    
    void reverse(int pos, int len){
    	int x, y, z;
    	split(root, pos - 1, x, y);
    	split(y, len, y, z);
    	t[y].reverse ^= 1;
    	std::swap(t[y].lc, t[y].rc);
    	std::swap(t[y].ls, t[y].rs);
    	root = merge(merge(x, y), z);
    }
}t;

signed main(){
    t.init();
    int n = inp();
    int m = inp();
    for(int i = 1; i <= n; i++)
        t.build(inp());
    // printf("%d\n", m);
    // t.print(t.root);
    char type[20];
    for(int i = 1; i <= m; i++){
        scanf("%s", type);
		if(type[0] == 'I'){
			int pos = inp();
			int cnt = inp();
			std::vector <int> vec;
			int rt = 0;
			for(int j = 1; j <= cnt; j++)
				rt = t.merge(rt, t.create(inp()));
            t.insert(pos, rt);
        } else if(type[0] == 'D'){
            int l = inp();
            int len = inp();
			t.del(l, len);
        } else if(type[0] == 'R'){
            int pos = inp();
            int len = inp();
            t.reverse(pos, len);
        } else if(type[0] == 'M' && type[2] == 'K'){
            int pos = inp();
            int len = inp();
            int x = inp();
            t.modify(pos, len, x);
		} else if(type[0] == 'G'){
			int pos = inp();
			int len = inp();
			printf("%d\n", t.query(pos, len));
		} else {
            printf("%d\n", t.t[t.root].sum);
        }
        // t.print(t.root);
        // putchar('\n');
    }
}

Ⅳ 与其他相似算法的比较

Splay

Splay的作用跟fhq Treapfhq\ Treap差不多，都是可以维护区间操作，但是个人认为fhqfhq优于SplaySplay，理由有二

  • 好写，代码短
  • 易于理解

而且，fhqfhq的常数跟SplaySplay差不多

但是fhqfhq的缺点也是显著，就是不能写LCT。

其他平衡树

不得不说fhqfhq和SplaySplay两个可以维护区间操作的平衡树在常数方面完全可以以变态大的常数打爆其他平衡树（甚至包括setset）

所以，如果不写区间操作，setset都比fhqfhq快。

完结撒花～～


QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动，使用 Azurus 作为主题。