传送门：https://ac.nowcoder.com/acm/problem/19971

先记录下来，以后再学。神奇操作

 

题解

用到了C++ pb_ds库，真是一个神奇的库啊....

#include <ext/pb_ds/assoc_containe.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

定义一颗红黑树
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>t;

int 关键字类型
null_type无映射(低版本g++为null_mapped_type)
less<int>从小到大排序
rb_tree_tag 红黑树（splay_tree_tag）
tree_order_statistics_node_update结点更新
插入t.insert();
删除t.erase();
Rank:t.order_of_key();
第K值:t.find_by_order();
前驱:t.lower_bound();
后继t.upper_bound();

代码

 1 #include<bits/stdc++.h>
 2 #include<ext/pb_ds/assoc_container.hpp>
 3 #include<ext/pb_ds/tree_policy.hpp>
 4 using namespace std;
 5 using namespace __gnu_pbds;
 6 
 7 const int maxn=5e5+10;
 8 
 9 struct node
10 {
11     int val,id;
12     bool operator < (const node &rhs) const{
13         if(val!=rhs.val) return val>rhs.val;
14         return id<rhs.id;
15     }
16 };
17 
18 tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> T;
19 map<string,int>id;
20 string name[maxn];
21 int val[maxn];
22 int cnt=0,tot=0;
23 
24 int main()
25 {
26     int n;
27     cin>>n;
28     while(n--){
29         char ch;
30         string s;
31         cin>>ch>>s;
32         if(ch=='+'){
33             if(id[s]) T.erase((node){val[id[s]],id[s]}),tot--;
34             cin>>val[++cnt],id[s]=cnt,name[cnt]=s;
35             T.insert((node){val[cnt],cnt}),tot++;
36         }
37         else{
38             if(s[0]>='0'&&s[0]<='9'){
39                 int x=0,len=s.size();
40                 for(int i=0;i<len;i++) x=x*10+s[i]-'0';
41                     for(int i=x-1;i<min(tot,x+9);i++) cout<<name[T.find_by_order(i)->id]<<' ';
42                 cout<<endl;
43             }
44             else cout<<T.order_of_key((node){val[id[s]],id[s]})+1<<endl;
45         }
46     }
47     return 0;
48 }