Luogu P2234+P2286 (Splay性质

Luogu P2234

  • 记住性质才能更好利用: Splay的查询前驱和后继操作
    • $tree.ins(val)$插入后会$Splay$到根节点
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5+10;

int rt,tot,fa[maxn],ch[maxn][2],cnt[maxn],size[maxn];
int val[maxn];

struct Splay {
    void maintain(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x]; }
    bool get(int x) { return x == ch[fa[x]][1]; }
    void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = size[x] = cnt[x] = 0; }

    // 向右旋转
    void rotate(int x) {
        int y = fa[x],z=fa[y],chk=get(x);
        ch[y][chk] = ch[x][chk^1];
        fa[ch[x][chk^1]] = y;

        ch[x][chk^1] = y;
        fa[y] = x;

        fa[x] = z;
        if (z) ch[z][y == ch[z][1]] = x;

        maintain(y);
        maintain(x);
    }
    void splay(int x) {
        for (int f=fa[x]; f=fa[x],f; rotate(x))
            if (fa[f]) rotate(get(x) == get(f) ? f : x);
        rt = x;
    }
    void ins(int k) {
        // 树为空 插入到根节点
        if (!rt) {
            val[++tot] = k;
            cnt[tot]++;
            rt = tot;
            maintain(rt);
            return ;
        }
        int cnr = rt,f = 0;
        while (1) {
            // 恰好k == 当前值
            if (val[cnr] == k) {
                cnt[cnr]++;
                maintain(cnr);
                maintain(f);
                splay(cnr);
                break;
            }
            f = cnr;
            // 判断去左树还是右树
            cnr = ch[cnr][val[cnr] < k];
            // 到了叶节点,插入新的节点
            if (!cnr) {
                val[++tot] = k;
                cnt[tot]++;
                fa[tot] = f;
                ch[f][val[f] < k] = tot;

                maintain(tot);
                maintain(f);
                splay(tot);
                break;
            }
        }
    }
    // 给一个数k 查它的排名
    int rk(int k) {
        int res = 0,cnr = rt;
        while (1) {
            if (k < val[cnr])
                cnr = ch[cnr][0];
            else {
                res += size[ch[cnr][0]];
                if (k == val[cnr]) {
                    splay(cnr);
                    return res+1;
                }
                // 加上该节点的值
                res += cnt[cnr];
                cnr = ch[cnr][1];
            }
        }
    }
    // 给出排名k, 查询数
    int kth(int k) {
        int cnr = rt;
        while (1) {
            if (ch[cnr][0] && k <= size[ch[cnr][0]])
                cnr = ch[cnr][0];
            else {
                k -= size[ch[cnr][0]] + cnt[cnr];
                if (k <= 0) return val[cnr];
                cnr = ch[cnr][1];
            }
        }
    }
    // 根节点左子树最大值
    int pre() {
        int cnr = ch[rt][0];
        while(ch[cnr][1]) cnr = ch[cnr][1];
        return cnr;
    }
    // 根节点右子树最小值
    int nxt() {
        int cnr = ch[rt][1];
        while(ch[cnr][0]) cnr = ch[cnr][0];
        return cnr;
    }
    // 删除 值为k的节点
    void del(int k) {
        // 查k的排名将它旋转到根节点
        rk(k);
        // 多个k, 减去一个然后退出
        if (cnt[rt] > 1) {
            cnt[rt]--;
            maintain(rt);
            return ;
        }
        // 子节点都不存在
        if (!ch[rt][0] && !ch[rt][1]) {
            clear(rt);
            rt = 0;
            return ;
        }
        // 左节点不存在
        if (!ch[rt][0]) {
            int cnr = rt;
            rt = ch[rt][1];
            fa[rt] = 0;
            clear(cnr);
            return ;
        }
        // 右节点不存在
        if (!ch[rt][1]) {
            int cnr = rt;
            rt = ch[rt][0];
            fa[rt] = 0;
            clear(cnr);
            return ;
        }
        // 否则将x的左子树最大值旋转上来作为新 ,删除根节点后右子树接上来
        int x = pre(),cnr = rt;
        splay(x);
        // 修改原右子树的父亲节点
        fa[ch[cnr][1]] = x;
        // 新左子树
        ch[x][1] = ch[cnr][1];
        clear(cnr);
        maintain(rt);
    }
} tree;

int n,ans,temp;

