左偏红黑树

发表于 更新于 分类于 本文字数： 20k 阅读时长 ≈ 18 分钟

左偏红黑树的简单实现

左偏红黑树实现的 multiset

支持：

  • 插入 / 删除一个元素
  • 查询元素数量
  • 查找前驱 / 后继
  • 查询第 k 大元素
  • 查询元素排名
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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
#ifndef __LLRE_TREE__
#define __LLRE_TREE__ 1

#include <functional>
#include <memory>
#include <cassert>

template<typename Key, typename Compare = std::less<Key>>
class LLRB_Tree{
private:
    enum class Node_Color{BLACK, RED}; // the color of the parent link

    Compare compare = Compare();

    struct Node{
        Node *left = nullptr;
        Node *right = nullptr;
        Node *father = nullptr;

        size_t size;
        Node_Color color;
        Key key;
        size_t cnt;

        Node(Key key, Node_Color color, Node *father): key(key), color(color), size(1), cnt(1), father(father){}
        Node() = default;
    };

    void Delete_Tree(Node *root) const{
        if(root != nullptr){
            Delete_Tree(root->left);
            Delete_Tree(root->right);
            root->left = root->right = nullptr;
            delete root;
        }
    }

    size_t size(const Node *node) const{
        return (node == nullptr ? 0 : node->size);
    }

    bool is_red(const Node *node) const{
        return (node == nullptr ? 0 : (node->color == Node_Color::RED));
    }

    int add_node(Node *node){
        node->cnt++;
        node->size++;
        return node->cnt;
    }

    int sub_node(Node *node){
        node->cnt--;
        node->size--;
        return node->cnt;
    }

    Node *rotate_left(Node *node) const{
        // rotate left a red link
        //      <nd>                    <rc>
        //     /    \\                //    \
        //    *     <rc>     -->    <nd>     *
        //         /    \          /    \
        //        *      *        *      *
        assert(is_red(node->right));
        Node *res = node->right;
        node->right = res->left;
        res->left = node;
        if(node->right != nullptr) node->right->father = node;
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }

    Node *rotate_right(Node *node) const{
        // rotate right a red link
        //          <nd>               <lc>
        //        //    \             /    \\
        //      <lc>     *    -->    *     <nd>
        //     /    \                     /    \
        //    *      *                   *      *
        assert(is_red(node->left));
        Node *res = node->left;
        node->left = res->right;
        res->right = node;
        if(node->left != nullptr) node->left->father = node;
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }
    // get the fliped color
    Node_Color fliped_color(Node_Color color) const{
        return (color == Node_Color::RED ? Node_Color::BLACK : Node_Color::RED);
    }
    // flip the color of the three node
    void color_flip(Node *node) const{
        node->color = fliped_color(node->color);
        node->left->color = fliped_color(node->left->color);
        node->right->color = fliped_color(node->right->color);
    }

