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

Creeper_LKF

2017-12-27 10:35:13

Solution

楼下也有写pbds的,但是需要n^20,这种情况下还是有可能撞hash(如果数据够大)。于是这里给出另外一种方法,0%的几率撞hash。 方法是用Node,然后记录每一个节点的输入时间,然后注意到相同数据下输入时间必定不同。 同时按照这个次序可以方便的lower/upper\_bound ```cpp #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; } ```