题解 P3369 【【模板】普通平衡树(Treap/SBT)】

2017-12-27 10:35:13


楼下也有写pbds的,但是需要n^20,这种情况下还是有可能撞hash(如果数据够大)。于是这里给出另外一种方法,0%的几率撞hash。

方法是用Node,然后记录每一个节点的输入时间,然后注意到相同数据下输入时间必定不同。

同时按照这个次序可以方便的lower/upper_bound

#include <cstdio>
#include <cctype>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
inline char get_char(){
    static char buf[5000001], *p1 = buf, *p2 = buf + fread(buf, 1, 5000000, stdin);
    return p1 == p2 ? EOF : *p1 ++;
}
inline int read(){
    int num = 0;
    char c, sf = 1;
    while (isspace(c = get_char()));
    if(c == '-') sf = -1, c = get_char();
    while (num = num * 10 + c - 48, isdigit(c = get_char()));
    return num * sf;
}
struct Node{
    int v, id;
    Node(int a, int b){
        v = a, id = b;
    }
    bool operator < (Node tar) const {
        return v == tar.v ? id < tar.id : v < tar.v;
    }
};
typedef tree<Node, null_type, less<Node>, rb_tree_tag, tree_order_statistics_node_update> Tree;
Tree stl_tree;
Tree::iterator it;
int main(){
    int n = read();
    for(int i = 1; i <= n; i++){
        int cons = read(), tar = read();
        switch(cons){
            case 1:
                stl_tree.insert((Node){tar, i});
                break;
            case 2:
                it = stl_tree.lower_bound((Node{tar, 1}));
                stl_tree.erase(it);
                break;
            case 3:
                printf("%d\n", stl_tree.order_of_key(Node{tar, 1}) + 1);
                break;
            case 4:
                printf("%d\n", stl_tree.find_by_order(tar - 1) -> v);
                break;
            case 5:
                it = stl_tree.lower_bound(Node{tar, 1});
                it--;
                printf("%d\n", *it);
                break;
            case 6:
                it = stl_tree.upper_bound(Node{tar, n});//注意这个地方
                printf("%d\n", *it);
                break;
        }
    }
    return 0;
}