    Node *root = nullptr;
    //fix to maintain the tree
    Node *fix_up(Node *root){
        if(is_red(root->right) && !is_red(root->left)) root = rotate_left(root);
        if(is_red(root->left) && is_red(root->left->left)) root = rotate_right(root);
        if(is_red(root->left) && is_red(root->right)) color_flip(root);
        root->size = size(root->left) + size(root->right) + root->cnt;
        return root;
    }
    // move a red edge to left
    Node *move_red_left(Node *root){
        // fix the following case
        //          //             //
        //        <rt>           <rt>
        //       /    \         /    \
        //      *      *       *      *
        //     /      / \     /     // \
        //    *              *
        color_flip(root);
        if(is_red(root->right->left)){
            // fix the following case
            //           /                     /                       /                      //
            //        <rt>                  <rt>                 <newrt>                 <newrt>
            //      //    \\              //    \\              //     \\                /     \
            //      *      *     -->      *      *     -->    <rt>      *    -->      <rt>      *
            //     /     // \            /      / \\          //                      //
            //    *                     *                     *                       *
            //                                               /                       /
            //                                              *                       *
            root->right = rotate_right(root->right);
            root = rotate_left(root);
            color_flip(root);
        }
        return root;
    }
    // move a red edge to right
    Node *move_red_right(Node *root){
        // fix the following case
        //          //              //
        //        <rt>            <rt>
        //       /    \          /    \
        //      *      *        *      *
        //     /      / \     //      / \
        //    *      *   *    *      *   *
        color_flip(root);
        if(is_red(root->left->left)){
            // fix the following case
            //           /                      /                       //
            //        <rt>                <newrt>                  <newrt>
            //      //    \\             //     \\                 /     \
            //      *      *      -->    *       <rt>      -->    *       <rt>
            //    //      / \                       \\                       \\
            //    *      *   *                       *                        *
            //                                      / \                      / \
            //                                     *   *                    *   *
            root = rotate_right(root);
            color_flip(root);
        }
        return root;
    }
    // get the min value of the subtree
    Node *get_min(Node *root){
        Node *node = root;
        assert(node != nullptr);
        for(; node->left != nullptr; node = node->left);
        return node;
    }
    // erase the min node of the subtree
    Node *erase_min(Node *root){
        if(root->left == nullptr){
            delete root;
            return nullptr;
        }
        if(!is_red(root->left) && !is_red(root->left->left)) root = move_red_left(root);
        root->left = erase_min(root->left);
        return fix_up(root);
    }
    // insert from root as leaf
    Node *insert(Node *root, const Key &key, Node *father){
        if(root == nullptr) return new Node(key, Node_Color::RED, father);
        if(root->key == key){
            add_node(root);
            return fix_up(root);
        }
        else if(compare(key, root->key)) root->left = insert(root->left, key, root);
        else root->right = insert(root->right, key, root);
        return fix_up(root);
    }
    // erase an element
    Node *erase(Node *root, const Key &key){
        if(compare(key, root->key)){
            if(!is_red(root->left) && !is_red(root->left->left)) root = move_red_left(root);
            root->left = erase(root->left, key);
        }
        else{
            if(is_red(root->left)) root = rotate_right(root);
            if(key == root->key & root->right == nullptr){
                if(sub_node(root) == 0){
                    delete root;
                    return nullptr;
                }
                else return fix_up(root);
            }
            if(!is_red(root->right) && !is_red(root->right->left)) root = move_red_right(root);
            if(key == root->key){
                if(sub_node(root) == 0){
                    Node *node_min = get_min(root->right);
                    root->key = node_min->key;
                    root->cnt = node_min->cnt;
                    root->right = erase_min(root->right);
                }
                else return fix_up(root);
            }
            else root->right = erase(root->right, key);
        }
        return fix_up(root);
    }
    // get the prev node of the node
    Node *get_prev_node(Node *node) const{
        assert(node != nullptr);
        if(node->left == nullptr){
            while(node->father != nullptr && node->father->left == node) node = node->father;
            node = node->father;
        }
        else{
            node = node->left;
            while(node->right != nullptr) node = node->right;
        }
        return node;
    }
    // get the next node of the node
    Node *get_next_node(Node *node) const{
        assert(node != nullptr);
        if(node->right == nullptr){
            while(node->father != nullptr && node->father->right == node) node = node->father;
            node = node->father;
        }
        else{
            node = node->right;
            while(node->left != nullptr) node = node->left;
        }
        return node;
    }
    // print all (value: cnt)
    void print_tree(Node *root) const{
        if(root == nullptr) return;
        print_tree(root->left);
        std::cout << "(" << root->key << ": " << root->cnt << ") ";
        print_tree(root->right);
    }
public:
    LLRB_Tree() = default;
    LLRB_Tree(LLRB_Tree &) = default;
    LLRB_Tree(LLRB_Tree &&) noexcept = default;
    ~LLRB_Tree(){
        Delete_Tree(root);
    }
    // insert a node
    void insert(const Key &key){
        root = insert(root, key, nullptr);
        root->color = Node_Color::BLACK;
    }
    // delete a node
    size_t erase(const Key &key){
        if(count(key) > 0){
            if(!is_red(root->left) && !is_red(root->right)) root->color = Node_Color::RED;
            root = erase(root, key);
            if(root != nullptr) root->color = Node_Color::BLACK;
            return 1;
        }
        else return 0;
    }
    // clear all node
    void clear(){
        Delete_Tree(root);
        root = nullptr;
    }
    // get the size of the tree
    size_t size() const{
        return size(root);
    }
    // count the key
    size_t count(const Key &key) const{
        Node *node = root;
        while(node != nullptr){
            if(key == node->key) return node->cnt;
            if(compare(key, node->key)) node = node->left;
            else node = node->right;
        }
        return 0;
    }
    // get the rk of the value
    int get_rk(const Key &key) const{
        int rank = 1;
        Node *node = root;
        while(node != nullptr){
            if(compare(key, node->key)){
                node = node->left;
            }
            else{
                rank += size(node->left);
                if(key == node->key) return rank;
                rank += node->cnt;
                node = node->right;
            }
        }
        return rank;
    }
    // get the kth value
    Key get_kth(int k) const{
        Node *node = root;
        if(size(root) < k) return -1;
        while(true){
            if(k > size(node->left) + node->cnt){
                k -= size(node->left) + node->cnt;
                node = node->right;
            }
            else if(size(node->left) >= k) node = node->left;
            else return node->key;
        }
    }
    // get the prev of key
    Node *get_prev(const Key &key) const{
        Node *node = root, *res_node = nullptr;
        while(node != nullptr){
            res_node = node;
            if(compare(node->key, key)) node = node->right;
            else node = node->left;
        }
        if(compare(res_node->key, key)) return res_node;
        else return get_prev_node(res_node);
    }
    // get the next of key
    Node *get_next(const Key &key) const{
        Node *node = root, *res_node = nullptr;
        while(node != nullptr){
            res_node = node;
            if(compare(key, node->key)) node = node->left;
            else node = node->right;
        }
        if(compare(key, res_node->key)) return res_node;
        else return get_next_node(res_node);
    }
    // check if is empty
    bool empty() const{
        return (size(root) == 0);
    }
    // print the value
    void print() const{
        print_tree(root);
        std::cout << "\n";
    }
};

