COGS 197 [HAOI2008] 排名系统-白红宇

COGS 197 [HAOI2008] 排名系统

阅读量：5806 次

发布时间：2019-06-18

本文共 4354 字，大约阅读时间需要 14 分钟。

　　　　　　　　　　　　　　　　　　★★★☆ 输入文件：rank.in 输出文件：rank.out 简单对比

　　　　　　　　　　　　　　　　　　　　时间限制：1 s 内存限制：128 MB

[题目描述]

排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。

[输入]

第一行是一个整数n（10<=n<=250000）表示请求总数目。接下来n行,每行包含了一个请求。请求的具体格式如下：

+Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多8位的正整数。

?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。如果两个玩家的得分相同，则先得到该得分的玩家排在前面。

?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。

[输出]

对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。

对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。

[样例]

Input

+ADAM 1000000

+BOB 1000000

+TOM 2000000

+CATHY 10000000

?TOM

+DAM 100000

+BOB 1200000

+ADAM 900000

+FRANK 12340000

+LEO 9000000

+KAINE 9000000

+GRACE 8000000

+WALT 9000000

+SANDY 8000000

+MICK 9000000

+JACK 7320000

?KAINE

Output

CATHY TOM ADAM BOB

CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB

WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM

说明：

+ADAM 1000000 加入ADAM的得分记录

+BOB 1000000 加入BOB的得分记录

+TOM 2000000 加入TOM的得分记录

+CATHY 10000000 加入CATHY的得分记录

?TOM 输出TOM目前排名

?1 目前有记录的玩家总数为4，因此应输出第1名到第4名。

+DAM 100000 加入DAM的得分记录

+BOB 1200000 更新BOB的得分记录

+ADAM 900000 更新ADAM的得分记录（即使比原来的差）

+FRANK 12340000 加入FRANK的得分记录

+LEO 9000000 加入LEO的得分记录

+KAINE 9000000 加入KAINE的得分记录

+GRACE 8000000 加入GRACE的得分记录

+WALT 9000000 加入WALT的得分记录

+SANDY 8000000 加入SANDY的得分记录

+MICK 9000000 加入MICK的得分记录

+JACK 7320000 加入JACK的得分记录

?2 目前有记录的玩家总数为12，因此应输出第2名到第11名。

?5 输出第5名到第13名。

?KAINE 输出KAINE的排名

[数据范围]

20%数据满足N<=100

100%数据满足N<=250000

题解：

　　用SBT维护每个玩家的记录和上传时间，以记录为第一关键字，时间为第二关键字。因为游戏排名记录越高排名越靠前，所以我让左子树>根>右子树。如果记录一样，时间不一样，时间靠后的往右子树走，时间靠前的往左子树走。

　　用map把字符串与玩家编号(1,2,3.....)建立联系，方便建树。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
              10 #include
              
                11 using namespace std; 12 typedef long long LL; 13 const LL maxn=250010,base=31; 14 map
               
                 m; 15 char s[100],sname[maxn][100]; 16 unsigned long long hash; 17 LL totnum,tottime,Time[maxn],num[maxn]; 18 LL N,tot,root; 19 LL tim[maxn],key[maxn],name[maxn],siz[maxn],lc[maxn],rc[maxn]; 20 void r_rotate(LL &rt){ 21 LL k=lc[rt]; 22 lc[rt]=rc[k]; 23 rc[k]=rt; 24 siz[k]=siz[rt]; 25 siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 26 rt=k; 27 } 28 void l_rotate(LL &rt){ 29 LL k=rc[rt]; 30 rc[rt]=lc[k]; 31 lc[k]=rt; 32 siz[k]=siz[rt]; 33 siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 34 rt=k; 35 } 36 void Maintain(LL &rt,bool flag){ 37 if(flag==false){ 38 if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt); 39 else if(siz[rc[lc[rt]]]>siz[rc[rt]]){ 40 l_rotate(lc[rt]); 41 r_rotate(rt); 42 } 43 else return; 44 } 45 else{ 46 if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt); 47 else if(siz[lc[rc[rt]]]>siz[lc[rt]]){ 48 r_rotate(rc[rt]); 49 l_rotate(rt); 50 } 51 else return; 52 } 53 Maintain(lc[rt],0); Maintain(rc[rt],1); 54 Maintain(rt,1); Maintain(rt,0); 55 } 56 void insert(LL &rt,LL player,LL v){ 57 if(rt==0){ 58 rt=++tot; 59 name[rt]=player; key[rt]=v; tim[rt]=Time[player]; //每个节点维护玩家姓名，记录，时间 60 lc[rt]=rc[rt]=0; 61 siz[rt]=1; 62 return ; 63 } 64 siz[rt]++; 65 if(v>key[rt]) insert(lc[rt],player,v);//排名系统要求key值越大排名越靠前,key值相同，tim值靠后的放在右子树 66 else insert(rc[rt],player,v); 67 Maintain(rt,false); Maintain(rt,true); 68 } 69 void Delete(LL &rt,LL t,LL v){ //删除时间为 t，记录为 v的玩家数据 70 if((v>key[rt]&&lc[rt]==0)||(v
                
                 key[rt]) Delete(lc[rt],t,v); 87 else Delete(rc[rt],t,v); 88 } 89 LL rank(LL &rt,LL t,LL v){ 90 if(rt==0) return (LL)0; 91 if(v==key[rt]){ 92 if(t==tim[rt]) return siz[lc[rt]]+(LL)1; 93 else if(t
                 
                  key[rt]) return rank(lc[rt],t,v); 97 else return siz[lc[rt]]+(LL)1+rank(rc[rt],t,v); 98 } 99 LL select(LL &rt,LL k){100 if(k==siz[lc[rt]]+1) return name[rt];101 if(k< siz[lc[rt]]+1) return select(lc[rt],k);102 else return select(rc[rt],k-siz[lc[rt]]-1);103 }104 int main(){105 scanf("%lld",&N);106 for(LL i=1,tmp=0;i<=N;i++){107 scanf("%s",s);108 if(s[1]>'9'||s[1]<'0'){ //是 +Name 或 ?Name 109 for(LL i=1;i
                  
                   玩家编号 114 for(int i=1;i
                   
                    名字 115 }116 else Delete(root,Time[m[hash]],num[m[hash]]);//已经有过，删除记录，时间 记录两个关键字都要保证 117 118 num[m[hash]]=tmp; Time[m[hash]]=++tottime;//时间要改变 119 insert(root,m[hash],tmp);120 }121 else{122 printf("%d\n",rank(root,Time[m[hash]],num[m[hash]]));//查询排名 123 }124 }125 else{ // ?Index 返回自第 Index 名开始的最多10名玩家名字126 tmp=0;127 for(int i=1;i