[原创][HAOI2008] 排名系统 & [ZJOI2006] GameZ游戏排名系统 [SPLAY]【数据结构】 [原创][HAOI2008] 排名系统 & [ZJOI2006] GameZ游戏排名系统 [SPLAY]【数据结构】
2017-06-28 02:52:41 Tabris_ 阅读数：355
博客爬取于2020-06-14 22:39:54以下为正文
版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/73825606
题目链接:http://codevs.cn/problem/1985/
GameZ为他们最新推出的游戏开通了一个网站。世界各地的玩家都可以将自己的游戏得分上传到网站上。这样就可以看到自己在世界上的排名。得分越高，排名就越靠前。当两个玩家的名次相同时，先上传记录者优先。由于新游戏的火爆，网站服务器已经难堪重负。为此GameZ雇用了你来帮他们重新开发一套新的核心。 排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。
输入描述 Input Description
输出描述 Output Description
样例输入 Sample Input
样例输出 Sample Output
数据范围及提示 Data Size & Hint
【数据范围】
首先这题考虑到玩家需要加分 ，那么就会产生一个新的排名，可以确定
因为排名是分数大的在前,所以是降序.我们可以在树上挂负值
那么考虑 怎么能在二叉排序树中找某个人的名字，？
这题光输入就很麻烦啊
名字 用一个map 映射成一个值就好了
一共两个map
其实还是很简单的 记录下分数 然后就找就行了
附本题代码
# include <bits/stdc++.h> typedef long long int LL ; using namespace std; const int N = 300000+7; const LL INF = 1000000000000000000LL; /******************************************************/ int n;string ss,s; map<string,LL>mmp; map<LL,string>mmp2; int ch[N][2]; //ch[][0] lson ch[][1] rson int f[N]; //father int sz[N]; //size LL val[N]; //value of node_i int cnt[N]; // counts of the node_i int root; //root of splay-tree int tot; //tot,total,is the number of node of tree void pushup(int x){ if(x)sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x]; } void rotate(int x,int k){ // k = 0 左旋， k = 1 右旋 int y=f[x];int z=f[y]; ch[y][!k]=ch[x][k];if(ch[x][k])f[ch[x][k]]=y; f[x]=z;if(z)ch[z][ch[z][1]==y]=x; f[y]=x;ch[x][k]=y; pushup(y),pushup(x); } void splay(int x,int goal){ for(int y=f[x];f[x]!=goal;y=f[x]) rotate(x,(ch[y][0]==x)); if(goal==0) root=x; } void newnode(int rt,LL v,int fa){ f[rt]=fa;val[rt]=v,sz[rt]=cnt[rt]=1; ch[rt][0]=ch[rt][1]=0; } void delnode(int &rt){ //其实是为内存回收做准备的 回头再完善 f[rt]=val[rt]=sz[rt]=cnt[rt]=0; ch[rt][0]=ch[rt][1]=rt=0; } /***************************以下是DEBUG***************************/ void Traversal(int rt){ if(!rt) return; Traversal(ch[rt][0]); printf("%d f[]=%d sz[]=%d lson=%d rson=%d val[]=%lld\n",rt,f[rt],sz[rt],ch[rt][0],ch[rt][1],val[rt]); Traversal(ch[rt][1]); } void debug(){ printf("ROOT = %d <---\n",root); Traversal(root); } /**************************以下是前置操作**************************/ //以x为根的子树 的极值点 0 极小 1 极大 int extreme(int x,int k){ while(ch[x][k])x=ch[x][k];splay(x,0); return x; } //以x为根的子树 第k个数的位置 int kth(int x,int k){ if(sz[ch[x][0]]+1<=k&&k<=sz[ch[x][0]]+cnt[x]) return x; else if(ch[x][0]&&sz[ch[x][0]]>=k) return kth(ch[x][0],k); else return kth(ch[x][1],k-sz[ch[x][0]]-cnt[x]); } int search(int rt,LL x){ if(ch[rt][0]&&val[rt]>x) return search(ch[rt][0],x); else if(ch[rt][1]&&val[rt]<x)return search(ch[rt][1],x); else return rt; } /***************************以下是正经操作*************************/ //前驱 int prec(LL x){ int k=search(root,x); splay(k,0);//debug(); if(val[k]<x) return k; return extreme(ch[k][0],1); } //后继 int sufc(LL x){ int k=search(root,x); splay(k,0);//debug(); if(val[k]>x) return k; return extreme(ch[k][1],0); } int rk(LL x){ int k=search(root,x); splay(k,0); return sz[ch[root][0]]+1; } //按照二叉排序树性质插入x void _insert(LL x){ int p=prec(x),s=sufc(x); splay(p,0);splay(s,p); newnode(++tot,x,ch[root][1]); ch[ch[root][1]][0]=tot; for(int z=ch[root][1];z;z=f[z])pushup(z); splay(tot,0); } void _delete(LL x){ int p=prec(x),s=sufc(x); splay(p,0);splay(s,p); ch[ch[root][1]][0]=0; delnode(ch[ch[root][1]][0]); for(int yy=s;yy;yy=f[yy]) pushup(yy); } LL mystack[100],len; void dfs(int rt){ if(!rt) return ; dfs(ch[rt][0]); mystack[++len]=val[rt]; dfs(ch[rt][1]); } void solve(int x){ int y=kth(root,x-1); int z=kth(root,min(x+10,sz[root])); splay(y,0),splay(z,y); len=0; dfs(ch[ch[root][1]][0]); for(int i=1;i<len;i++) cout<<mmp2[mystack[i]]<<" "; cout<<mmp2[mystack[len]]<<endl; } int main(){ mmp.clear();mmp2.clear(); cin>>n; tot=0,root=1; newnode(++tot,-INF,0),newnode(++tot,INF,root); ch[root][1]=tot; for(int i=1,sc;i<=n;i++){//debug(); cin>>s; ss=""; for(int i=1;i<s.size();i++) ss+=s[i]; if(s[0]=='+'){ cin>>sc; if(mmp[ss]!=0) _delete(mmp[ss]); mmp[ss]=(LL)sc*-1000000+i; mmp2[mmp[ss]]=ss; _insert(mmp[ss]); } else { if('0'<=ss[0]&&ss[0]<='9'){ sc=0; for(int j=0;j<ss.size();j++) sc=(sc<<3)+(sc<<1)+ss[j]-'0'; solve(sc+1); } else{ cout<<rk(mmp[ss])-1<<endl; } } } return 0; }
