记录编号	272331	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]排名系统	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	2.550 s
提交时间	2016-06-16 20:17:44	内存使用	6.46 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
const int maxn=300010;
const int INF=2147483647;
map<string,int>ID;
char c;
string name[maxn],str;
int rt,cnt,fa[maxn],ch[maxn][2],sz[maxn],key[maxn];
 
void Push_up(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
}
 
void Rotate(int x){
	int y=fa[x],g=fa[y],c=ch[y][1]==x;
	ch[y][c]=ch[x][c^1];
	if(ch[x][c^1])fa[ch[x][c^1]]=y;
	ch[x][c^1]=y;fa[y]=x;fa[x]=g;
	if(g)ch[g][ch[g][1]==y]=x;
	Push_up(y);
}
 
void Splay(int x,int g=0){
	for(int y;(y=fa[x])!=g;Rotate(x))
		if(fa[y]!=g)Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
	Push_up(x);
	if(!g)rt=x;
}
 
void Get_LR(int x,int &l,int &r){
	Splay(x);
	l=ch[x][0];r=ch[x][1];
	while(ch[l][1])l=ch[l][1];
	while(ch[r][0])r=ch[r][0];
}
 
void Delete(int x){
	int l,r;
	Get_LR(x,l,r);
	Splay(l);Splay(r,rt);
	ch[ch[rt][1]][0]=0;
	Push_up(ch[rt][1]);
	Push_up(rt);
}
 
void Insert(int &p,int f,int id,int x){
	if(!p){
		key[p=id]=x;
		fa[p]=f;
		sz[p]=1;
		Splay(p);
		return;
	}
	sz[p]+=1;
	Insert(ch[p][key[p]<x],p,id,x);
}
 
int Get_ID(int k){
	int p=rt;
	while(true){
		if(sz[ch[p][0]]+1==k)break;
		if(sz[ch[p][0]]+1>k)p=ch[p][0];
		else k-=sz[ch[p][0]]+1,p=ch[p][1];
	}
	return p;
}
 
void Print(int p){
	if(!p)return;
	Print(ch[p][1]);
	cout<<name[p]<<" ";
	Print(ch[p][0]);
}
 
void Init(){
	Insert(rt,0,1,-INF);
	Insert(rt,0,2,INF);cnt=2;
}
 
int main(){
#ifndef ONLINE_JUDGE
	freopen("rank.in","r",stdin);
	freopen("rank.out","w",stdout);
#endif
	Init();
	int Q,d,tot=0;
	scanf("%d",&Q);
	while(Q--){
		do c=getchar();
		while(c!='+'&&c!='?');
	
		if(c=='+'){	
			cin>>str;
			scanf("%d",&d);
			if(ID[str]){
				Delete(ID[str]);
				Insert(rt,0,ID[str],d);
			}
			else{
				ID[str]=++cnt;tot+=1;name[cnt]=str;
				Insert(rt,0,ID[str],d);
			}
		}
		else{
			cin>>str;
			if(str[0]<='9'&&str[0]>='0'){
				int l,r=0;
				for(int i=0;str[i];i+=1)
					r=r*10+(str[i]-'0');
				r=tot-r+1;l=max(r-9,1);
				Splay(Get_ID(l));Splay(Get_ID(r+2),rt);
				Print(ch[ch[rt][1]][0]);
				printf("\n");
			}
			else{
				Splay(Get_ID(1));Splay(ID[str],rt);
				printf("%d\n",tot-sz[ch[ch[rt][1]][0]]);
			}	
		}
	}
	return 0;
}