COGS 197 [HAOI2008] 排名系统

　　　　　　　　　　　　　　　　　　★★★☆ 输入文件：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

20
+ADAM 1000000
+BOB 1000000
+TOM 2000000
+CATHY 10000000
?TOM
?1
+DAM 100000
+BOB 1200000
+ADAM 900000
+FRANK 12340000
+LEO 9000000
+KAINE 9000000
+GRACE 8000000
+WALT 9000000
+SANDY 8000000
+MICK 9000000
+JACK 7320000
?2
?5
?KAINE

Output

2
CATHY TOM ADAM BOB
CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM
4

说明：

+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.....)建立联系，方便建树。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #include<queue>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long LL;

 const LL maxn=,base=;

 map<unsigned LL,LL> m;

 char s[],sname[maxn][];

 unsigned long long hash;

 LL totnum,tottime,Time[maxn],num[maxn];

 LL N,tot,root;

 LL tim[maxn],key[maxn],name[maxn],siz[maxn],lc[maxn],rc[maxn];

 void r_rotate(LL &rt){

     LL k=lc[rt];

     lc[rt]=rc[k];

     rc[k]=rt;

     siz[k]=siz[rt];

     siz[rt]=siz[lc[rt]]+siz[rc[rt]]+;

     rt=k;

 }

 void l_rotate(LL &rt){

     LL k=rc[rt];

     rc[rt]=lc[k];

     lc[k]=rt;

     siz[k]=siz[rt];

     siz[rt]=siz[lc[rt]]+siz[rc[rt]]+;

     rt=k;

 }

 void Maintain(LL &rt,bool flag){

     if(flag==false){

         if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt);

         else if(siz[rc[lc[rt]]]>siz[rc[rt]]){

             l_rotate(lc[rt]);

             r_rotate(rt);

         }

         else return;

     }

     else{

         if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt);

         else if(siz[lc[rc[rt]]]>siz[lc[rt]]){

             r_rotate(rc[rt]);

             l_rotate(rt);

         }

         else return;

     }

     Maintain(lc[rt],); Maintain(rc[rt],);

     Maintain(rt,); Maintain(rt,);

 }

 void insert(LL &rt,LL player,LL v){

     if(rt==){

         rt=++tot;

         name[rt]=player; key[rt]=v; tim[rt]=Time[player]; //每个节点维护玩家姓名，记录，时间

         lc[rt]=rc[rt]=;

         siz[rt]=;

         return ;

     }

     siz[rt]++;

     if(v>key[rt]) insert(lc[rt],player,v);//排名系统要求key值越大排名越靠前,key值相同，tim值靠后的放在右子树

     else insert(rc[rt],player,v);

     Maintain(rt,false); Maintain(rt,true);

 }

 void Delete(LL &rt,LL t,LL v){//删除时间为 t，记录为 v的玩家数据

     if((v>key[rt]&&lc[rt]==)||(v<key[rt]&&rc[rt]==)) return ;

     siz[rt]--;

     if(v==key[rt]){

         if(t==tim[rt]){

             if(lc[rt]==||rc[rt]==) rt=lc[rt]+rc[rt];

             else{

                 LL u=lc[rt];

                 while(rc[u]!=) u=rc[u];

                 name[rt]=name[u]; key[rt]=key[u]; tim[rt]=tim[u];

                 Delete(lc[rt],tim[u],key[u]);

             }

         }

         else if(t<tim[rt]) Delete(lc[rt],t,v);//tim值小的在左子树

         else Delete(rc[rt],t,v);

         return ;

     }

     if(v>key[rt]) Delete(lc[rt],t,v);

     else Delete(rc[rt],t,v);

 }

 LL rank(LL &rt,LL t,LL v){

     if(rt==) return (LL);

     if(v==key[rt]){

         if(t==tim[rt]) return siz[lc[rt]]+(LL);

         else if(t<tim[rt]) return rank(lc[rt],t,v);

         else return siz[lc[rt]]+(LL)+rank(rc[rt],t,v);

     }

     if(v>key[rt]) return rank(lc[rt],t,v);

     else return siz[lc[rt]]+(LL)+rank(rc[rt],t,v);

 }

 LL select(LL &rt,LL k){

     if(k==siz[lc[rt]]+) return name[rt];

     if(k< siz[lc[rt]]+) return select(lc[rt],k);

     else return select(rc[rt],k-siz[lc[rt]]-);

 }

 int main(){

     scanf("%lld",&N);

     for(LL i=,tmp=;i<=N;i++){

         scanf("%s",s);

         if(s[]>''||s[]<''){//是 +Name 或 ?Name

             for(LL i=;i<strlen(s);i++) hash=hash*base+s[i]-'A'+; //哈希

             if(s[]=='+'){//添加记录

                 scanf("%lld",&tmp);

                 if(m[hash]==){//是新人

                     m[hash]=++totnum;// 建立map联系 hash值-->玩家编号

                     for(int i=;i<strlen(s);i++)  sname[totnum][i-]=s[i];// 玩家编号-->名字

                 }

                 else Delete(root,Time[m[hash]],num[m[hash]]);//已经有过，删除记录，时间 记录两个关键字都要保证 

                 num[m[hash]]=tmp; Time[m[hash]]=++tottime;//时间要改变

                 insert(root,m[hash],tmp);

             }

             else{

                 printf("%d\n",rank(root,Time[m[hash]],num[m[hash]]));//查询排名

             }

         }

         else{// ?Index 返回自第 Index 名开始的最多10名玩家名字

             tmp=;

             for(int i=;i<strlen(s);i++)  tmp=tmp*+s[i]-'';

             for(int i=tmp;i<=tmp+&&i<=siz[root];i++){

                 int j=select(root,i);//找到玩家编号

                 if(i!=tmp) printf(" ");

                 printf("%s",sname[j]);

             }

             printf("\n");

         }

         hash=;

     }

     return ;

 }

巴特西

COGS 197 [HAOI2008] 排名系统

最新文章

热门文章