参考的大佬的博客的链接:
https://blog.csdn.net/onepointo/article/details/75083305
//luogu_3369
#include <stdio.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
null_type, less<LL>, rb_tree_tag, tree_order_statistics_node_update> t;
tree<LL, int, int> ma;
map<void Insert(int v) {
32) + ++ma[v]);
t.insert(((LL)v <<
}
void Delete(int v) {
auto it = ma.find(v);
32) + it->second);
t.erase(((LL)v <<
--it->second;if (0 == it->second) {
ma.erase(it);
}
}
int RankOf(int v) {
return t.order_of_key((LL)v << 32) + 1;
}
int FindByRank(int r) {
return *t.find_by_order(r-1) >> 32;
}
int FindPre(int v) {
auto it = ma.lower_bound(v);
--it;return it->first;
}
int FindNext(int v) {
return ma.upper_bound(v)->first;
}
int main() {
int n;
"%d", &n);
scanf(while (n--) {
int op, x;
"%d%d", &op, &x);
scanf(switch (op) {
case 1:
Insert(x);break;
case 2:
Delete(x);break;
case 3:
"%d\n", RankOf(x));
printf(break;
case 4:
"%d\n", FindByRank(x));
printf(break;
case 5:
"%d\n", FindPre(x));
printf(break;
case 6:
"%d\n", FindNext(x));
printf(break;
}
}return 0;
}
注意如果less<LL>不小心写成了less<int>,编译器不会报错,但是答案是错的。
另一种不用map来求前驱和后继的比较和谐的方法:
//luogu_3369
#include <stdio.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
null_type, less<LL>, rb_tree_tag, tree_order_statistics_node_update> t;
tree<LL, int, int> ma;
map<void Insert(int v) {
32) + ++ma[v]);
t.insert(((LL)v <<
}
void Delete(int v) {
32) + ma[v]--);
t.erase(((LL)v <<
}
int RankOf(int v) {
return t.order_of_key((LL)v << 32) + 1;
}
int FindByRank(int r) {
return *t.find_by_order(r-1) >> 32;
}
int FindPre(int v) {
auto it = t.lower_bound((LL)v << 32);
--it;return *it >> 32;
}
int FindNext(int v) {
return *t.lower_bound((LL)(v+1) << 32) >> 32;
}
int main() {
int n;
"%d", &n);
scanf(while (n--) {
int op, x;
"%d%d", &op, &x);
scanf(switch (op) {
case 1:
Insert(x);break;
case 2:
Delete(x);break;
case 3:
"%d\n", RankOf(x));
printf(break;
case 4:
"%d\n", FindByRank(x));
printf(break;
case 5:
"%d\n", FindPre(x));
printf(break;
case 6:
"%d\n", FindNext(x));
printf(break;
}
}return 0;
}
封装版:
//luogu_3369
#include <stdio.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T, typename less>
struct Cmp_MultiSet {
bool operator () (const pair<T, size_t>& x, const pair<T, size_t>& y) const {
return less()(x.first, y.first) ? true : (less()(y.first, x.first) ? false : less()(x.second, y.second));
}
};
template<typename T, typename less>
struct MultiSet {
size_t>, null_type, Cmp_MultiSet<T, less>, rb_tree_tag, tree_order_statistics_node_update> t;
tree<pair<T, size_t> ma;
map<T, void Insert(T v) {
t.insert(make_pair(v, ++ma[v]));
}void Delete(T v) {
t.erase(make_pair(v, ma[v]--));
}size_t RankOf(T v) {
return t.order_of_key(make_pair(v, 0)) + 1;
}size_t r) {
T FindByRank(return t.find_by_order(r-1)->first;
}
T FindPre(T v) {auto it = t.lower_bound(make_pair(v, 0));
return (--it)->first;
}
T FindNext(T v) {return t.lower_bound(make_pair(v+1, 0))->first;
}
};
int main() {
int, less<int> > se;
MultiSet<int n;
"%d", &n);
scanf(while (n--) {
int op, x;
"%d%d", &op, &x);
scanf(switch (op) {
case 1:
se.Insert(x);break;
case 2:
se.Delete(x);break;
case 3:
"%lu\n", se.RankOf(x));
printf(break;
case 4:
"%d\n", se.FindByRank(x));
printf(break;
case 5:
"%d\n", se.FindPre(x));
printf(break;
case 6:
"%d\n", se.FindNext(x));
printf(break;
}
}return 0;
}