1
struct DSU
2
{
3
    vector<int> f, siz;
4
    DSU() {};
5
    DSU(int n)
6
    {
7
        init(n);
8
    }
9
    void init(int n)
10
    {
11
        f.resize(n + 1);
12
        iota(f.begin(), f.end(), 0);
13
        siz.assign(n + 1, 1);
14
    }
15
    int find(int x)
16
    {
17
        while(x != f[x])
18
            x = f[x] = f[f[x]];
19
        return x;
20
    }
21
    bool same(int x,int y)
22
    {
23
        return find(x) == find(y);
24
    }
25
    bool merge(int x,int y)
26
    {
27
        x = find(x);
28
        y = find(y);
29
        if(x == y)
30
            return false;
31
        if(siz[x] < siz[y])
32
            swap(x, y);
33
        siz[x] += siz[y];
34
        f[y] = x;
35
        return true;
36
    }
37
    int size(int x)
38
    {
39
        return siz[find(x)];
40
    }
41
};

1
struct DSU
2
{
3
    vector<int> f, siz, d;
4
    int mod;//mod的大小代表有几种关系
5
    DSU(int n,int mod_) : f(n + 1), siz(n + 1, 1), d(n + 1, 0), mod(mod_)
6
    {
7
        iota(f.begin(), f.end(), 0);
8
    }
9
    int find(int x)
10
    {
11
        if (x != f[x])
12
        {
13
            int root = find(f[x]);// 递归找根
14
            d[x] = (d[x] + d[f[x]]) % mod;// 核心：累加路径权值
15
            f[x] = root;// 路径压缩
16
        }
17
        return f[x];
18
    }
19
    // 合并 x 和 y，关系为：x -> y 的权值为 v
20
    // 返回值：true 表示合并成功或者已经在一个集合中且该关系v是正确的，false 表示已经在一个集合且矛盾
21
    bool merge(int x,int y,int v)
22
    {
23
        int rootx = find(x);
24
        int rooty = find(y);
25
        if(rootx == rooty)
26
        {
27
            int check = (d[x] - d[y] + mod) % mod;
28
            return check == v;
29
        }
30
        if(siz[rootx] < siz[rooty])
31
        {
32
            swap(rootx, rooty);
33
            v = (mod - v) % mod;
34
            swap(x, y);
35
        }
36
        f[rooty] = rootx;
37
        siz[rootx] += siz[rooty];
38
        d[rooty] = (d[x] - d[y] - v + mod) % mod;
39
        return true;
40
    }
41
    int query(int x,int y)
42
    {
43
        int rootx = find(x);
44
        int rooty = find(y);
45
        if(rootx != rooty)
46
            return -1;
47
        return (d[x] - d[y] + mod) % mod;
48
    }
49
};

1
struct DSU
2
{
3
    vector<int> f, siz;
4
    vector<pii> his;//记录历史操作,[y, x]表示y成为了x的儿子
5
    int part;
6
    DSU() {}
7
    DSU(int n)
8
    {
9
        init(n);
10
    }
11
    void init(int n)
12
    {
13
        f.resize(n + 1);
14
        iota(f.begin(), f.end(), 0);
15
        siz.assign(n + 1, 1);
16
        his.clear();
17
        part = n;
18
    }
19
    int find(int x)
20
    {
21
        while(x != f[x])
22
            x = f[x];
23
        return x;
24
    }
25
    bool same(int x,int y)
26
    {
27
        return find(x) == find(y);
28
    }
29
    bool merge(int x,int y)
30
    {
31
        x = find(x);
32
        y = find(y);
33
        if(x == y)
34
            return false;
35
        if(siz[x] < siz[y])
36
            swap(x, y);
37
        his.push_back({y, x});
38
        siz[x] += siz[y];
39
        f[y] = x;
40
        part--;
41
        return true;
42
    }
43
    int size(int x)
44
    {
45
        return siz[find(x)];
46
    }
47
    // 新增：撤销上一次成功的 merge 操作
48
    void undo()
49
    {
50
        if(his.empty())
51
            return;
52
        auto [y, x] = his.back();
53
        his.pop_back();
54
        siz[x] -= siz[y];
55
        f[y] = y;
56
        part++;
57
    }
58
    // 新增：获取当前状态（快照）
59
    int hissize()
60
    {
61
        return his.size();
62
    }
63
    // 新增：回滚到之前的某个快照状态
64
    void rollback(int tag)
65
    {
66
        while(his.size() > tag)
67
            undo();
68
    }
69
};

