题解
双关键字平衡树。
其实也没什么，跟排序的时候写两个关键字一样操作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
using namespace std;
typedef long long ll;
struct Tr{
Tr *ch[2];
int r,v,siz,tim;
char name[12];
int cmp(int x,int tt) const {
if(x==v&&tt==tim)return -1;
return x==v?tt>tim:x>v;
}
void maintain(){
siz=1;
if(ch[0]!=NULL)siz+=ch[0]->siz;
if(ch[1]!=NULL)siz+=ch[1]->siz;
}
};
Tr tree[400005],*ans;
int S=0,n,T;
char ord[12];
map<unsigned int,int> mp1;//最近一次得分
map<unsigned int,int> mp2;//最近一次插入
void rorate_tr(Tr* &tr,int d){
Tr *k=tr->ch[d^1];
tr->ch[d^1]=k->ch[d];
k->ch[d]=tr;
tr->maintain(),k->maintain(),tr=k;
}
void insert_tr(Tr* &tr,int x,int tt){
if(tr==NULL){
S++,tr=&tree[S],tr->siz=1,tr->v=x,tr->tim=tt;
tr->ch[0]=tr->ch[1]=NULL,tr->r=rand();
memcpy(tr->name,ord,sizeof(ord));
return ;
}
tr->siz++;
int d=tr->cmp(x,tt);
insert_tr(tr->ch[d],x,tt);
if(tr->ch[d]->r>tr->r)rorate_tr(tr,d^1);
}
void del(Tr* &tr,int x,int tt){
int d=tr->cmp(x,tt);
if(d==-1){
if(tr->ch[0]==NULL)tr=tr->ch[1];
else if(tr->ch[1]==NULL)tr=tr->ch[0];
else{
int d_=(tr->ch[0]->r>tr->ch[1]->r);
rorate_tr(tr,d_),tr->siz--,del(tr->ch[d_],x,tt);
}
}else tr->siz--,del(tr->ch[d],x,tt);
}
Tr* Kth(Tr *tr,int x){
if(tr==NULL||x<=0||x>tr->siz)return NULL;
int evid=(tr->ch[0]==NULL)?0:tr->ch[0]->siz;
if(x<=evid)return Kth(tr->ch[0],x);
else if(x>evid+1)return Kth(tr->ch[1],x-evid-1);
else return tr;
}
int Rank(Tr *tr,int x,int tt){
if(tr==NULL)return 0;
int evid=(tr->ch[0]==NULL)?0:tr->ch[0]->siz;
if(tr->cmp(x,tt)<0)return evid+1;
if(!tr->cmp(x,tt))return Rank(tr->ch[0],x,tt);
else return evid+1+Rank(tr->ch[1],x,tt);
}
bool Find(Tr *tr,int x){
while(tr!=NULL){
if(tr->v==x)return true;
else tr=tr->ch[(tr->v<x)];
}
return false;
}
unsigned int Hash(char *s){
unsigned int res=0;
for(;*s;s++)res=res*133u+*s;
return res;
}
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
void solve(){
n=read(),T=0;
Tr *root=NULL;
while(n--){
scanf("%s",ord);
if(ord[0]=='+'){
int u=-read(),pre,close;
unsigned int code=Hash(ord+1);
pre=mp1[code],close=mp2[code];
//上一次的得分和插入时间
if(pre&&Find(root,pre))
del(root,pre,close);
mp1[code]=u,mp2[code]=T,insert_tr(root,u,T);
}else if(isdigit(ord[1])){
int rk=atoi(ord+1);
for(int i=0;i<10;i++){
ans=Kth(root,rk+i);
if(ans==NULL)break;
if(i)printf(" ");
printf("%s",ans->name+1);
}
printf("\n");
}else {
unsigned int code=Hash(ord+1);
int pre=mp1[code],close=mp2[code];
printf("%d\n",Rank(root,pre,close));
}
T++;
}
}
int main(){
solve();
return 0;
}