学步园

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<ctime>
#define mod 985003
using namespace std;
struct data{
	int l,r,time,num,rnd,s;
	char ch[11];
}tr[250001];
struct data2{
	int num,time,next;
	char ch[11];
}hash[250001];
int n,size,root,tot,head[mod+1];
int Hash(char ch[]){//ch[0]是表示操作的字符 
	int s=0;
	for(int i=1;i<strlen(ch);i++)
		s=(s*27+ch[i]-'A'+1)%mod;
	return s;
}
void update(int k){
	tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;
} 
void lturn(int &k){
	int t=tr[k].r;
	tr[k].r=tr[t].l;
	tr[t].l=k;
	tr[t].s=tr[k].s;
	update(k);
	k=t;
}
void rturn(int &k){
	int t=tr[k].l;
	tr[k].l=tr[t].r;
	tr[t].r=k;
	tr[t].s=tr[k].s;
	update(k);
	k=t;
}
bool cmp(char a[],char b[]){
	if(strlen(a)!=strlen(b))return 0;
	for(int i=1;i<strlen(a);i++)
		if(a[i]!=b[i])return 0;
	return 1;
}
void insert(int &k,char ch[],int x,int time){
	if(k==0){
		k=++size;
		tr[k].rnd=rand();
		tr[k].num=x;
		tr[k].time=time;
		tr[k].s=1;
		memcpy(tr[k].ch,ch,strlen(ch));
		return;
	}
	tr[k].s++;
	if(x<=tr[k].num){
		insert(tr[k].l,ch,x,time);
		if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
	}
	else{
		insert(tr[k].r,ch,x,time);
		if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);
	}
}
void del(int &k,int x,int time){
	if(k==0)return;
	if(tr[k].num==x)
		if(tr[k].time==time){
			if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;
			else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd){
				rturn(k);del(k,x,time);
			}
			else{
				lturn(k);del(k,x,time);
			}
		}
		else if(tr[k].time<time){
			tr[k].s--;
			del(tr[k].l,x,time);
		}
		else{
			tr[k].s--;
			del(tr[k].r,x,time);
		}
	else if(x<tr[k].num){
		tr[k].s--;
		del(tr[k].l,x,time);
	}
	else{
		tr[k].s--;
		del(tr[k].r,x,time);
	}
}
void ins(char ch[],int x,int time){
	int k=Hash(ch),i=head[k];
	while(i){
		if(cmp(hash[i].ch,ch)){
			del(root,hash[i].num,hash[i].time);
			hash[i].num=x;hash[i].time=time;
			insert(root,ch,x,time);
			return;
		}
		i=hash[i].next;
	}
	hash[++tot].time=time;hash[tot].num=x;
	memcpy(hash[tot].ch,ch,strlen(ch));
	hash[tot].next=head[k];head[k]=tot;
	insert(root,ch,x,time);
}
int get(char ch[]){
	int k=Hash(ch),i=head[k];
	while(i){
		if(cmp(hash[i].ch,ch))return i;
		i=hash[i].next;
	}
}
int ask_rank(int k,int x,int time){
	if(k==0)return 0;
	if(tr[k].num==x){
		if(tr[k].time>time)return ask_rank(tr[k].r,x,time);
		else if(tr[k].time<time)return tr[tr[k].r].s+ask_rank(tr[k].l,x,time)+1;
		else return tr[tr[k].r].s+1;
	}
	else if(tr[k].num<x)return ask_rank(tr[k].r,x,time);
	else return tr[tr[k].r].s+ask_rank(tr[k].l,x,time)+1;
}
void ask1(char ch[]){
	int t=get(ch);
	printf("%d\n",ask_rank(root,hash[t].num,hash[t].time));
}
int index(int k,int x){
	if(tr[tr[k].r].s+1==x)return k;
	else if(x<=tr[tr[k].r].s)return index(tr[k].r,x);
	else return index(tr[k].l,x-tr[tr[k].r].s-1);
}
void ask2(char ch[]){
	int t=0;
	for(int i=1;i<strlen(ch);i++)
		t=t*10+ch[i]-'0';
	for(int i=t;i<=min(tot,t+9);i++){
		printf("%s",tr[index(root,i)].ch+1);
		if(i<min(tot,t+9))printf(" ");
	}
	printf("\n");
}
int main(){
	scanf("%d",&n);
	char oper[11];int t;
	for(int i=1;i<=n;i++){
		scanf("%s",oper);
		if(oper[0]=='+'){
			scanf("%d",&t);
			ins(oper,t,i);
		}
		else{
			if(oper[1]>='0'&&oper[1]<='9')ask2(oper);
			else ask1(oper);
		}
	}
	return 0;
}