其它平衡树¶
pbds中的平衡树¶
请参考
pbds库学习笔记(优先队列、平衡树、哈希表)-CSDN博客
平衡树的vector伪做法¶
注意，vector的常数较大（尤其是插入删除操作≥1e4），请**不要视为set（前驱|后继|最值|插入|删除）的平替**，仅限急救使用。
1. 插入数值 x。¶
我们运用刚刚学到的知识，使用 lower_bound() 来得到应该插入的位置的迭代器，然后使用 insert() 函数来插入，是一个基础的操作。
2. 删除数值 x。¶
仿照上例易得，使用 lower_bound() 来得到应该删除的位置的迭代器，然后使用 erase() 函数删除。
3. 查询数值 x 的排名。¶
由于整个序列都是有序的，所以说我们可以查找 x 的位置，然后看其在数组中的位置。这样既然是查找位置，我们明显可以 lower_bound() 一波嘛~ 然后呢，用得到的迭代器减去开头的迭代器，就是得到的排名了。
4. 查询排名为 x 的数值。¶
输出在第 x 位上的数。没什么好讲的。
5. 求数值 x 的前驱后继。¶
前驱可以用 lower_bound() 来求，然后就是这个迭代器前一个的位置。注意要用星号解引用。
后继直接用 upper_bound() 就可以了~
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
vector<int> s;
vector<int>::iterator vit;
int rks;
int main() {
int t;
cin >> t;
while(t --) {
int cmd, x;
cin >> cmd >> x;
if(cmd == 1) {
vit = lower_bound(s.begin(), s.end(), x);
s.insert(vit, x);
} else if(cmd == 2) {
vit = lower_bound(s.begin(), s.end(), x);
s.erase(vit);
} else if(cmd == 3) {
rks = lower_bound(s.begin(),s.end(),x)-s.begin();
cout << rks + 1 << endl;
} else if(cmd == 4) {
cout << s[x - 1] << endl;
} else if(cmd == 5) {
vit = lower_bound(s.begin(), s.end(), x);
cout << (*(--vit)) << endl;
} else if(cmd == 6) {
vit = upper_bound(s.begin(), s.end(), x);
cout << (*vit) << endl;
}
}
}