STL-vector YYDS!!!
真·建树
vector <int> v;
真·插入
void insert () {
v.insert (lower_bound (v.begin (), v.end (), x), x); //vector-insert 是指在当前迭代器前插入 x,然后我们为了保证单调不减就可以用 lower_bound
return ;
}
真·删除
void del () {
v.erase (lower_bound (v.begin (), v.end (), x)); //找到 x 的第一个迭代器位置然后删掉
return ;
}
真·找排名
int find_rank () {
return lower_bound (v.begin (), v.end (), x) - v.begin () + 1; //找到第一个 x 位置,因为 vector 是 0 开始,别忘了 +1
}
真·找数
int find_num () {
return v[x - 1]; //最简单一个,别忘了 -1
}
真·找前驱
int last () {
return *(-- lower_bound (v.begin (), v.end (), x)); //找前驱很简单,只要找到第一个大于等于 x 的数,然后它的前一个数就是最后一个前驱位置力
}
真·找后继
int next () {
return *upper_bound (v.begin (), v.end (), x); //upper_bound 自带的。。
}
Code
# include <bits/stdc++.h>
# define ffor(i,name) \
for (auto i = name.begin (); i != name.end (); ++ i)
# define iter vector <int> :: iterator
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
int n, op, x;
vector <int> v;
void insert () {
v.insert (lower_bound (v.begin (), v.end (), x), x);
return ;
}
void del () {
v.erase (lower_bound (v.begin (), v.end (), x));
return ;
}
int find_rank () {
return lower_bound (v.begin (), v.end (), x) - v.begin () + 1;
}
int find_num () {
return v[x - 1];
}
int last () {
return *(-- lower_bound (v.begin (), v.end (), x));
}
int next () {
return *upper_bound (v.begin (), v.end (), x);
}
int main () {
ios::sync_with_stdio (0);
cin.tie (0);
cout.tie (0);
cin >> n;
while (n --) {
cin >> op >> x;
if (op < 2)
insert ();
else if (op < 3)
del ();
else if (op < 4)
cout << find_rank () << '\n';
else if (op < 5)
cout << find_num () << '\n';
else if (op < 6)
cout << last () << '\n';
else
cout << next () << '\n';
}
return 0;
}
有意思吗,这不是练习平衡树的吗?/cf
没意思,这能过只能说明数据水。。
或者是 vector 常数为1/inf
nsdd,dshttps://www.luogu.com.cn/record/144112916