int main() {
    cin >> n;
    for (int i=1; i<=n; ++i) {
        cin >> temp;
        tree.ins(temp); // 插入后splay到了根节点
        if (i==1)
            ans += temp;
        else {
            if (cnt[rt]<=1) {
                int left = tree.pre();
                int right = tree.nxt();
                if (cnt[left] && cnt[right])
                    ans += min( abs(temp-val[left]) , abs(temp-val[right]) );
                else if (cnt[left])
                    ans += abs(temp-val[left]);
                else if (cnt[right])
                    ans += abs(temp-val[right]);
            }
        }
    }
    cout << ans << endl;
}

Luogu P2286

  1. 开2个树分别存(人和宠物)

  2. 同一时间呆在收养所中的，要么全是宠物，要么全是领养者, 所以一个树就可以处理,判断哪一个时刻存转为村宠物或者领养者

  • 处理mod
  • 处理 可能2子树其中有一个不存在的情况
  • 所有值都唯一

套在splay板子上 代码有点长

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int rt,tot,fa[maxn],ch[maxn][2],val[maxn],cnt[maxn],size[maxn];
int mod = 1e6;

struct Splay {
    void maintain(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x]; }
    bool get(int x) { return x == ch[fa[x]][1]; }
    void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = size[x] = cnt[x] = 0; }

    // 向右旋转
    void rotate(int x) {
        int y = fa[x],z=fa[y],chk=get(x);
        ch[y][chk] = ch[x][chk^1];
        fa[ch[x][chk^1]] = y;

        ch[x][chk^1] = y;
        fa[y] = x;

        fa[x] = z;
        if (z) ch[z][y == ch[z][1]] = x;

        maintain(y);
        maintain(x);
    }
    void splay(int x) {
        for (int f=fa[x]; f=fa[x],f; rotate(x))
            if (fa[f]) rotate(get(x) == get(f) ? f : x);
        rt = x;
    }
    void ins(int k) {
        // 树为空 插入到根节点
        if (!rt) {
            val[++tot] = k;
            cnt[tot]++;
            rt = tot;
            maintain(rt);
            return ;
        }
        int cnr = rt,f = 0;
        while (1) {
            // 恰好k == 当前值
            if (val[cnr] == k) {
                cnt[cnr]++;
                maintain(cnr);
                maintain(f);
                splay(cnr);
                break;
            }
            f = cnr;
            // 判断去左树还是右树
            cnr = ch[cnr][val[cnr] < k];
            // 到了叶节点,插入新的节点
            if (!cnr) {
                val[++tot] = k;
                cnt[tot]++;
                fa[tot] = f;
                ch[f][val[f] < k] = tot;

                maintain(tot);
                maintain(f);
                splay(tot);
                break;
            }
        }
    }
    // 给一个数k 查它的排名
    int rk(int k) {
        int res = 0,cnr = rt;
        while (1) {
            if (k < val[cnr])
                cnr = ch[cnr][0];
            else {
                res += size[ch[cnr][0]];
                if (k == val[cnr]) {
                    splay(cnr);
                    return res+1;
                }
                // 加上该节点的值
                res += cnt[cnr];
                cnr = ch[cnr][1];
            }
        }
    }
    // 给出排名k, 查询数
    int kth(int k) {
        int cnr = rt;
        while (1) {
            if (ch[cnr][0] && k <= size[ch[cnr][0]])
                cnr = ch[cnr][0];
            else {
                k -= size[ch[cnr][0]] + cnt[cnr];
                if (k <= 0) return val[cnr];
                cnr = ch[cnr][1];
            }
        }
    }
    // 根节点左子树最大值
    int pre() {
        int cnr = ch[rt][0];
        while(ch[cnr][1]) cnr = ch[cnr][1];
        return cnr;
    }
    // 根节点右子树最小值
    int nxt() {
        int cnr = ch[rt][1];
        while(ch[cnr][0]) cnr = ch[cnr][0];
        return cnr;
    }
    // 删除 值为k的节点
    void del(int k) {
        // 查k的排名将它旋转到根节点
        rk(k);
        // 多个k, 减去一个然后退出
        if (cnt[rt] > 1) {
            cnt[rt]--;
            maintain(rt);
            return ;
        }
        // 子节点都不存在
        if (!ch[rt][0] && !ch[rt][1]) {
            clear(rt);
            rt = 0;
            return ;
        }
        // 左节点不存在
        if (!ch[rt][0]) {
            int cnr = rt;
            rt = ch[rt][1];
            fa[rt] = 0;
            clear(cnr);
            return ;
        }
        // 右节点不存在
        if (!ch[rt][1]) {
            int cnr = rt;
            rt = ch[rt][0];
            fa[rt] = 0;
            clear(cnr);
            return ;
        }
        // 否则将x的左子树最大值旋转上来作为新 ,删除根节点后右子树接上来
        int x = pre(),cnr = rt;
        splay(x);
        // 修改原右子树的父亲节点
        fa[ch[cnr][1]] = x;
        // 新左子树
        ch[x][1] = ch[cnr][1];
        clear(cnr);
        maintain(rt);
    }
} tree;

