[原创][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/
————————————————————————————————————————
题目描述 Description
[HAOI2008] 排名系统 & [ZJOI2006] GameZ游戏排名系统：

GameZ为他们最新推出的游戏开通了一个网站。世界各地的玩家都可以将自己的游戏得分上传到网站上。这样就可以看到自己在世界上的排名。得分越高，排名就越靠前。当两个玩家的名次相同时，先上传记录者优先。由于新游戏的火爆，网站服务器已经难堪重负。为此GameZ雇用了你来帮他们重新开发一套新的核心。 排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。

输入描述 Input Description
　　第一行是一个整数n（n>=10）表示请求总数目。
　　接下来n行每行包含了一个请求。请求的具体格式如下：
　　　　+Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为不超过无符号32位整型表示范围的非负整数。
　　　　?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。
　　　　?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。
　　输入数据大小不超过2M。
　　NOTE：用C++的fstream读大规模数据的效率较低。

输出描述 Output Description
　　对于每条查询请求，输出相应结果。对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。

样例输入 Sample 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

样例输出 Sample 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

数据范围及提示 Data Size & Hint
【样例解释】
20
+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
————————————————————————————————————————

首先这题考虑到玩家需要加分 ，那么就会产生一个新的排名，可以确定
这是一个SPLAY

因为排名是分数大的在前,所以是降序.我们可以在树上挂负值

那么考虑 怎么能在二叉排序树中找某个人的名字，？

这题光输入就很麻烦啊

名字 用一个map 映射成一个值就好了
考虑到先出现的在前 所以给这个值放大 然后+i就好了
然后在用这个值映射回名字即可,

一共两个map

其实还是很简单的 记录下分数 然后就找就行了

附本题代码
————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
# 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;
}