首先有插入查找排名x的数,查找x数字的排名,查找x
排名的前驱或者后驱的数字,删除等操作
所以可以用stl的multiset来完成(好东西)
#include <bits/stdc++.h>
using namespace std;
typedef multiset<int>::iterator sett;//每次都写太长了,typedef一下
sett c,d;//定义2个迭代器
int main()
{
int n,a,x;
multiset<int> s1;
cin>>n;
s1.insert(2147483647);//为防止没有后继,手动添加一个最大值
while(n--)
{
cin>>a>>x;
switch(a){
case 1:{//查询 x数的排名
c=s1.lower_bound(x);//二分查找第一个x出现的位置
int num=1;//计数器
for(d=s1.begin();d!=c;++d)//从第一个开始跑,直到到了第一个x
++num;
cout<<num<<"\n";//输出num
break;
}
case 2:{//查询排名为x的数
int num=1;
for(d=s1.begin();num<x;++num)//不会pbds,只能手动一个一个加了
++d;
cout<<*d<<"\n";
break;
}
case 3:{//求x的前驱
c=s1.lower_bound(x);//二分查找第一个x出现的位置
--c;//那他前面一个必然是前驱
cout<<*c<<"\n";
break;
}
case 4:{//求x的后继
c=s1.upper_bound(x);//二分查找第一个大于x的位置
cout<<*c<<"\n";
break;
}
case 5:{//插入一个数x
s1.insert(x);//插入元素
break;
}
}
}
return 0;
}
网友评论