俺集训队论文写了 vEB tree 和 压位trie，论文里有测速，这里把用来测速的板子公开一下。

vEB tree

#include<bits/stdc++.h>
class IO {
        unsigned buf_in[1 << 26], *idx_in;
        unsigned buf_out[1 << 26], *idx_out;
    public :
        IO() {
            fread((char*) buf_in, 1, sizeof buf_in, stdin);
            idx_in = buf_in;
            idx_out = buf_out;
        }
        ~ IO() {
            fwrite((char*) buf_out, 1, (char*) idx_out - (char*) buf_out, stdout);
        }
        inline unsigned getint() {
            return *idx_in ++ ;
        }
        inline void putint(unsigned x) {
            *idx_out++ = x;
        }
} IO;
#define high(x) (x >> size)
#define low(x) (x & ((1 << size) - 1))
#define index(x, y) (x << size | y)
template<const int size>
struct vEB_tree_tag {
    vEB_tree_tag <size / 2> c[1 << size], s;
    int MN, MX;
    vEB_tree_tag() {
        MN = MX = -1;
    }
    inline int mx() {
        return MX;
    }
    inline int mn() {
        return MN;
    }
    int succ(int x) {
        if (MX <= x) return -1;
        if (x < MN) return MN;
        int t = c[high(x)].mx();
        if (t != -1 && low(x) < t) return index(high(x), c[high(x)].succ(low(x)));
        t = s.succ(high(x));
        return index(t, c[t].mn());
    }
    int pre(int x) {
        if (MN >= x || MN == -1) return -1;
        int t = c[high(x)].mn();
        if (t != -1 && low(x) > t) return index(high(x), c[high(x)].pre(low(x)));
        t = s.pre(high(x));
        if (t == -1) return MN;
        return index(t, c[t].mx());
    }
    void empty_insert(int x) {
        MN = MX = x;
    }
    void insert(int x) {
        if (MN == -1)return empty_insert(x);
        if (x < MN) std::swap(x, MN);
        if (c[high(x)].mn() == -1) {
            s.insert(high(x));
            c[high(x)].empty_insert(low(x));
        } else c[high(x)].insert(low(x));
        if (x > MX) MX = x;
    }
    void erase(int x) {
        if (MN == MX) {
            MN = MX = -1;
            return;
        }
        if (x == MN) {
            int t = s.mn();
            MN = x = index(t, c[t].mn());
        }
        c[high(x)].erase(low(x));
        if (c[high(x)].mn() == -1) s.erase(high(x));
        if (x == MX) {
            int t = s.mx();
            if (t == -1) MX = MN;
            else MX = index(t, c[t].mx());
        }
    }
};

#define clz __builtin_clzll
#define ctz __builtin_ctzll
typedef unsigned long long ull;
template<>
struct vEB_tree_tag<3> {
    ull val;
    inline int mx() {
        return val ? 63 - clz(val) : -1;
    }
    inline int mn() {
        return val ? ctz(val) : -1;
    }
    inline void empty_insert(int x) {
        val = 1ll << x;
    }
    inline void insert(int x) {
        val |= 1ll << x;
    }
    inline void erase(int x) {
        val ^= val & 1ll << x;
    }
    inline int pre(int x) {
        return val & ((1ll << x) - 1) ? 63 - clz(val & ((1ll << x) - 1)) : -1;
    }
    inline int succ(int x) {
        return val >> (x + 1) ? x + 1 + ctz(val >> (x + 1)) : -1;
    }
};

vEB_tree_tag<12>S;
int T;
int main() {
    for (T = IO.getint(); T--;) {
        unsigned w = IO.getint();
        int op = w >> 24;
        int x = w & (1 << 24) - 1;
        if (op == 1) S.insert(x);
        if (op == 2) S.erase(x);
        if (op == 3) IO.putint(S.pre(x));
        if (op == 4) IO.putint(S.succ(x));
    }
    return 0;
}

压位 trie

#include<bits/stdc++.h>

class IO {
        unsigned buf_in[1 << 26], *idx_in;
        unsigned buf_out[1 << 26], *idx_out;
    public :
        IO() {
            fread((char*) buf_in, 1, sizeof buf_in, stdin);
            idx_in = buf_in;
            idx_out = buf_out;
        }
        ~ IO() {
            fwrite((char*) buf_out, 1, (char*) idx_out - (char*) buf_out, stdout);
        }
        inline unsigned getint() {
            return *idx_in ++ ;
        }
        inline void putint(unsigned x) {
            *idx_out++ = x;
        }
} IO;
using int_t = uint64_t;
const int BIT = sizeof(int_t) * 8;
const int LG = std::__lg(BIT);
const int state = (1 << LG) - 1;

int_t buffer[1 << 25], *end = buffer + sizeof(buffer) / sizeof(int_t);
inline int_t* alloc(int size) {
    return end -= size;
}

inline int ctz(uint32_t x) {
    return __builtin_ctz(x);
}
inline int ctz(uint64_t x) {
    return __builtin_ctzll(x);
}
inline int clz(uint32_t x) {
    return __builtin_clz(x);
}
inline int clz(uint64_t x) {
    return __builtin_clzll(x);
}