int n,all,hope,k,ans;

int main() {
    cin >> n;
    while(n--) {
        cin >> k >> hope;
        if (all == 0)
            tree.ins(hope);
        if (all > 0) {
            if (k==0)
                tree.ins(hope);
            else {
                tree.ins(hope);
                int left = tree.pre(),right = tree.nxt();
                int lv = val[left],rv = val[right];
                if (cnt[left] && cnt[right]) {
                    if (abs(hope - lv) == abs(hope - rv)) {
                        ans += abs(hope - lv);
                        ans = ans % mod;
                        tree.del(lv);
                    } else {
                        int temp = min( abs(hope-lv) , abs(hope-rv) );
                        ans += temp;
                        ans = ans % mod;
                        tree.del( (temp==abs(hope-lv)) ? lv : rv );
                    }
                } else if (cnt[left]) {
                    //cout << " lv " << lv << endl;
                    ans += abs(hope - lv);
                    ans = ans % mod;
                    tree.del(lv);
                } else if (cnt[right]) {
                    //cout << " rv " << rv << " hope " << hope  << " ans " << ans  << endl;
                    ans += abs(hope - rv);
                    ans = ans % mod;
                    tree.del(rv);
                }

                tree.del(hope);
            }
        }
        if (all < 0) { // 顾客树
            if (k == 1) // 插入顾客
                tree.ins(hope);
            else {
                tree.ins(hope);
                int left = tree.pre(),right = tree.nxt();
                int lv = val[left],rv = val[right];
                if (cnt[left] && cnt[right]) {
                    if (abs(hope - lv) == abs(hope - rv)) {
                        ans += abs(hope - lv);
                        ans = ans % mod;
                        tree.del(lv);
                    } else {
                        int temp = min( abs(hope-lv) , abs(hope-rv) );
                        ans += temp;
                        ans = ans % mod;
                        tree.del( (temp==abs(hope-lv)) ? lv : rv );
                    }
                } else if (cnt[left]) {
                    ans += abs(hope - lv);
                    ans = ans % mod;
                    tree.del(lv);
                } else if (cnt[right]) {
                    ans += abs(hope - rv);
                    ans = ans % mod;
                    tree.del(rv);
                }
                tree.del(hope);
            }
        }
        all += (k==0 ? 1 : -1);
    }
    cout << ans << 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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int rt,tot,fa[maxn],ch[maxn][2],val[maxn],cnt[maxn],size[maxn];
int mod = 1e6;

struct Splay {
    void maintain(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x]; }
    bool get(int x) { return x == ch[fa[x]][1]; }
    void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = size[x] = cnt[x] = 0; }

    // 向右旋转
    void rotate(int x) {
        int y = fa[x],z=fa[y],chk=get(x);
        ch[y][chk] = ch[x][chk^1];
        fa[ch[x][chk^1]] = y;

        ch[x][chk^1] = y;
        fa[y] = x;

        fa[x] = z;
        if (z) ch[z][y == ch[z][1]] = x;

        maintain(y);
        maintain(x);
    }
    void splay(int x) {
        for (int f=fa[x]; f=fa[x],f; rotate(x))
            if (fa[f]) rotate(get(x) == get(f) ? f : x);
        rt = x;
    }
    void ins(int k) {
        // 树为空 插入到根节点
        if (!rt) {
            val[++tot] = k;
            cnt[tot]++;
            rt = tot;
            maintain(rt);
            return ;
        }
        int cnr = rt,f = 0;
        while (1) {
            // 恰好k == 当前值
            if (val[cnr] == k) {
                cnt[cnr]++;
                maintain(cnr);
                maintain(f);
                splay(cnr);
                break;
            }
            f = cnr;
            // 判断去左树还是右树
            cnr = ch[cnr][val[cnr] < k];
            // 到了叶节点,插入新的节点
            if (!cnr) {
                val[++tot] = k;
                cnt[tot]++;
                fa[tot] = f;
                ch[f][val[f] < k] = tot;

                maintain(tot);
                maintain(f);
                splay(tot);
                break;
            }
        }
    }
    // 给一个数k 查它的排名
    int rk(int k) {
        int res = 0,cnr = rt;
        while (1) {
            if (k < val[cnr])
                cnr = ch[cnr][0];
            else {
                res += size[ch[cnr][0]];
                if (k == val[cnr]) {
                    splay(cnr);
                    return res+1;
                }
                // 加上该节点的值
                res += cnt[cnr];
                cnr = ch[cnr][1];
            }
        }
    }
    // 给出排名k, 查询数
    int kth(int k) {
        int cnr = rt;
        while (1) {
            if (ch[cnr][0] && k <= size[ch[cnr][0]])
                cnr = ch[cnr][0];
            else {
                k -= size[ch[cnr][0]] + cnt[cnr];
                if (k <= 0) return val[cnr];
                cnr = ch[cnr][1];
            }
        }
    }
    // 根节点左子树最大值
    int pre() {
        int cnr = ch[rt][0];
        while(ch[cnr][1]) cnr = ch[cnr][1];
        return cnr;
    }
    // 根节点右子树最小值
    int nxt() {
        int cnr = ch[rt][1];
        while(ch[cnr][0]) cnr = ch[cnr][0];
        return cnr;
    }
    // 删除 值为k的节点
    void del(int k) {
        // 查k的排名将它旋转到根节点
        rk(k);
        // 多个k, 减去一个然后退出
        if (cnt[rt] > 1) {
            cnt[rt]--;
            maintain(rt);
            return ;
        }
        // 子节点都不存在
        if (!ch[rt][0] && !ch[rt][1]) {
            clear(rt);
            rt = 0;
            return ;
        }
        // 左节点不存在
        if (!ch[rt][0]) {
            int cnr = rt;
            rt = ch[rt][1];
            fa[rt] = 0;
            clear(cnr);
            return ;
        }
        // 右节点不存在
        if (!ch[rt][1]) {
            int cnr = rt;
            rt = ch[rt][0];
            fa[rt] = 0;
            clear(cnr);
            return ;
        }
        // 否则将x的左子树最大值旋转上来作为新 ,删除根节点后右子树接上来
        int x = pre(),cnr = rt;
        splay(x);
        // 修改原右子树的父亲节点
        fa[ch[cnr][1]] = x;
        // 新左子树
        ch[x][1] = ch[cnr][1];
        clear(cnr);
        maintain(rt);
    }
} tree;