#endif

洛谷 P6136 AC 代码

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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
#include <iostream>
#include <functional>
#include <memory>
#include <cassert>

template<typename Key, typename Compare = std::less<Key>>
class LLRB_Tree{
private:
    enum class Node_Color{BLACK, RED}; // the color of the parent link

    Compare compare = Compare();

    struct Node{
        Node *left = nullptr;
        Node *right = nullptr;
        Node *father = nullptr;

        size_t size;
        Node_Color color;
        Key key;
        size_t cnt;

        Node(Key key, Node_Color color, Node *father): key(key), color(color), size(1), cnt(1), father(father){}
        Node() = default;
    };

    void Delete_Tree(Node *root) const{
        if(root != nullptr){
            Delete_Tree(root->left);
            Delete_Tree(root->right);
            root->left = root->right = nullptr;
            delete root;
        }
    }

    size_t size(const Node *node) const{
        return (node == nullptr ? 0 : node->size);
    }

    bool is_red(const Node *node) const{
        return (node == nullptr ? 0 : (node->color == Node_Color::RED));
    }

    int add_node(Node *node){
        node->cnt++;
        node->size++;
        return node->cnt;
    }

    int sub_node(Node *node){
        node->cnt--;
        node->size--;
        return node->cnt;
    }

    Node *rotate_left(Node *node) const{
        // rotate left a red link
        //      <nd>                    <rc>
        //     /    \\                //    \
        //    *     <rc>     -->    <nd>     *
        //         /    \          /    \
        //        *      *        *      *
        assert(is_red(node->right));
        Node *res = node->right;
        node->right = res->left;
        res->left = node;
        if(node->right != nullptr) node->right->father = node;
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }

    Node *rotate_right(Node *node) const{
        // rotate right a red link
        //          <nd>               <lc>
        //        //    \             /    \\
        //      <lc>     *    -->    *     <nd>
        //     /    \                     /    \
        //    *      *                   *      *
        assert(is_red(node->left));
        Node *res = node->left;
        node->left = res->right;
        res->right = node;
        if(node->left != nullptr) node->left->father = node;
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }
    // get the fliped color
    Node_Color fliped_color(Node_Color color) const{
        return (color == Node_Color::RED ? Node_Color::BLACK : Node_Color::RED);
    }
    // flip the color of the three node
    void color_flip(Node *node) const{
        node->color = fliped_color(node->color);
        node->left->color = fliped_color(node->left->color);
        node->right->color = fliped_color(node->right->color);
    }

