HAOI2008 排名系统

P4291 [HAOI2008] 排名系统

题目大意

有一个排名系统和$n$次操作，操作分为以下三种：

• +Name Score：上传一条新的得分记录
• ?Name：查询某个玩家的当前排名
• ?Index：返回某个区段内的排名记录

当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。

$10\le n\le 250000$

题解

前置知识：Splay平衡树

用平衡树维护分数，然后在平衡树上加点、删点、一个数的排名和排名为$k$的名字。可以用$map$将名字和分数一一对应。

不过，我们发现可能会有几个人的分数相同，我们考虑如何解决。我们发现人数不会超过$10^6+1$，那么我们可以将每个人的分数$w$变为$w?(10^6+1)+k$，其中$k$是一个随着操作次数的增加二减少的数，这就解决了分数相同的问题。

code

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
int T,s1,nt;
int rt,tot,cnt[N+5],siz[N+5],fa[N+5],ch[N+5][2];
long long mt[N+5];
char s[105];
string nm[N+5];
map<string,int>mp;
struct node{
	long long v;
	int wt;
	bool operator<(const node ax)const{
		return v<ax.v;
	}
	bool operator>(const node ax)const{
		return v>ax.v;
	}
	bool operator!=(const node ax)const{
		return v!=ax.v;
	}
}v[N+5];
int gt(int x){
	return ch[fa[x]][1]==x;
}
void pt(int x){
	siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
}
void rot(int x){
	int y=fa[x],z=fa[y],k=gt(x);
	ch[z][gt(y)]=x;fa[x]=z;
	ch[y][k]=ch[x][!k];fa[ch[y][k]]=y;
	ch[x][!k]=y;fa[y]=x;
	pt(y);pt(x);
}
void splay(int x,int g=0){
	for(int y;fa[x]!=g;rot(x)){
		y=fa[x];
		if(fa[y]!=g) rot((gt(y)==gt(x))?y:x);
	}
	if(!g) rt=x;
}
void find(long long x){
	if(!rt) return;
	int u=rt;
	while(ch[u][(node){x,0}>v[u]]&&(node){x,0}!=v[u]) u=ch[u][(node){x,0}>v[u]];
	splay(u);
}
void insert(long long x,int wt){
	int u=rt,fu=0;
	while(u&&v[u]!=(node){x,0}){
		fu=u;u=ch[u][(node){x,0}>v[u]];
	}
	u=++tot;
	if(fu) ch[fu][(node){x,0}>v[fu]]=u;
	fa[u]=fu;v[u]=(node){x,wt};
	siz[u]=1;
	splay(u);
}
int nxt(long long x,int f){
	find(x);
	int u=rt;
	if(v[u]>(node){x,0}&&f) return u;
	if(v[u]<(node){x,0}&&!f) return u;
	u=ch[u][f];
	while(ch[u][!f]) u=ch[u][!f];
	return u;
}
void dele(long long x){
	int lt=nxt(x,0),rt=nxt(x,1);
	splay(lt);splay(rt,lt);
	ch[rt][0]=0;
}
int kth(int k){
	int u=rt,sn=0;
	for(;;){
		sn=ch[u][0];
		if(k>siz[sn]+1) k-=siz[sn]+1,u=ch[u][1];
		else if(siz[sn]>=k) u=sn;
		else{
			splay(u);
			return v[u].wt;
		}
	}
}
int main()
{
	insert(1e18,0);
	insert(-1e18,0);
	scanf("%d",&T);
	while(T--){
		scanf("%s",s);
		s1=strlen(s);
		int tp=0;
		string t;
		long long w;
		if(s[0]=='+'){
			for(int i=1;i<s1;i++) t=t+s[i];
			scanf("%lld",&w);
			w=w*(N+1)+T;
			if(mp.count(t)){
				dele(mt[mp[t]]);
			}
			else{
				nm[++nt]=t;
				mp[t]=nt;
			}
			mt[mp[t]]=w;
			insert(w,mp[t]);
		}
		else if(s[1]<'0'||s[1]>'9'){
			for(int i=1;i<s1;i++) t=t+s[i];
			find(mt[mp[t]]);
			int tmp=siz[ch[rt][0]]+(v[rt]<(node){mt[mp[t]],0});
			printf("%d\n",nt-tmp+1);
		}
		else{
			for(int i=1;i<s1;i++) tp=tp*10+s[i]-'0';
			tp=nt-tp+1;
			for(int i=tp;i>=max(tp-10+1,1);i--){
				cout<<nm[kth(i+1)]<<" ";
			}
			printf("\n");
		}
	}
	return 0;
}