记录编号	87805	评测结果	AAAAAAAATT
题目名称	[HAOI 2008]排名系统	最终得分	80
用户昵称	QWERTIer	是否通过	未通过
代码语言	C++	运行时间	3.707 s
提交时间	2014-02-10 15:13:14	内存使用	17.48 MiB

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<string>
#define For(i,n) for(int i=1; i<=n; i++)
#define Rep(i,n) for(int i=0; i<n; i++)
#define MP make_pair
#define N 500009

using namespace std;

FILE* fin=fopen("rank.in","r"),*fout=fopen("rank.out","w");

void readint(char *s,int &x){
  x=0;
  while(*s){
    x=x*10+*s-'0';
    s++;
  }
}
int dig[20],len;
void writeint(int x){
  len=0;
  while(x){
    dig[++len]=x%10;
    x/=10;
  }
  for(int i=len; i; --i)
    fputc(dig[i]+'0',fout);
}
void readstr(char *s){
  len=0;
  char c=fgetc(fin);
  while(c!='+'&&c!='?'&&!isdigit(c)&&!isalpha(c)){
    c=fgetc(fin);
  }
  while(!feof(fin)&&(c=='+'||c=='?'||isdigit(c)||isalpha(c))){
    s[len++]=c;
    c=fgetc(fin);
  }
  s[len]=0;
}
void writestr(char *s){
  while(*s)fputc(*s++,fout);
}

char name[N][20];
int score[N],ord[N],lh[N],ph[N],hcnt;
unsigned int hash(char *s){
  unsigned int ret=0;
  while(*s)ret=(*s++)+(ret<<6)+(ret<<16)-ret;
  return ret&0x7FFFFFFF;
}

struct Node{
  Node* ch[2];
  int r,s,sc,ord,idx;
  Node(int,int,int);
  inline void maintain(){
    s=ch[0]->s+ch[1]->s+1;
  }
  int cmp(int a,int b){
    if(sc==a&&ord==b)return -1;
    return sc>a||(sc==a&&ord<b);
  }
}*null,*root;
Node::Node(int a,int b,int c){
  this->sc=a;
  this->ord=b;
  this->idx=c;
  this->r=rand();
  this->s=1;
  ch[0]=ch[1]=null;
}
void rotate(Node* &o,int d){
  Node *k=o->ch[d];
  o->ch[d]=k->ch[1^d];
  k->ch[1^d]=o;
  o->maintain();
  k->maintain();
  o=k;
}
int xsc,xord;
void insert(Node* &o,int idx){
  if(o==null){
    o=new Node(xsc,xord,idx);
    return;
  }
  int d=o->cmp(xsc,xord);
  insert(o->ch[d],idx);
  if(o->r<o->ch[d]->r)
    rotate(o,d);
  o->maintain();
}
void erase(Node* &o){
  int d=o->cmp(xsc,xord);
  if(d==-1){
    if(o->ch[0]!=null&&o->ch[1]!=null){
      int d2=(o->ch[1]->r>o->ch[0]->r);
      rotate(o,d2);
      erase(o->ch[1^d2]);
    }else{
      Node *tmp=o;
      if(o->ch[0]==null)
    o=o->ch[1];
      else
    o=o->ch[0];
      delete tmp;
    }
  }else
    erase(o->ch[d]);
  if(o!=null)o->maintain();
}
int rank(Node* &o){
  int d=o->cmp(xsc,xord);
  if(d==-1)return o->ch[0]->s+1;
  return (o->ch[0]->s+1)*d+rank(o->ch[d]);
}
int L,R;
void print(Node* &o,int k){
  if(o==null)return;
  if(L<=k+o->ch[0]->s)print(o->ch[0],k);
  if(L<=k+o->ch[0]->s+1&&k+o->ch[0]->s+1<=R){writestr(name[o->idx]);fputc(' ',fout);}
  if(R>k+o->ch[0]->s+1)print(o->ch[1],k+o->ch[0]->s+1);
}
void init(){
  null=new Node(-1,-1,0);
  null->r=-1;
  null->ch[0]=null->ch[1]=null;
  null->s=0;
  root=null;
}
void dbg(Node *o,int depth,int rc){
  if(o==null)return;
  For(i,depth)putchar(' ');
  printf("%d name:%s sc:%d ord:%d s:%d\n",rc,name[o->idx],o->sc,o->ord,o->s);
  dbg(o->ch[0],depth+1,0);
  dbg(o->ch[1],depth+1,1);
}

int n;
char opt[20];
char numt[20];
int main(){
  init();
  fscanf(fin,"%d",&n);
  For(i,n){
    readstr(opt);
    if(opt[0]=='+'){
      int h=hash(opt+1)%N;
      int idx=0;
      for(int j=lh[h]; j; j=ph[j])
	if(!strcmp(name[j],opt+1)){
	  xsc=score[j];
	  xord=ord[j];
	  idx=j;
	  break;
	}
      if(idx)
	erase(root);
      readstr(numt);
      readint(numt,xsc);
      xord=i;
      if(!idx){
	hcnt++;
	idx=hcnt;
	ph[hcnt]=lh[h];
	strcpy(name[hcnt],opt+1);
	lh[h]=hcnt;
      }
      score[idx]=xsc;
      ord[idx]=xord;
      insert(root,idx);
    }else{
      if(isdigit(opt[1])){
	readint(opt+1,L);
	R=min(L+9,root->s);
	print(root,0);
	fputc('\n',fout);
      }else{
	int h=hash(opt+1)%N;
	int idx=0;
	for(int j=lh[h]; j; j=ph[j])
	  if(!strcmp(name[j],opt+1)){
	    xsc=score[j];
	    xord=ord[j];
	    idx=j;
	    break;
	  }
	//printf("query:%s %d %d\n",name[idx],xsc,xord);
	writeint(rank(root));
	fputc('\n',fout);
      }
    }
    //dbg(root,0,0);
  }
  return 0;
}