    Node *root = nullptr;
    //fix to maintain the tree
    Node *fix_up(Node *root){
        if(is_red(root->right) && !is_red(root->left)) root = rotate_left(root);
        if(is_red(root->left) && is_red(root->left->left)) root = rotate_right(root);
        if(is_red(root->left) && is_red(root->right)) color_flip(root);
        root->size = size(root->left) + size(root->right) + root->cnt;
        return root;
    }
    // move a red edge to left
    Node *move_red_left(Node *root){
        // fix the following case
        //          //             //
        //        <rt>           <rt>
        //       /    \         /    \
        //      *      *       *      *
        //     /      / \     /     // \
        //    *              *
        color_flip(root);
        if(is_red(root->right->left)){
            // fix the following case
            //           /                     /                       /                      //
            //        <rt>                  <rt>                 <newrt>                 <newrt>
            //      //    \\              //    \\              //     \\                /     \
            //      *      *     -->      *      *     -->    <rt>      *    -->      <rt>      *
            //     /     // \            /      / \\          //                      //
            //    *                     *                     *                       *
            //                                               /                       /
            //                                              *                       *
            root->right = rotate_right(root->right);
            root = rotate_left(root);
            color_flip(root);
        }
        return root;
    }
    // move a red edge to right
    Node *move_red_right(Node *root){
        // fix the following case
        //          //              //
        //        <rt>            <rt>
        //       /    \          /    \
        //      *      *        *      *
        //     /      / \     //      / \
        //    *      *   *    *      *   *
        color_flip(root);
        if(is_red(root->left->left)){
            // fix the following case
            //           /                      /                       //
            //        <rt>                <newrt>                  <newrt>
            //      //    \\             //     \\                 /     \
            //      *      *      -->    *       <rt>      -->    *       <rt>
            //    //      / \                       \\                       \\
            //    *      *   *                       *                        *
            //                                      / \                      / \
            //                                     *   *                    *   *
            root = rotate_right(root);
            color_flip(root);
        }
        return root;
    }
    // get the min value of the subtree
    Node *get_min(Node *root){
        Node *node = root;
        assert(node != nullptr);
        for(; node->left != nullptr; node = node->left);
        return node;
    }
    // erase the min node of the subtree
    Node *erase_min(Node *root){
        if(root->left == nullptr){
            delete root;
            return nullptr;
        }
        if(!is_red(root->left) && !is_red(root->left->left)) root = move_red_left(root);
        root->left = erase_min(root->left);
        return fix_up(root);
    }
    // insert from root as leaf
    Node *insert(Node *root, const Key &key, Node *father){
        if(root == nullptr) return new Node(key, Node_Color::RED, father);
        if(root->key == key){
            add_node(root);
            return fix_up(root);
        }
        else if(compare(key, root->key)) root->left = insert(root->left, key, root);
        else root->right = insert(root->right, key, root);
        return fix_up(root);
    }
    // erase an element
    Node *erase(Node *root, const Key &key){
        if(compare(key, root->key)){
            if(!is_red(root->left) && !is_red(root->left->left)) root = move_red_left(root);
            root->left = erase(root->left, key);
        }
        else{
            if(is_red(root->left)) root = rotate_right(root);
            if(key == root->key & root->right == nullptr){
                if(sub_node(root) == 0){
                    delete root;
                    return nullptr;
                }
                else return fix_up(root);
            }
            if(!is_red(root->right) && !is_red(root->right->left)) root = move_red_right(root);
            if(key == root->key){
                if(sub_node(root) == 0){
                    Node *node_min = get_min(root->right);
                    root->key = node_min->key;
                    root->cnt = node_min->cnt;
                    root->right = erase_min(root->right);
                }
                else return fix_up(root);
            }
            else root->right = erase(root->right, key);
        }
        return fix_up(root);
    }
    // get the prev node of the node
    Node *get_prev_node(Node *node) const{
        assert(node != nullptr);
        if(node->left == nullptr){
            while(node->father != nullptr && node->father->left == node) node = node->father;
            node = node->father;
        }
        else{
            node = node->left;
            while(node->right != nullptr) node = node->right;
        }
        return node;
    }
    // get the next node of the node
    Node *get_next_node(Node *node) const{
        assert(node != nullptr);
        if(node->right == nullptr){
            while(node->father != nullptr && node->father->right == node) node = node->father;
            node = node->father;
        }
        else{
            node = node->right;
            while(node->left != nullptr) node = node->left;
        }
        return node;
    }
    // print all (value: cnt)
    void print_tree(Node *root) const{
        if(root == nullptr) return;
        print_tree(root->left);
        std::cout << "(" << root->key << ": " << root->cnt << ") ";
        print_tree(root->right);
    }
public:
    LLRB_Tree() = default;
    LLRB_Tree(LLRB_Tree &) = default;
    LLRB_Tree(LLRB_Tree &&) noexcept = default;
    ~LLRB_Tree(){
        Delete_Tree(root);
    }
    // insert a node
    void insert(const Key &key){
        root = insert(root, key, nullptr);
        root->color = Node_Color::BLACK;
    }
    // delete a node
    size_t erase(const Key &key){
        if(count(key) > 0){
            if(!is_red(root->left) && !is_red(root->right)) root->color = Node_Color::RED;
            root = erase(root, key);
            if(root != nullptr) root->color = Node_Color::BLACK;
            return 1;
        }
        else return 0;
    }
    // clear all node
    void clear(){
        Delete_Tree(root);
        root = nullptr;
    }
    // get the size of the tree
    size_t size() const{
        return size(root);
    }
    // count the key
    size_t count(const Key &key) const{
        Node *node = root;
        while(node != nullptr){
            if(key == node->key) return node->cnt;
            if(compare(key, node->key)) node = node->left;
            else node = node->right;
        }
        return 0;
    }
    // get the rk of the value
    int get_rk(const Key &key) const{
        int rank = 1;
        Node *node = root;
        while(node != nullptr){
            if(compare(key, node->key)){
                node = node->left;
            }
            else{
                rank += size(node->left);
                if(key == node->key) return rank;
                rank += node->cnt;
                node = node->right;
            }
        }
        return rank;
    }
    // get the kth value
    Key get_kth(int k) const{
        Node *node = root;
        if(size(root) < k) return -1;
        while(true){
            if(k > size(node->left) + node->cnt){
                k -= size(node->left) + node->cnt;
                node = node->right;
            }
            else if(size(node->left) >= k) node = node->left;
            else return node->key;
        }
    }
    // get the prev of key
    Node *get_prev(const Key &key) const{
        Node *node = root, *res_node = nullptr;
        while(node != nullptr){
            res_node = node;
            if(compare(node->key, key)) node = node->right;
            else node = node->left;
        }
        if(compare(res_node->key, key)) return res_node;
        else return get_prev_node(res_node);
    }
    // get the next of key
    Node *get_next(const Key &key) const{
        Node *node = root, *res_node = nullptr;
        while(node != nullptr){
            res_node = node;
            if(compare(key, node->key)) node = node->left;
            else node = node->right;
        }
        if(compare(key, res_node->key)) return res_node;
        else return get_next_node(res_node);
    }
    // check if is empty
    bool empty() const{
        return (size(root) == 0);
    }
    // print the value
    void print() const{
        print_tree(root);
        std::cout << "\n";
    }
};

int ans = 0, lst = 0;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;

    LLRB_Tree<int> st;

    for(int i = 1, x; i <= n; i++){
        std::cin >> x;
        st.insert(x);
    }

    while(m--){
        int op, x;
        std::cin >> op >> x;
        x ^= lst;

        if(op == 1){
            st.insert(x);
        }
        else if(op == 2){
            st.erase(x);
        }
        else if(op == 3){
            lst = st.get_rk(x);
            ans ^= lst;
        }
        else if(op == 4){
            lst = st.get_kth(x);
            ans ^= lst;
        }
        else if(op == 5){
            lst = st.get_prev(x)->key;
            ans ^= lst;
        }
        else{
            lst = st.get_next(x)->key;
            ans ^= lst;
        }
    }

    std::cout << ans << "\n";

    return 0;
}