记录编号	146578	评测结果	AAAAAAAAAAA
题目名称	[HAOI 2008]排名系统	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	1.170 s
提交时间	2015-01-18 08:08:30	内存使用	17.75 MiB

#include<cstdio>
#include<cstring>
#define C(i,j,k) c[c[i][j]][k]
using namespace std;
const int N = 250010;
const int P = 999997;
struct data{
    int key,tim,next;char nam[12];
    data(){key=0;tim=1000000;next=0;}
    bool operator < (const data&a) const{
        if(key<a.key) return 1;
        if(key==a.key&&tim>a.tim) return 1;
        return 0;
    }
    bool operator > (const data&a) const{
        if(key>a.key) return 1;
        if(key==a.key&&tim<a.tim) return 1;
        return 0;
    }
    bool operator == (const data&a) const{
        if(key==a.key&&tim==a.tim) return 1;
        return 0;
    }
    bool operator >= (const data&a) const{if(*this>a)return 1;if(*this==a) return 1;return 0;}
    bool operator <= (const data&a) const{if(*this<a)return 1;if(*this==a) return 1;return 0;}
}F[N];
int key[N],siz[N],c[N][2],last[P];
int n,ot,ft,root,total;
char s[20];
inline bool cmp(char *s1,char *s2){
    int l=strlen(s1);
    if(l!=strlen(s2)) return 0;
    for(int i=0;i<l;i++) if(s1[i]!=s2[i]) return 0;
    return 1;
}
inline int Hash(char *s){
    int l=strlen(s);unsigned int hash=0;
    for(int i=0;i<l;i++)
        hash=hash*27+s[i]-'A'+1;
    return hash%P;
}
inline int Get(char *s){
    int hash=Hash(s),now=last[hash];
    while(now!=0){
        if(cmp(s,F[now].nam)==1) return now;
        now=F[now].next;
    }
    return 0;
}
inline void Rot(int &o,bool f){
    int t=c[o][!f];
    c[o][!f]=c[t][f];
    c[t][f]=o;
    siz[t]=siz[o];
    siz[o]=siz[c[o][0]]+siz[c[o][1]]+1;
    o=t;
    return;
}
inline void Maintain(int &o,bool f){
    if(siz[o]<=1) return;
    if(siz[C(o,f,f)] > siz[c[o][!f]]) Rot(o,!f);
    else if(siz[C(o,f,!f)] > siz[c[o][!f]]) Rot(c[o][f],f),Rot(o,!f);
    else return;
    Maintain(c[o][0],0);
    Maintain(c[o][1],1);
    Maintain(o,0);
    Maintain(o,1);
    return;
}
inline void Insert(int &o,int x){
    if(siz[o]==0){
        if(o==0) o=++ot;
        siz[o]=1;key[o]=x;
        return;
    }
    siz[o]++;
    bool f=(F[x]>=F[key[o]]);
    Insert(c[o][f],x);
    Maintain(o,f);
    return;
}
inline void Delete(int &o,int x){
    if(siz[o]==0) return;
    if(F[key[o]]==F[x]){
        if(siz[c[o][0]]==0) {o=c[o][1];return;}
        if(siz[c[o][1]]==0) {o=c[o][0];return;}
        int t=c[o][0];
        while(siz[c[t][1]]) t=c[t][1];
        siz[o]--;
        key[o]=key[t];
        Delete(c[o][0],key[o]);
        return;
    }
    siz[o]--;
    Delete(c[o][(F[x]>=F[key[o]])],x);
    return;
}
inline void Rank(int x){
    int o=root,ran=0;
    while(siz[o]){
        if(F[key[o]]>F[x]) ran+=siz[c[o][1]]+1,o=c[o][0];
        else o=c[o][1];
    }
    printf("%d\n",ran+1);
}
inline void Select(int x){
    int o=root,now;
    while(siz[o]){
        now=siz[c[o][1]]+1;
        if(now==x){
            for(int i=0;i<strlen(F[key[o]].nam);i++)
            printf("%c",F[key[o]].nam[i]);
            return;
        }
        else if(now>x) o=c[o][1];
        else x-=now,o=c[o][0];
    }
    return;
}
inline void Print(int o){
    if(siz[o]==0) return;
    Print(c[o][0]);
    for(int i=0;i<strlen(F[key[o]].nam);i++) printf("%c",F[key[o]].nam[i]);
    printf(" ");
    printf("%d %d\n",F[key[o]].key,F[key[o]].tim);
    Print(c[o][1]);
    return;
}
int main(){
	freopen("rank.in","r",stdin);
	freopen("rank.out","w",stdout);
    scanf("%d",&n);int x,now,pre;char ch;
    for(int i=1;i<=n;i++){
        while(ch=getchar(),ch!='?'&&ch!='+');
        scanf("%s",s);
        if(ch=='+'){
            scanf("%d",&x);
            pre=Get(s);now=Hash(s);
            ft++;F[ft].key=x;F[ft].tim=i;F[ft].next=last[now];
            memcpy(F[ft].nam,s,sizeof(s));
            if(pre==0) Insert(root,ft),total++;
            else Delete(root,pre),Insert(root,ft);
            last[now]=ft;
        }
        else{
            if(s[0]>='0'&&s[0]<='9'){
                x=0;int i;
                for(i=0;i<strlen(s);i++) x=x*10+s[i]-48;
                for(i=x;i<total&&i<x+9;i++) Select(i),printf(" ");
                Select(i);
                printf("\n");
            }
            else{
                now=Get(s);
                Rank(now);
            }
        }
    }
    return 0;
}