题目描述
GameZ 为他们最新推出的游戏开通了一个网站。
世界各地的玩家都可以将自己的游戏得分上传到网站上。
这样就可以看到自己在世界上的排名。
得分越高，排名就越靠前。
当两个玩家的名次相同时，先上传记录者优先。
由于新游戏的火爆，网站服务器已经难堪重负。
为此 GameZ 雇用了你来帮他们重新开发一套新的核心。
排名系统通常要应付三种请求：
上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。
当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。
为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回 10 条记录。
输入样例
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
输出样例
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
代码
`
/*
就在这里说好了。
我们就不说splay的原理和基操了(因为我也可能说不清楚...)。然后我们直接看这道题，就是比模板题多了个
名字和从某一位开始输出名字。
分开解答：
1.上传操作-------这里有必要记录节点对应的名字和名字对应的节点,如果之前上传了那么就得删除记录(即del函数)
题目中还要求先上传记录者优先，直接判断就可以了，如果等于的话,那就插入子树的右边不就完了？（滑稽）
2.询问操作-------和模板一样,具体看代码
*/
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
/*
1.用map存名字对应的节点,节点对应的名字
2.上传得分时,先删除记录
3.查询排名时,找到名字对应的节点,旋到根节点,输出siz
4.先找到index名,然后可以循环依次find
*/
#include<bits/stdc++.h>
#define R register
#define ll long long
#define inf INT_MAX
#define lc(x) (s[x].ch[0])
#define rc(x) (s[x].ch[1])
using namespace std;
const int N=3e5+10;
int n,tot,rt;
map<string,int>p;//名字对应的节点
map<int,string>kp;//节点对应的名字
struct nkl
{
int ch[2],val,siz,fa;
}s[N];
inline int ident(int x,int y)
{
return (rc(y)==x);
}
inline void cn(int x,int y,int k)
{
s[x].fa=y;
s[y].ch[k]=x;
}
inline void upd(int x)
{
s[x].siz=s[lc(x)].siz+s[rc(x)].siz+1;
}
inline void rotate(int x)
{
int y=s[x].fa,z=s[y].fa,k=ident(x,y);
cn(s[x].ch[k^1],y,k);
cn(x,z,ident(y,z));
cn(y,x,k^1);
upd(y),upd(x);
}
inline void splay(int x,int to)
{
if(!to) rt=x;
while(s[x].fa!=to)
{
int y=s[x].fa,z=s[y].fa;
if(z!=to)
ident(x,y)^ident(y,z) ? rotate(x):rotate(y);
rotate(x);
}
}
inline void newcode(int &now,int va,int fa)
{
now=tot;
s[tot].val=va;
s[tot].fa=fa;
s[tot].siz=1;
lc(tot)=rc(tot)=0;
}
inline void insert(int &now,int va,int fa)
{
if(!now) newcode(now,va,fa),splay(now,0);
else
{
if(s[now].val<=va) insert(rc(now),va,now);
else insert(lc(now),va,now);
}
}
inline void del(int x)
{
splay(x,0);
if(s[x].ch[1])
{
int u=rc(x);
while(lc(u)) u=lc(u);
splay(u,x);
cn(s[x].ch[0],u,0);
rt=u;s[u].fa=0;
upd(rt);
}
else rt=s[x].ch[0],s[rt].fa=0;
}
inline int find(int tk)
{
int u=rt;
while(u)
{
int lk=s[lc(u)].siz+1;
if(tk==lk)
{
splay(u,0);
break;
}
else if(tk<lk) u=lc(u);
else tk-=lk,u=rc(u);
}
return u;
}
int main()
{
char ins;string t;int x;
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>ins>>t;
if(ins=='+')
{
cin>>x;
if(p[t]) del(p[t]);
p[t]=++tot;kp[tot]=t;
//分数,
insert(rt,-x,0);
//这里的-x是为了使树保持小的在左,大的在右,实际上节点左边的全是排名比他高的
}
else
{
if(t[0]>='0'&&t[0]<='9')
{
int rk=0,tk=0;
while(t[rk]>='0'&&t[rk]<='9')
tk=10*tk+(t[rk]-'0'),rk++;
int j=tk,sum=0;
cout<<kp[find(j)];j++,sum++;
while(j<=s[rt].siz)
{
cout<<" "<<kp[find(j)];
j++,sum++;
if(sum==10) break;
}puts("");
//想模板一样挨个输出就行了
}
else
{
splay(p[t],0);
//因为我们知道名字对应的节点,直接旋到根节点,他左边的全是排名比他高的
cout<<s[lc(rt)].siz+1<<"\n";
}
}
}
return 0;
//愉快
}
`
