关于 pb_ds 的平衡树怎么写
  • 板块学术版
  • 楼主cymrain07
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/10/23 10:29
  • 上次更新2023/11/4 02:44:16
查看原帖
关于 pb_ds 的平衡树怎么写
236006
cymrain07楼主2021/10/23 10:29

rt,普通平衡树那题想用 pb_ds 实现,样例都过不去。

#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;
}
2021/10/23 10:29
加载中...