记录编号	283669	评测结果	AAAAAAAAAAE
题目名称	[HAOI 2008]排名系统	最终得分	90
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	1.174 s
提交时间	2016-07-15 10:25:59	内存使用	7.94 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=250010;
struct Key{
	char name[10];
	int k,num;
	bool operator > (const Key &x)const{return k==x.k?num>x.num:k<x.k;}
	bool operator == (const Key &x)const{return num==x.num;}
}now;
struct node{
	node *go[26];
	int k,num;
	node(){memset(go,0,sizeof go);k=num=0;}
}*root=new node(),*p;
void trie(){
	p=root;int len=strlen(now.name);
	for (int i=0;i<len;i++){
		int j=now.name[i]-'A';
		if (!p->go[j]) p->go[j]=new node();
		p=p->go[j];
	}
	swap(now.k,p->k);swap(now.num,p->num);
}
struct SBT{
	Key k[N];
	int l[N],r[N],s[N],x,top;
	void update(int x){
		s[x]=s[l[x]]+s[r[x]]+1;
	}
	void l_rotate(int &x){
		int y=r[x];
		r[x]=l[y];l[y]=x;
		update(x);update(y);
		x=y;
	}
	void r_rotate(int &x){
		int y=l[x];
		l[x]=r[y];r[y]=x;
		update(x);update(y);
		x=y;
	}
	void Maintain(int &x,bool y){
		if (!y){
			if (s[l[l[x]]]>s[r[x]]) r_rotate(x);else
			if (s[r[l[x]]]>s[r[x]]){
				l_rotate(l[x]);r_rotate(x);
			}else return;
		}
		else{
			if (s[r[r[x]]]>s[l[x]]) l_rotate(x);else
			if (s[l[r[x]]]>s[l[x]]){
				r_rotate(r[x]);l_rotate(x);
			}else return;
		}
		Maintain(l[x],0);Maintain(r[x],1);
		Maintain(x,1);Maintain(x,0);
	}
	void insert(int &x){
		if (x==0){
			x=++top;s[x]=1;k[x]=now;return;
		}
		s[x]++;
		insert(now>k[x]?r[x]:l[x]);
		Maintain(x,now>k[x]);
	}
	int rank(int x){
		int i=s[l[x]]+1;
		if (k[x]==now) return i;
		if (k[x]>now) return rank(l[x]);
			else return i+rank(r[x]);
	}
	int select(int x,int rank){
		int i=s[l[x]]+1;
		if (i==rank) return x;
		if (i>rank) return select(l[x],rank);
			else return select(r[x],rank-i);
	}
	void remove(int &x){
		s[x]--;
		if (k[x]==now){
			if (!l[x]||!r[x]){
				x=l[x]+r[x];return;
			}
			int y=select(r[x],1);
			swap(k[x],k[y]);
			remove(r[x]);
			return;
		}
		remove(now>k[x]?r[x]:l[x]);
	}
	/*int pred(Key &key){
		int i=rank(x,key);
		if (i==1) return -1;
		return select(x,i-1);
	}
	int succ(Key &key){
		int i=rank(x,key);
		if (i==s[x]) return -1;
		return select(x,i+1);
	}*/
}T;
int n,score,rank,num,_x,pos;char ch,c;
int read(){
	int len=strlen(now.name);_x=0;
	for (int i=0;i<len;i++) _x=_x*10+now.name[i]-'0';
	return _x;
}
int main()
{
	freopen("rank.in","r",stdin);
	freopen("rank.out","w",stdout); 
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		for (ch=getchar();ch!='+'&&ch!='?';ch=getchar());
		scanf("%s",now.name);
		if (ch=='+'){
			scanf("%d\n",&score);
			now.num=i;now.k=score;
			trie();
			if (now.num) T.remove(T.x);
			now.num=i;now.k=score;
			T.insert(T.x);
		}
		else{
			if (now.name[0]>='A'&&now.name[0]<='Z'){
				trie();
				num=now.num;score=now.k;
				trie();
				now.num=num;now.k=score;
				printf("%d\n",T.rank(T.x));
			}
			else{
				rank=read();
				for (int i=1;i<=10;i++){
					if (rank>T.s[T.x]) break;
					now=T.k[T.select(T.x,rank)];
					printf("%s ",now.name);
					rank++;
				}
				putchar('\n');
			}
		}
	}
	return 0;
}