题目：https://www.luogu.com.cn/problem/P5076
使用STL: set
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
/*快读*/
int read(){
int x = 0,f = 1;
char c = getchar();
while (c<'0'||c>'9') {
if (c=='-') {
f = -1;
}
c = getchar();
}
while (c>='0'&&c<='9') {
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
/*multiset有什么性质？
* 里面的元素按顺序排列，默认升序。
* 不去重（这点和set是不同的）*/
multiset<int>q;
int n,t,x,order;
int main()
{
q.insert(-0x7fffffff);
q.insert(0x7fffffff);
//提前放入这两个数，避免错误
n = read();
while(n--)
{
t = read();//功能
x = read();//数字
if(t==1)
{
multiset<int>::iterator it=q.lower_bound(x);
//auto是自动判断数据类型，只有C++14以上才支持
//可以写作multiset<int>::iterator，因为lower_bound方法返回的是迭代器
// it 取得 x 的位置
order=0;
//order为排名
for(multiset<int>::iterator i=q.begin();i!=it;i++,order++);
//这里的auto同理，也是迭代器
//这里就处理出了x的排名——order
printf("%d\n",order);
//输出order即为答案
}
else if(t==2)
{
order=-1;
//初值为-1是因为前面有一个-0x7fffffff，所以order要多跑一步
/*
for(int i:q)
if(++order==x)
//缩写，order先自增一，再判断是否与x相等
//如果是(order++==x)，那就是先判断再自增，这里要尤其注意
printf("%d\n",i);
//i就是容器里的值，输出i
*/
//注意这里的for(:)循环，是只有C++11以上才支持的
//和auto一样，都是noip不能用的
//这种循环，i就是容器里的值而不是下标
//也可以使用迭代器循环，上面的循环等价于
for(multiset<int>::iterator it=q.begin();it!=q.end();it++)
{
order++;
if(order==x)
printf("%d\n",*it);
}
//这种循环是noip可以使用的
}
else if(t==3)
{
multiset<int>::iterator it=q.lower_bound(x);
//取得第一个大于等于x的值
//也就是第一个x的位置
//由于我们要取得前驱，所以it要自减一
printf("%d\n",*(--it));
//这句是先自减，再输出，是缩写
//等价于：
/*
it--;
printf("%d\n",*it);
*/
//因为是迭代器（指针），所以输出前面加 *
}
else if(t==4)
{
printf("%d\n",*q.upper_bound(x));
//要取得后继，就是第一个大于x的值
//用upper_bound方法取得第一个大于x的迭代器
//输出即可
//因为是迭代器（指针），所以输出前面加 *
}
else
{
q.insert(x);
//直接添加即可
}
}
return 0;
}
/*
7
5 1
5 3
5 5
1 3
2 2
3 3
4 3
*/
非STL
#include<iostream>
#include<cstdio>
using namespace std;
const int INF=0x7fffffff;
int cont;
struct node{
int val,ls,rs,cnt,siz;
}tree[500010];
int n,opt,xx;
void add(int x,int v)
{
tree[x].siz++;
if(tree[x].val==v){
tree[x].cnt++;
return ;
}
if(tree[x].val>v){
if(tree[x].ls!=0)
add(tree[x].ls,v);
else{
cont++;
tree[cont].val=v;
tree[cont].siz=tree[cont].cnt=1;
tree[x].ls=cont;
}
}
else{
if(tree[x].rs!=0)
add(tree[x].rs,v);
else{
cont++;
tree[cont].val=v;
tree[cont].siz=tree[cont].cnt=1;
tree[x].rs=cont;
}
}
}
int queryfr(int x, int val, int ans) {
if (tree[x].val>=val)
{
if (tree[x].ls==0)
return ans;
else
return queryfr(tree[x].ls,val,ans);
}
else
{
if (tree[x].rs==0)
return (tree[x].val<val) ? tree[x].val : ans;
if (tree[x].cnt!=0)
return queryfr(tree[x].rs,val,tree[x].val);
else
return queryfr(tree[x].rs,val,ans);
}
}
int queryne(int x, int val, int ans) {
if (tree[x].val<=val)
{
if (tree[x].rs==0)
return ans;
else
return queryne(tree[x].rs,val,ans);
}
else
{
if (tree[x].ls==0)
return (tree[x].val>val)? tree[x].val : ans;
if (tree[x].cnt!=0)
return queryne(tree[x].ls,val,tree[x].val);
else
return queryne(tree[x].ls,val,ans);
}
}
int queryrk(int x,int rk)
{
if(x==0) return INF;
if(tree[tree[x].ls].siz>=rk)
return queryrk(tree[x].ls,rk);
if(tree[tree[x].ls].siz+tree[x].cnt>=rk)
return tree[x].val;
return queryrk(tree[x].rs,rk-tree[tree[x].ls].siz-tree[x].cnt);
}
int queryval(int x,int val)
{
if(x==0) return 0;
if(val==tree[x].val) return tree[tree[x].ls].siz+1;
if(val<tree[x].val) return queryval(tree[x].ls,val);
return queryval(tree[x].rs,val)+tree[tree[x].ls].siz+tree[x].cnt;
}
inline int read()
{
int r=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
r=(r<<3)+(r<<1)+(ch^48);
ch=getchar();
}
return r*w;
}
int main()
{
n=read();
while(n--){
opt=read();xx=read();
if(opt==1) printf("%d\n",queryval(1,xx)+1);
else if(opt==2) printf("%d\n",queryrk(1,xx));
else if(opt==3) printf("%d\n",queryfr(1,xx,-INF));
else if(opt==4) printf("%d\n",queryne(1,xx,INF));
else{
if(cont==0){
cont++;
tree[cont].cnt=tree[cont].siz=1;
tree[cont].val=xx;
}
else add(1,xx);
}
}
return 0;
}
以上题解搬运自洛谷
网友评论