BZOJ1862: [Zjoi2006]GameZ游戏排名系统
GameZ为他们最新推出的游戏开通了一个网站。世界各地的玩家都可以将自己的游戏得分上传到网站上。这样就可以看到自己在世界上的排名。得分越高，排名就越靠前。当两个玩家的名次相同时，先上传记录者优先。由于新游戏的火爆，网站服务器已经难堪重负。为此GameZ雇用了你来帮他们重新开发一套新的核心。排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。
第一行是一个整数n（n>=10）表示请求总数目。接下来n行每行包含了一个请求。请求的具体格式如下： +Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多8位的正整数。 ?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。 ?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。输入文件总大小不超过2M。 NOTE：用C++的fstream读大规模数据的效率较低
对于每条查询请求，输出相应结果。对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。
这个操作显然就是两种情况：
1. 原本没有，那就插入平衡树
2. 原本有，那就先删除原来的，再插入更新后的。
但是怎么找到这个人在平衡树中对应的节点呢？
我们使用了$STL$——已经封装好的$map$！~
有现成的为什么不用呢？
于是这个问题就完美解决了。
用$map$找到对应节点，伸展到根，然后其左子树的大小即为排名。
为什么不减一呢？
因为我们为了操作三，设立了两个哨兵节点。
本蒟蒻一开始的想法是一个一个$kth$，然后$TLE$到爆炸。。。
其实只要把十个节点单独拎出来，按照其后序遍历输出名字即可。
好了，这个题就做完了。
然后本蒟蒻还$RE\times2$，原因是在建立新的节点时，$newnode$函数没有返回值。。。
尴尬到极致。。。
最后，这个题我还手写读入、手写输出的。。。
然后具体的细节看代码吧。
附代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
#define MAXN 1000010
#define MAX 2147483646
using namespace std;
map<string,int> id;
int root=0,size=0;
struct Splay{
int f,s,son[2];
int v;
string name;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
string input_que(int &f,int &val){
char ch[15];
string name="";
val=0;
scanf("%s",ch);
if(ch[0]==‘+‘){
f=1;
int l=strlen(ch);
for(int i=1;i<l;i++)name+=ch[i];
val=read();
return name;
}
else{
if(ch[1]>=‘0‘&&ch[1]<=‘9‘){
f=3;
int l=strlen(ch);
for(int i=1;i<l;i++)val=val*10+ch[i]-‘0‘;
return name;
}
else{
f=2;
int l=strlen(ch);
for(int i=1;i<l;i++)name+=ch[i];
return name;
}
}
return name;
}
void output(string name){
for(int i=0;i<name.size();i++)putchar(name[i]);
putchar(‘ ‘);
}
void print(int rt){
if(!rt)return;
if(a[rt].son[1])print(a[rt].son[1]);
output(a[rt].name);
if(a[rt].son[0])print(a[rt].son[0]);
}
inline void clean(int rt){
a[rt].f=a[rt].s=a[rt].son[1]=a[rt].son[2]=a[rt].v=0;
a[rt].name="";
}
inline void pushup(int rt){
if(!rt)return;
a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+1;
}
inline void turn(int rt,int k){
int x=a[rt].f,y=a[x].f;
a[x].son[k^1]=a[rt].son[k];
if(a[rt].son[k])a[a[rt].son[k]].f=x;
a[rt].f=y;
if(y)a[y].son[a[y].son[1]==x]=rt;
a[x].f=rt;
a[rt].son[k]=x;
pushup(x);pushup(rt);
}
void splay(int rt,int ancestry){
while(a[rt].f!=ancestry){
int x=a[rt].f,y=a[x].f;
if(y==ancestry)turn(rt,a[x].son[0]==rt);
else{
int k=a[y].son[0]==x?1:0;
if(a[x].son[k]==rt){turn(rt,k^1);turn(rt,k);}
else{turn(x,k);turn(rt,k);}
}
}
if(ancestry==0)root=rt;
}
inline int newnode(int fa,string name,int v){
int rt=++size;
a[rt].son[0]=a[rt].son[1]=0;
if(fa)a[fa].son[a[fa].v<v]=rt;
a[rt].v=v;a[rt].f=fa;
a[rt].s=1;a[rt].name=name;
id[name]=rt;
return rt;
}
void insert(int rt,string name,int v){
int fa=0;
while(rt){
fa=rt;
rt=a[rt].son[a[rt].v<v];
}
rt=newnode(fa,name,v);
splay(rt,0);
}
int kth(int rt,int k){
if(k<1)k=1;
while(1){
int y=a[rt].son[0];
if(k>a[y].s+1){
k-=a[y].s+1;
rt=a[rt].son[1];
}
else if(k<=a[y].s)rt=y;
else return rt;
}
}
int front_next(int rt,int k){
rt=a[rt].son[k];
while(a[rt].son[k^1])rt=a[rt].son[k^1];
return rt;
}
void remove(int rt){
splay(rt,0);
int front=front_next(rt,0),next=front_next(rt,1),q;
splay(front,0);splay(next,front);
q=a[next].son[0];
a[next].son[0]=0;
clean(q);
pushup(next);pushup(front);
}
void update(string name,int v){
int x=id[name];
remove(x);
insert(root,name,v);
}
void get_rank(string name){
int x=id[name];
splay(x,0);
printf("%d\n",a[a[x].son[1]].s);
}
void get_name(int k){
k=a[root].s-k;
int next=kth(root,k+1),front=kth(root,k-10),q;
splay(front,0);splay(next,front);
q=a[next].son[0];
print(q);putchar(‘\n‘);
}
void work(){
string name;
int f,val;
int t=read();
while(t--){
name=input_que(f,val);
switch(f){
case 1:{
if(id[name])update(name,val);
else insert(root,name,val);
break;
}
case 2:{
get_rank(name);
break;
}
case 3:{
get_name(val);
break;
}
}
}
}
void init(){
insert(root," ",-1);insert(root," ",MAX);
}
int main(){
init();
work();
return 0;
}
BZOJ1862: [Zjoi2006]GameZ游戏排名系统
原文：https://www.cnblogs.com/Yangrui-Blog/p/9863844.html