【洛谷P2584】【ZJOI2006】GameZ游戏排名系统题解
题目链接
题意：
GameZ为他们最新推出的游戏开通了一个网站。世界各地的玩家都可以将自己的游戏得分上传到网站上。这样就可以看到自己在世界上的排名。得分越高，排名就越靠前。当两个玩家的名次相同时，先上传记录者优先。由于新游戏的火爆，网站服务器已经难堪重负。为此GameZ雇用了你来帮他们重新开发一套新的核心。
排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。
输入格式：
第一行是一个整数n（n>=10）表示请求总数目。
接下来n行每行包含了一个请求。请求的具体格式如下：
+Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多10位的正整数。
?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。
?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。输入文件总大小不超过2M。
NOTE：用C++的fstream读大规模数据的效率较低
输出格式：
对于每条查询请求，输出相应结果。
对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。
对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。
样例输入：
+ADAM
+BOB
+TOM
+CATHY
?TOM
?
+DAM
+BOB
+ADAM
+FRANK
+LEO
+KAINE
+GRACE
+WALT
+SANDY
+MICK
+JACK
?
?
?KAINE
样例输出：
CATHY TOM ADAM BOB
CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM
时空限制：
每个测试点1s，128MB
数据范围：
n≥10
输入文本大小≤2MB
得分Score是最多十位的正整数
名字字符串最多十位
题解：
明显是一道Splay的题，不过还是需要一些技巧。
2MB文本太大怎么读入？题目已经提示用fstream很慢，所以我们在读入整数时用快读，读入字符串时一个一个getchar而不是用C++的string。
怎么知道字符串对应的节点？用map！
怎么知道节点对应的字符串？我们可以把字符串的Hash值存入节点中，注意这里Hash不用取模，因为字符串最多10位，而且取模后从Hash值还原成字符串是一件十分困难的事。
Splay一定要用双旋！一定要用双旋！一定要用双旋！不然会被极端数据（能够把Splay退化成链的）卡掉。
除此之外，还需要一些卡常技巧（如把i++改成++i，自己定义min和max代替algorithm中的，在函数前加inline）。
参考代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define max(a,b) ((a)>(b)?a:b)
#define min(a,b) ((a)<(b)?a:b)
#define ll long long
#define maxid 250005
using namespace std;
struct Splay{
int ch[],fa,times,size;
ll score,hash;
Splay(){
ch[]=ch[]=fa=times=size=score=hash=;
}
Splay(int f,ll has,ll scr,int tms){//新建节点的构造函数
ch[]=ch[]=;
fa=f;
times=tms;
size=;
score=scr;
hash=has;
}
}node[maxid];
map<ll,int>tono;//Hash映射到Splay节点的编号
int splayid=,super;//super是Splay大根的下标
inline void maintain(int p){
node[p].size=node[node[p].ch[]].size+node[node[p].ch[]].size+;
}
inline void rot(int&p,int lr){//0:左旋 1:右旋
int faa=node[p].fa;
int k=node[p].ch[lr^];
node[p].ch[lr^]=node[k].ch[lr];
node[node[p].ch[lr^]].fa=p;
maintain(p);
node[p].fa=k;
node[k].ch[lr]=p;
maintain(k);
node[k].fa=faa;
p=k;
}
inline void ins(int&p,int fa,ll hash,ll score,int times){//插入节点
if(!p){//新建节点
node[p=++splayid]=Splay(fa,hash,score,times);
return;
}
if(node[p].score!=score?node[p].score<score:node[p].times>times)ins(node[p].ch[],p,hash,score,times);
else ins(node[p].ch[],p,hash,score,times);
maintain(p);
}
inline int qrank(int p){//查询节点p的排名
int ans=node[node[p].ch[]].size+;
int fa=node[p].fa;
while(fa){
if(p==node[fa].ch[])ans+=node[node[fa].ch[]].size+;
p=fa;
fa=node[p].fa;
}
return ans;
}
inline int qid(int p,int rank){//查询排名为rank的节点
if(rank<=node[node[p].ch[]].size)return qid(node[p].ch[],rank);
else if(rank==node[node[p].ch[]].size+)return p;
else return qid(node[p].ch[],rank-node[node[p].ch[]].size-);
}
inline void splay(int p){//将p旋到根
int fa=node[p].fa;
while(fa){//还没到根节点
int ga=node[fa].fa;//爷爷
if(ga&&((node[ga].ch[]==fa&&node[fa].ch[]==p)||(node[ga].ch[]==fa&&node[fa].ch[]==p))){//一字型，双旋
int&pt=node[ga].fa?(node[node[ga].fa].ch[]==ga?node[node[ga].fa].ch[]:node[node[ga].fa].ch[]):super;
if(node[ga].ch[]==fa){
rot(pt,);
rot(pt,);
}else{
rot(pt,);
rot(pt,);
}
p=pt;
fa=node[p].fa;
}else{//普通单旋
int&pt=ga?(node[ga].ch[]==fa?node[ga].ch[]:node[ga].ch[]):super;
if(p==node[fa].ch[])rot(pt,);
else rot(pt,);
p=pt;
fa=node[p].fa;
}
}
}
bool toright;//是否到达了右哨兵
inline void pt(ll hash){//打印字符串
if(!hash){
toright=;
return;
}
char s[];
s[]=;
int pos=;
while(hash){
s[--pos]=hash%-+'A';
hash/=;
}
printf("%s ",s+pos);
}
inline void print(int&p,int rank){//打印字符串
if(rank<=node[node[p].ch[]].size)print(node[p].ch[],rank);
else if(rank>+node[node[p].ch[]].size)print(node[p].ch[],rank-node[node[p].ch[]].size-);
else pt(node[p].hash);
}
inline ll rd(){//快读
ll ans=;
char c=;
while(c<''||c>'')c=getchar();
while(c>=''&&c<=''){
ans=ans*10LL+c-'';
c=getchar();
}
return ans;
}
int main(){
int n=rd();
ins(super,,,1000000000000000000LL,);//左（前）哨兵
ins(super,,,-1000000000000000000LL,);//右（后）哨兵
for(int times=;times<=n;++times){//时间顺序
char tp=;
while(tp!='+'&&tp!='?')tp=getchar();
if(tp=='+'){
ll hash=;
char ch=getchar();
while(ch>='A'&&ch<='Z'){
hash=hash*+ch-'A'+;//将字符串Hash，不用取模，因为最多只有10位字母
ch=getchar();
}
ll score=rd();
if(tono[hash]){//存在，需要先删除原来的节点
int rnk=qrank(tono[hash]);
splay(qid(super,rnk-));
splay(qid(super,rnk+));
if(node[node[super].ch[]].ch[]){
node[node[super].ch[]].ch[]=;
maintain(node[super].ch[]);
maintain(super);
}else{
int pre=node[node[super].ch[]].ch[];
node[super].ch[]=pre;
node[pre].fa=super;
maintain(super);
}
}
ins(super,,hash,score,times);
tono[hash]=splayid;
splay(splayid);
}else{
char ch=getchar();
if(ch>=''&&ch<=''){//查10个人名
int num=;
while(ch>=''&&ch<=''){
num=num*+ch-'';
ch=getchar();
}
toright=;
for(int i=;i<=;++i){
print(super,num+i);
if(toright)break;
splay(qid(super,num+i));
}
putchar('\n');
}else{//查排名
ll hash=;
while(ch>='A'&&ch<='Z'){
hash=hash*+ch-'A'+;
ch=getchar();
}
int ans=qrank(tono[hash]);
splay(tono[hash]);
printf("%d\n",ans-);//有左哨兵，所以要-1
}
}
}
return ;
}