社区讨论

关于 pb_ds 的平衡树怎么写

学术版参与者 4已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@lobijrv8
此快照首次捕获于
2023/10/29 21:35
2 年前
此快照最后确认于
2023/11/04 02:44
2 年前
查看原帖
rt,普通平衡树那题想用 pb_ds 实现,样例都过不去。
CPP
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> Tree;
int n, op;
ll x;
Tree t;
template <class T>
void read(T &x)
{
    x = 0;
    char c = getchar(), d = 0;
    while (!isdigit(c)) d = c, c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (d == '-') x = -x;
}
template <class T>
void wt(T x)
{
    if (x / 10) wt(x / 10);
    putchar(x % 10 + '0');
}
template <class T>
void write(T x)
{
    if (x < 0) putchar('-'), x = -x;
    wt(x);
}
#define space(x) write(x), putchar(' ')
#define enter(x) write(x), putchar('\n')
int main()
{
    read(n);
    while (n--)
    {
        read(op), read(x);
        if (op == 1) t.insert(x);
        if (op == 2) t.erase(t.lower_bound(x));
        if (op == 3) enter(t.order_of_key(x));
        if (op == 4) enter(*t.find_by_order(x));
        if (op == 5) enter(*--t.lower_bound(x));
        if (op == 6) enter(*t.upper_bound(x));
    }
    return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...