1
struct Treap
2
{
3
    static const int INF = 1e9;
4
    vector<int> val, dat, sz, cnt;
5
    vector<array<int,2>> ch;
6
    int tot, root;
7
    Treap() {}
8
    Treap(int n)
9
    {
10
        val.resize(n + 5);
11
        dat.resize(n + 5);
12
        sz.resize(n + 5);
13
        cnt.resize(n + 5);
14
        ch.resize(n + 5, {0, 0});
15
        tot = 0;
16
        root = 0;
17
        build();
18
    }
19
    int New(int v)
20
    {
21
        val[++tot] = v;
22
        dat[tot] = rand();
23
        sz[tot] = 1;
24
        cnt[tot] = 1;
25
        ch[tot][0] = ch[tot][1] = 0;
26
        return tot;
27
    }
28
    void pushup(int id)
29
    {
30
        if(!id)
31
            return;
32
        sz[id] = cnt[id] + sz[ch[id][0]] + sz[ch[id][1]];
33
    }
34

35
    void rotate(int &id,int d)
36
    {
37
        int tp = ch[id][d ^ 1];
38
        ch[id][d ^ 1] = ch[tp][d];
39
        ch[tp][d] = id;
40
        id = tp;
41
        pushup(ch[id][d]);
42
        pushup(id);
43
    }
44
    void build()
45
    {
46
        root = New(-INF);
47
        ch[root][1] = New(INF);
48
        pushup(root);
49
    }
50
    void insert(int &id,int v)
51
    {
52
        if(!id)
53
        {
54
            id = New(v);
55
            return;
56
        }
57
        if(val[id] == v)
58
        {
59
            cnt[id]++;
60
        }
61
        else
62
        {
63
            int d = (v < val[id] ? 0 : 1);
64
            insert(ch[id][d], v);
65
            if(dat[ch[id][d]] > dat[id])
66
                rotate(id, d ^ 1);
67
        }
68
        pushup(id);
69
    }
70
    void remove(int &id, int v)
71
    {
72
        if(!id)
73
            return;
74
        if(v == val[id])
75
        {
76
            if(cnt[id] > 1)
77
            {
78
                cnt[id]--;
79
                pushup(id);
80
                return;
81
            }
82
            else
83
            {
84
                if(ch[id][0] || ch[id][1])
85
                {
86
                    if(!ch[id][1]  || dat[ch[id][0]] > dat[ch[id][1]])
87
                    {
88
                        rotate(id, 1);
89
                        remove(ch[id][1], v);
90
                    }
91
                    else
92
                    {
93
                        rotate(id, 0);
94
                        remove(ch[id][0], v);
95
                    }
96
                    pushup(id);
97
                }
98
                else
99
                {
100
                    id = 0;
101
                }
102
                return;
103
            }
104
        }
105
        v < val[id] ? remove(ch[id][0], v) : remove(ch[id][1], v);
106
        pushup(id);
107
    }
108
    //查询 M 中有多少个数比 x 小，并且将得到的答案加一。
109
    int getRank(int id,int v)
110
    {
111
        if(!id)
112
            return 1;
113
        if(v == val[id])
114
            return sz[ch[id][0]] + 1;
115
        else if(v < val[id])
116
            return getRank(ch[id][0], v);
117
        else
118
            return sz[ch[id][0]] + cnt[id] + getRank(ch[id][1], v);
119
    }
120
    //根据排名找数字
121
    int getVal(int id,int rank)
122
    {
123
        if(!id)
124
            return INF;
125
        if(rank <= sz[ch[id][0]])
126
            return getVal(ch[id][0], rank);
127
        if(rank <= sz[ch[id][0]] + cnt[id])
128
            return val[id];
129
        return getVal(ch[id][1],rank - sz[ch[id][0]] - cnt[id]);
130
    }
131
    //前驱（小于 x，且最大的数）。
132
    int getPre(int v)
133
    {
134
        int id = root,pre = -INF;
135
        while(id)
136
        {
137
            if(val[id] < v)
138
                pre = val[id], id = ch[id][1];
139
            else
140
                id = ch[id][0];
141
        }
142
        return pre;
143
    }
144
    //后继（大于 x，且最小的数）。
145
    int getNext(int v)
146
    {
147
        int id = root, nxt = INF;
148
        while(id)
149
        {
150
            if(val[id] > v)
151
                nxt = val[id], id = ch[id][0];
152
            else
153
                id = ch[id][1];
154
        }
155
        return nxt;
156
    }
157
};
158
int main()
159
{
160
    int n;
161
    cin >> n;
162
    Treap t(n);
163
    while(n--)
164
    {
165
        int op, x;
166
        cin >> op >> x;
167
        if(op == 1)
168
            t.insert(t.root, x);
169
        else if(op == 2)
170
            t.remove(t.root, x);
171
        else if(op == 3)
172
            cout << t.getRank(t.root, x) - 1<< "\n";
173
        else if(op == 4)
174
            cout << t.getVal(t.root, x + 1) << "\n";
175
        else if(op == 5)
176
            cout << t.getPre(x) << "\n";
177
        else
178
            cout << t.getNext(x) << "\n";
179
    }
180
}