int n,all,hope,k,ans;

int main() {
    cin >> n;
    while(n--) {
        cin >> k >> hope;
        if (all == 0)
            tree.ins(hope);
        bool flag = 0;
        if (all>0 && k==0) {
            tree.ins(hope);
            flag = 1;
        }
        if (all<0 && k==1) {
            tree.ins(hope);
            flag = 1;
        }
        if (flag) {
            all += (k==0?1:-1);
            continue;
        }
        tree.ins(hope);
        int left = tree.pre(),right = tree.nxt();
        int lv = val[left],rv = val[right];
        if (cnt[left] && cnt[right]) {
            if (abs(hope - lv) == abs(hope - rv)) {
                ans = (abs(hope -lv) + ans)%mod;
                tree.del(lv);
            } else {
                int temp = min( abs(hope-lv),abs(hope-rv) );
                ans = (ans + temp) % mod;
                tree.del((temp==abs(hope-lv))?lv:rv);
            }
        } else if (cnt[left]) {
            ans = (ans + abs(hope - lv)) % mod;
            tree.del(lv);
        } else if (cnt[right]) {
            ans = (ans + abs(hope - rv)) % mod;
            tree.del(rv);
        }
        tree.del(hope);
        all += (k==0?1:-1);
    }
    cout << ans << endl;
    return 0;
}
  • 一定要锻炼将题目所求转化到学过的东西？？？目前面临的最大问题，不然白学了 艹
算法
Splay性质

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！