题解 P3369 【【模板】普通平衡树(Treap/SBT)】
Creeper_LKF
2017-12-27 10:35:13
楼下也有写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;
}
```