1
template<typename T>
2
struct Fenwick
3
{
4
    int n;
5
    vector<T> a;
6
    Fenwick(int n_ = 0)
7
    {
8
        init(n_);
9
    }
10
    void init(int n_)
11
    {
12
        n = n_;
13
        a.assign(n + 1, T{});
14
    }
15
    void add(int x,T v)
16
    {
17
        for (int i = x; i <= n;i += i & (-i))
18
        {
19
            a[i] += v;
20
        }
21
    }
22
    T sum(int x)
23
    {
24
        T ans{};
25
        for (int i = x; i > 0;i -= i & (-i))
26
        {
27
            ans += a[i];
28
        }
29
        return ans;
30
    }
31
    T rangeSum(int l,int r)
32
    {
33
        return sum(r) - sum(l - 1);
34
    }
35
    //select的功能是找到最大的位置 x，使得前缀和到x时 < k
36
    int select(const T &k)
37
    {
38
        int x = 0;
39
        T cur{};
40
        for (int i = 1 << __lg(n); i;i >>= 1)
41
        {
42
            if(x + i <= n && cur + a[x + i] <= k)
43
            {
44
                x += i;
45
                cur += a[x];
46
            }
47
        }
48
        return x;
49
    }
50
};

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4
template<class T>
5
void chmax(T &a, T b)
6
{
7
    if (a < b)
8
        a = b;
9
}
10
//i64
11
struct Basis
12
{
13
    vector<i64> a;// 基向量，a[i] 的最高位为 i
14
    vector<i64> t;// 时间戳，-1 表示空位
15
    bool zero = false;
16
    Basis()
17
    {
18
        a.resize(64, 0);
19
        t.resize(64, -1);//t[i] 的默认值 -1 表示该位尚未被占用
20
    }
21
    void add(i64 x, i64 y = 2e18)
22
    {
23
        for (int i = 63; i >= 0;i--)
24
        {
25
            if((x >> i) & 1)
26
            {
27
                if (y > t[i])
28
                {
29
                    swap(a[i], x);
30
                    swap(t[i], y);
31
                }
32
                x ^= a[i];
33
            }
34
        }
35
        if(x == 0)
36
            zero = true;
37
    }
38
    // 查询 x 能否由时间戳 ≥ y 的基向量表示
39
    bool query(i64 x, i64 y = 0)
40
    {
41
        for (int i = 63; i >= 0;i--)
42
        {
43
            if(((x >> i) & 1) && t[i] >= y)
44
                x ^= a[i];
45
        }
46
        return x == 0;
47
    }
48
    // 求最大异或和
49
    i64 getMax() {
50
        i64 res = 0;
51
        for (int i = 63; i >= 0; --i) {
52
            if ((res ^ a[i]) > res)  // 异或后变大则采用
53
                res ^= a[i];
54
        }
55
        return res;
56
    }
57
    i64 getMin()
58
    {
59
        if(zero)
60
            return 0;
61
        for (int i = 0; i <= 63;i++)
62
        {
63
            if(a[i])
64
                return a[i];
65
        }
66
        return 0;
67
    }
68
    //求第 k 小
69
    i64 getkth(i64 k)
70
    {
71
        if(zero)
72
        {
73
            if(k == 1)
74
                return 0;
75
            k--;//否则，将 k 减 1，后续只考虑非零的异或和，即第 2 小对应原来的第 1 个非零数，以此类推。
76
        }
77
        vector<i64> b = a;//复制，防止修改原数组
78
        vector<i64> tmp;
79
        for (int i = 0; i <= 63;i++)
80
        {
81
            for (int j = i - 1; j >= 0;j--)
82
            {
83
                //消元过程
84
                if((b[i] >> j) & 1)
85
                    b[i] ^= b[j];
86

87
            }
88
            if(b[i])//如果不为0
89
                tmp.push_back(b[i]);
90
        }
91
        i64 cnt = tmp.size();
92
        if(k >= (1ll << cnt))
93
            return -1;
94
        i64 res = 0;
95
        for (int i = 0; i < cnt;i++)
96
        {
97
            if((k >> i) & 1)
98
                res ^= tmp[i];
99
        }
100
        return res;
101
    }
102
};

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4
struct Splay
5
{
6
    struct Node
7
    {
8
        int val, id, lazy, size;
9
        Node *ch[2];
10
        Node *parent;
11
        Node(int v, int idx = 0) : val(v), id(idx), lazy(0), size(1), ch{nullptr, nullptr}, parent(nullptr) {}
12
    };
13
    Node *root;
14
    Splay() : root(nullptr) {}
15
    ~Splay() { clear(root); }
16
    void clear(Node *t)
17
    {
18
        if(!t)
19
            return;
20
        clear(t->ch[0]);
21
        clear(t->ch[1]);
22
        delete t;
23
    }
24
    // ---------- 辅助函数 ----------
25
    int getpos(Node* t) const
26
    {
27
        return t->parent ? (t->parent->ch[1] == t) : 0;
28
    }
29
    void pushup(Node* t)
30
    {
31
        if(!t)
32
            return;
33
        t->size = 1;
34
        if(t->ch[0])
35
            t->size += t->ch[0]->size;
36
        if(t->ch[1])
37
            t->size += t->ch[1]->size;
38
    }
39
    //执行加法
40
    void applytag(Node *t, int v)
41
    {
42
        if(!t)
43
            return;
44
        t->val += v;
45
        t->lazy += v;
46
    }
47
    void pushdown(Node *t)
48
    {
49
        if(!t || t->lazy == 0)
50
            return;
51
        if(t->ch[0])
52
            applytag(t->ch[0], t->lazy);
53
        if(t->ch[1])
54
            applytag(t->ch[1], t->lazy);
55
        t->lazy = 0;
56
    }
57
    // ---------- 旋转与伸展 ----------
58
    void rotate(Node *t)
59
    {
60
        Node *q = t->parent;
61
        int x = !getpos(t);
62
        q->ch[!x] = t->ch[x];
63
        if(t->ch[x])
64
            t->ch[x]->parent = q;
65
        t->parent = q->parent;
66
        if(q->parent)
67
            q->parent->ch[getpos(q)] = t;
68
        t->ch[x] = q;
69
        q->parent = t;
70
        pushup(q);
71
        pushup(t);
72
    }
73
    //伸展 (splay)：将指定节点通过旋转提升到根，沿途下传懒标记。
74
    void splay(Node *t)
75
    {
76
        vector<Node *> stk;
77
        for (Node *i = t; i->parent; i = i->parent)
78
            stk.push_back(i->parent);
79
        while(!stk.empty())
80
        {
81
            pushdown(stk.back());
82
            stk.pop_back();
83
        }
84
        pushdown(t);
85
        while(t->parent)//只要 t 还不是根，就继续旋转。
86
        {
87
            if(t->parent->parent)
88
            {
89
                if(getpos(t) == getpos(t->parent))
90
                    rotate(t->parent);
91
                else
92
                    rotate(t);
93
            }
94
            rotate(t);
95
        }
96
        root = t;
97
    }
98
    //分裂（split）：以值 x 为界，将树分成 < x 和 >= x 两部分
99
    //pair第一个元素是左子树的根（值 < x），第二个元素是右子树的根（值 ≥ x）
100
    pair<Node*, Node*> split(Node *t, int x)
101
    {
102
        if(!t)
103
            return {nullptr, nullptr};
104
        Node *v = nullptr;
105
        Node *j = t;
106
        for (Node *i = t; i; )
107
        {
108
            pushdown(i); // 下传懒标记，确保当前值正确
109
            j = i;// 记录最后访问的节点
110
            if(i->val >= x)
111
            {
112
                v = i;// 记录第一个遇到的 ≥ x 的节点
113
                i = i->ch[0]; // 继续向左，寻找更小的 ≥ x 的节点
114
            }
115
            else
116
            {
117
                i = i->ch[1]; // 向右，因为当前值 < x，要找 ≥ x 只能向右
118
            }
119
        }
120
        splay(j);
121
        if(!v)//如果没找到
122
            return {j, nullptr};
123
        splay(v);
124
        Node *u = v->ch[0];//将 v 的左孩子 u 取出，这就是我们需要的左子树（所有 < x 的节点）
125
        if(u)
126
        {
127
            v->ch[0] = u->parent = nullptr;//断开 u 与 v 的连接
128
            pushup(v);//更新子树大小
129
        }
130
        return {u, v};
131
    }
132
    //合并（merge）：要求输入的左树的最大值 < 右树的最小值，否则合并后的树会破坏 BST 结构。
133
    Node* merge(Node *l,Node *r)
134
    {
135
        if(!l)
136
            return r;
137
        if(!r)
138
            return l;
139
        Node *i = l;
140
        while(i->ch[1])
141
            i = i->ch[1];
142
        Node *ck = r;
143
        while(ck->ch[0])
144
            ck = ck->ch[0];
145
        assert(i->val < ck->val && "Merge precondition violated: left max >= right min");
146
        splay(i);
147
        i->ch[1] = r;
148
        r->parent = i;
149
        pushup(i);
150
        return i;//返回合并后的根节点
151
    }
152
    // ---------- 基本操作 ----------
153
    //插入
154
    void insert(int val, int id = 0)
155
    {
156
        Node *x = new Node(val, id);
157
        if(!root)
158
        {
159
            root = x;
160
            return;
161
        }
162
        auto [L, R] = split(root, val);
163
        root = merge(merge(L, x), R);
164
    }
165
    //全部清除
166
    void eraseAll(int val)
167
    {
168
        if(!root)
169
            return;
170
        auto [L, MR] = split(root, val);
171
        auto [M, R] = split(MR, val + 1);
172
        if(M)
173
            clear(M);
174
        root = merge(L, R);
175
    }
176
    //只删除一个
177
    void eraseSingle(int val)
178
    {
179
        if(!root)
180
            return;
181
        auto [L, MR] = split(root, val);
182
        auto [M, R] = split(MR, val + 1);
183
        if(M)
184
        {
185
            Node *v = M;
186
            Node *l = v->ch[0];
187
            Node *r = v->ch[1];
188
            if(l)
189
                l->parent = nullptr;
190
            if(r)
191
                r->parent = nullptr;
192
            delete v;
193
            M = merge(l, r);
194
        }
195
        root = merge(merge(L, M), R);
196
    }
197
    //查找某个数是否存在
198
    bool find(int val)
199
    {
200
        auto [L, R] = split(root, val);
201
        bool ok = false;
202
        if(R && R->val == val)
203
            ok = true;
204
        root = merge(L, R);
205
        return ok;
206
    }
207
    //查询一个数从小往大排为第几个
208
    int rank(int val)
209
    {
210
        auto [L, R] = split(root, val);
211
        int res = (L ? L->size : 0) + 1;
212
        root = merge(L, R);
213
        return res;
214
    }
215
    //查询第k小的数
216
    int kth(int k)
217
    {
218
        assert(root && k >= 1 && k <= root->size);
219
        Node *t = root;//从根节点开始
220
        while(t)
221
        {
222
            pushdown(t);//先调用 pushdown(t) 下传懒标记，保证左右子树的 size 和节点值准确。
223
            int lsz = t->ch[0] ? t->ch[0]->size : 0;//获取左子树大小
224
            if(k <= lsz)
225
                t = t->ch[0];//说明此时到左子树去找
226
            else if(k == lsz + 1)//说明当前节点 t 就是第 k 小的节点。
227
            {
228
                splay(t);
229
                return t->val;
230
            }
231
            else//在右子树，相应的去找就行
232
            {
233
                k -= lsz + 1;
234
                t = t->ch[1];
235
            }
236
        }
237
        return -1;//一般不可能在这里return，while循环里就return完了
238
    }
239
    //返回整个树的大小
240
    int size() const
241
    {
242
        return root ? root->size : 0;
243
    }
244
    // //区间加法
245
    // //这里l ，r代表的是真实数值，不是下标
246
    // void rangeAdd(int l, int r, int delta)
247
    // {
248
    //     if(l > r)
249
    //         return;
250
    //     auto [L, MR] = split(root, l);
251
    //     auto [M, R] = split(MR, r + 1);
252
    //     if(M)
253
    //         applytag(M, delta);//将 M 根节点的值增加 delta（t->val += delta）。并将 M 根节点的懒标记累加 delta（t->lazy += delta）。
254
    //     root = merge(merge(L, M), R);//复原
255
    // }
256
    //做中序遍历
257
    void inOrder(Node *t, vector<int> &out)
258
    {
259
        if(!t)
260
            return;
261
        pushdown(t);
262
        inOrder(t->ch[0], out);
263
        out.push_back(t->val);
264
        inOrder(t->ch[1], out);
265
    }
266
    //对所有> x的执行add操作
267
    // >= x的情况自己微调
268
    void add(int x, int addval)
269
    {
270
        auto [L, MR] = split(root, x);
271
        auto [M, R] = split(MR, x + 1);
272
        if(R)
273
            applytag(R, x);
274

275
        root = merge(merge(L, M), R);
276
    }
277
    //这个是special Add,在一组数插入之前就执行add，add 那些>=x的树完再插入
278
    void spe(int x, int id)
279
    {
280
        auto [L, R] = split(root, x);
281
        if(R)
282
            applytag(R, x);
283
        Node *node = new Node(x, id);
284
        Node *Lnode = merge(L, node);
285
        root = merge(Lnode, R);
286

287
        splay(node);
288
    }
289
    //对所有< x的执行minus操作
290
    void minus(int x,int mival)
291
    {
292
        auto [L, R] = split(root, x);
293
        if(L)
294
            applytag(L, -mival);
295
        root = merge(L, R);
296
    }
297
    void print()
298
    {
299
        vector<int> vals;
300
        inOrder(root, vals);
301
        for(int v : vals)
302
            cout << v << " ";
303
        cout << "\n";
304
    }
305
    void debugPrint()
306
    {
307
        vector<int> vals;
308
        inOrder(root, vals);
309
        for(int v : vals)
310
            cerr << v << " ";
311
        cerr << "\n";
312
    }
313
};