pbds平衡树求助
查看原帖
pbds平衡树求助
774258
mm1214楼主2024/9/30 16:09

rt,样例都过不去

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#define int long long
#define pii pair<int , int>
#define pb emplace_back
#define pair(x , y) make_pair(x , y)
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid (l + r >> 1)
using namespace std;
constexpr int N = 1e5 + 5;
int n;
struct BST {
    __gnu_pbds::tree<int , __gnu_pbds::null_type , less<int> , __gnu_pbds::rb_tree_tag , __gnu_pbds::tree_order_statistics_node_update> tr;
    inline void insert(int x) { tr.insert(x); }
    inline int Kth(int k)     { return *tr.find_by_order(k - 1); }
    inline void del(int x)    { tr.erase(tr.find(x)); }
    inline int rank(int x)    { return tr.order_of_key(x) + 1; }
    inline int Pre(int x)     { return Kth(rank(x)); }
    inline int Nxt(int x)     { return Kth(rank(x + 1) + 1); }
} tr;
void _main() {
    cin >> n;
    for (int i = 1 , op , x; i <= n; i++) {
        cin >> op >> x;
        if (op == 1) {
            tr.insert(x);
        } else if (op == 2) {
            tr.del(x);
        } else if (op == 3) {
            cout << tr.rank(x) << '\n';
        } else if (op == 4) {
            cout << tr.Kth(x) << '\n';
        } else if (op == 5) {
            cout << tr.Pre(x) << '\n';
        } else {
            cout << tr.Nxt(x) << '\n';
        }
    }
    return;
}
signed main() {
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int T = 1;
    for (; T--; _main());
    return 0;
}
2024/9/30 16:09
加载中...