class bitwise_trie {
        int_t * tree[10];
        int d;
    public :
        bitwise_trie(int size) {
            d = 1;
            for (;; ++d) {
                int cnt = (size + (1 << LG * d) - 1) >> LG * d;
                tree[d - 1] = alloc(cnt);
                if (cnt == 1) break;
            }
        }
        inline void ins(int x) {
            for (int i = 0; i < d; ++i) {
                const int_t w = (int_t) 1 << (x >> i * LG & state);
                if (tree[i][x >> (i + 1) * LG] & w) return ;
                tree[i][x >> (i + 1) * LG] |= w;
            }
        }
        inline void del(int x) {
            for (int i = 0; i < d; ++i)
                if (tree[i][x >> (i + 1) * LG] &= ~((int_t) 1 << (x >> i * LG & state)))
                    return ;
        }
        inline int succ(int x) const {
            for (int i = 0; i < d; ++i) {
                const int w = (x >> i * LG) & state;
                const int_t v = tree[i][x >> (i + 1) * LG];
                if ((v >> w) > 1) {
                    int ans = x >> (i + 1) * LG << (i + 1) * LG;
                    ans += (ctz(v >> (w + 1)) + w + 1) << i * LG;
                    for (int j = i - 1; j >= 0; --j)
                        ans += ctz(tree[j][ans >> (j + 1) * LG]) << j * LG;
                    return ans;
                }
            }
            return -1;
        }
        inline int prev(int x) const {
            for (int i = 0; i < d; ++i) {
                const int w = (x >> i * LG) & state;
                const int_t v = tree[i][x >> (i + 1) * LG];
                if (v & (((int_t) 1 << w) - 1)) {
                    int ans = x >> (i + 1) * LG << (i + 1) * LG;
                    ans += (state - clz(v & (((int_t) 1 << w) - 1))) << i * LG;
                    for (int j = i - 1; j >= 0; --j)
                        ans += (state - clz(tree[j][ans >> (j + 1) * LG])) << j * LG;
                    return ans;
                }
            }
            return -1;
        }
};


int main() {
    bitwise_trie a(1 << 24);
    int n, x, opt;
    n = IO.getint();
    for (int i = 0; i < n; ++i) {
        unsigned w = IO.getint();
        int opt = w >> 24;
        int x = w & (1 << 24) - 1;
        if (opt == 1) a.ins(x);
        if (opt == 2) a.del(x);
        if (opt == 3) IO.putint(a.prev(x));
        if (opt == 4) IO.putint(a.succ(x));
    }

}

树状数组

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<bitset>
class IO {
        unsigned buf_in[1 << 26], *idx_in;
        unsigned buf_out[1 << 26], *idx_out;
    public :
        IO() {
            fread((char*) buf_in, 1, sizeof buf_in, stdin);
            idx_in = buf_in;
            idx_out = buf_out;
        }
        ~ IO() {
            fwrite((char*) buf_out, 1, (char*) idx_out - (char*) buf_out, stdout);
        }
        inline unsigned getint() {
            return *idx_in ++ ;
        }
        inline void putint(unsigned x) {
            *idx_out++ = x;
        }
} IO;
const int N = 1 << 24;
int a[N + 1];
inline void add(int x) {
    ++x;
    while (x <= N) ++a[x], x += x & -x;
}
inline void dec(int x) {
    --x;
    while (x <= N) --a[x], x += x & -x;
}
inline int query(int x) {
    int ans = 0;
    while (x) ans += a[x], x &= x - 1;
    return ans;
}
inline int kth(int k, int rt = N) {
    if (a[rt] < k || k == 0) return -1;
    int l = 1, r = N;
    while (l != r) {
        int mid = l + r >> 1;
        if (a[mid] < k) k -= a[mid], l = mid + 1;
        else r = mid;
    }
    return l;
}
inline int pre(int x) {
    for (; x;) {
        int y = x & x - 1;
        if (a[x]) {
            int res = a[x];
            for (; y + 1 < x;) {
                int z = (x + y) >> 1;
                if (a[z] == res) x = z;
                else y = z, res -= a[z];
            }
            return x - 1;
        } else x = y;
    }
    return -1;
}
inline int succ(int x) {
    for (++x; x != N;) {
        int y = x + (x & -x), res = a[y];
        for (int z = x; z != (y & y - 1); z &= z - 1) res -= a[z];
        if (res) {
            for (; x + 1 < y;) {
                int z = (x + y) >> 1;
                if (!a[z]) x = z;
                else y = z;
            }
            return y - 1;
        } else x = y;
    }
    return -1;
}
int n, opt, x;
int main() {
    n = IO.getint();
    for (int i = 1; i <= n; ++i) {
        unsigned w = IO.getint();
        opt = w >> 24;
        x = w & (1 << 24) - 1;
        if (opt == 1) add(x);
        if (opt == 2) dec(x);
        if (opt == 3) IO.putint(pre(x));
        if (opt == 4) IO.putint(succ(x));
    }
}

set

#include<bits/stdc++.h>
using namespace std;

class IO {
        unsigned buf_in[1 << 26], *idx_in;
        unsigned buf_out[1 << 26], *idx_out;
    public :
        IO() {
            fread((char*) buf_in, 1, sizeof buf_in, stdin);
            idx_in = buf_in;
            idx_out = buf_out;
        }
        ~ IO() {
            fwrite((char*) buf_out, 1, (char*) idx_out - (char*) buf_out, stdout);
        }
        inline unsigned getint() {
            return *idx_in ++ ;
        }
        inline void putint(unsigned x) {
            *idx_out++ = x;
        }
} IO;

set<int> s;
int main() {
    int n = IO.getint();
    while (n--) {
        unsigned w = IO.getint();
        int opt = w >> 24;
        int x = w & (1 << 24) - 1;
        if (opt == 1) s.emplace(x);
        if (opt == 2) s.erase(x);
        if (opt == 3) {
            set<int>::iterator it = s.lower_bound(x);
            if (it == s.begin()) IO.putint(-1);
            else IO.putint(*prev(it));
        }
        if (opt == 4) {
            set<int>::iterator it = s.upper_bound(x);
            if (it == s.end()) IO.putint(-1);
            else IO.putint(*it);
        }

    return 0;
}