题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1862
** http://www.lydsy.com/JudgeOnline/problem.php?id=1056**
思路：用一棵平衡树维护用户分数排名，然后用一棵Trie或者是HASH来维护用户ID。（看到P1862的内存64M果断放弃前缀树写HASH~~）（注：样例里的那些乱七八糟的注释还有回车之类的其实是没有的。）
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <iostream>
using namespace std;
#define MAX 801959
//------------------------Size_Balanced_Tree------------------------------------
struct node {
string name;
int S,T,s;
node *left,*right;
};
node *bank=new(node),*roof;
void INIT_SBT(){
bank->s=0;
roof=bank->left=bank->right=bank;
srand(29);
}
void left_ratote(node* &t){
node *k=t->right;
t->right=k->left;
t->s=t->left->s+t->right->s+1;
k->left=t;
k->s=k->left->s+k->right->s+1;
t=k;
}
void right_ratote(node* &t){
node *k=t->left;
t->left=k->right;
t->s=t->left->s+t->right->s+1;
k->right=t;
k->s=k->left->s+k->right->s+1;
t=k;
}
void maintain(node* &t){
if (t->left->left->s>t->right->s){
right_ratote(t);
maintain(t->right);
maintain(t);
return ;
}
if (t->left->right->s>t->right->s){
left_ratote(t->left);
right_ratote(t);
maintain(t->left);
maintain(t->right);
maintain(t);
return ;
}
if (t->right->right->s>t->left->s){
left_ratote(t);
maintain(t->left);
maintain(t);
return ;
}
if (t->right->left->s>t->left->s){
right_ratote(t->right);
left_ratote(t);
maintain(t->left);
maintain(t->right);
maintain(t);
return ;
}
}
void INSERT(int S,int T,string name,node* &t){
if (t==bank){
t=new(node);
t->s=1;
t->S=S;
t->T=T;
t->name=name;
t->left=t->right=bank;
return ;
}
t->s++;
if (S<t->S||(S==t->S&&T>t->T)){
INSERT(S,T,name,t->left);
} else INSERT(S,T,name,t->right);
maintain(t);
}
void DELETE(int S,int T,node* &t){
if (S==t->S&&T==t->T){
if (t->left==bank&&t->right==bank){
delete(t);
t=bank;
return ;
}
if (t->left==bank){
node *k=t->right;
delete(t);
t=k;
return ;
}
if (t->right==bank){
node *k=t->left;
delete(t);
t=k;
return ;
}
if (rand()%2){
left_ratote(t);
DELETE(S,T,t->left);
} else {
right_ratote(t);
DELETE(S,T,t->right);
}
} else
if (S<t->S||(S==t->S&&T>t->T)){
DELETE(S,T,t->left);
} else {
DELETE(S,T,t->right);
}
t->s=t->left->s+t->right->s+1;
maintain(t);
}
string select(int rank,node *t){
if (rank-1==t->right->s){
return t->name;
}
if (rank-1<t->right->s){
return select(rank,t->right);
} else return select(rank-t->right->s-1,t->left);
}
int rank(int S,int T,node *t){
if (t==bank){
return 0;
}
if (t->S==S&&T==t->T){
return t->right->s;
}
if (S<t->S||(S==t->S&&T>t->T)){
return rank(S,T,t->left)+t->right->s+1;
} else return rank(S,T,t->right);
}
//--------------------------Hash------------------------------------------------
const int p[10]={399239,159017,76207,39971,18313,10657,6133,5371,1987,541};
int hash(string s){
int rec=0;
for (int i=0;i<s.size();i++){
rec+=p[i]*(int(s[i])-int('0'));
rec%=MAX;
}
return rec;
}
string Name[MAX];
int S[MAX],T[MAX];
void INIT_HASH(){
memset(S,0,sizeof(S));
memset(T,0,sizeof(T));
}
//--------------------------------------------------------------------------------
int n,N=0;
int main(){
INIT_SBT();
INIT_HASH();
scanf("%d",&n);
for (int i=0;i++<n;){
char s[100];
scanf("%s",&s);
if (s[0]=='+'){
string c;
c="";
for (int j=1;j<strlen(s);j++){
if (s[j]>='A'&&s[j]<='Z'){
c=c+s[j];
} else break;
}
int x;
scanf("%d",&x);
int y=hash(c);
bool flag=false;
while (T[y]){
if (Name[y]==c){
flag=true;
break;
};
y++;
y%=MAX;
}
if (flag){
DELETE(S[y],T[y],roof);
} else N++;
S[y]=x;
T[y]=i;
Name[y]=c;
INSERT(S[y],T[y],Name[y],roof);
} else {
if (s[1]>='A'&&s[1]<='Z'){
string c;
c="";
for (int j=1;j<strlen(s);j++){
if (s[j]>='A'&&s[j]<='Z'){
c=c+s[j];
} else break;
}
int y=hash(c);
while (Name[y]!=c){
y++;
y%=MAX;
}
printf("%d\n",rank(S[y],T[y],roof)+1);
} else {
int x=0;
for (int j=1;j<strlen(s);j++){
if (s[j]>='0'&&s[j]<='9'){
x*=10;
x+=int(s[j])-int('0');
} else break;
}
for (int j=x;j<=min(x+9,N)-1;j++){
string c=select(j,roof);
for (int k=0;k<c.size();k++) {
printf("%c",c[k]);
}
printf(" ");
}
string c=select(min(N,x+9),roof);
for (int j=0;j<c.size();j++) printf("%c",c[j]);
printf("\n");
}
}
}
return 0;
}
