[文章目录]
Decription
排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。N<=250000
splay+hash表。
指针版splay写的越来越顺手了，估计改不了了吧，get了hash表新技能。写一个bool的check，然后计数器为字符串id，hash值为head下标，然后直接扫，check匹配，遇到新的string就hash挂链，链式前向星直接上。
另外check的时候传参(char st1[],char st2[])||(char *st1,*st2)实测快慢没差多少。
另外字符串复制，用到库里的memcpy()函数。用法为(char st1[],char st2[],int y)，表示将st2指针位置开始的y个字符复制到st1开始的y个位置上。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,tot,num=2;
//=======================================================hash
char nam[251000][11],st[15];
int head[1001000],to_id[251000],nxt[251000],cnt;
bool check(char *st1,char *st2)
{
int l1=strlen(st1),l2=strlen(st2);
if(l1!=l2) return false;
for(int i=0;i<l1;i++) if(st1[i]!=st2[i]) return false;
return true;
}
int hash_id(char *str)
{
int len=strlen(str),re=0;
for(int i=1;i<len;i++) re=(re*97+str[i])%1000003;
return re;
}
void add(int x,int y) {to_id[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}
//=======================================================splay
struct node
{
node *fa,*c[2];
int w,siz,id;
node(int x,int y);
void pushup(){siz=c[0]->siz+c[1]->siz+1;}
}*null=new node(0,0),*root,*a[251000];
node :: node(int x,int y) {fa=c[1]=c[0]=null; siz=null?1:0; w=x; id=y;}
void initialize()
{
root=new node(0x80000000,0);
root->c[1]=new node(0x7fffffff,0);
root->c[1]->fa=root;
root->pushup();
}
void rotate(node *x)
{
node *y=x->fa; bool l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(y==y->fa->c[0]) y->fa->c[0]=x;
else y->fa->c[1]=x;
y->fa=x; y->pushup(); x->pushup();
if(y==root) root=x;
}
void splay(node *x,node *tar)
{
while(x->fa!=tar)
{
node *y=x->fa,*z=y->fa;
if(z==tar){rotate(x); break;}
if((x==y->c[0])^(y==z->c[0])==0) rotate(y);
else rotate(x); rotate(x);
}
}
void insert(node *x)
{
node *l,*r,*p=root; int sw=x->w;
while(p!=null)
{
if(p->w<sw) l=p,p=p->c[1];
else r=p,p=p->c[0];
}
splay(l,null); splay(r,root);
root->c[1]->c[0]=x; x->fa=root->c[1];
root->c[1]->pushup(); root->pushup();
}
int z[20],top;
void output(node *x)
{
if(x==null) return;
output(x->c[1]);
z[++top]=x->id;
output(x->c[0]);
}
void find(node *x,int y,node *z)
{
while(1)
{
int tmp=x->c[0]->siz;
if(y<=tmp) x=x->c[0];
else
{
y-=(tmp+1);
if(!y) break;
x=x->c[1];
}
}
splay(x,z);
}
void del(node *x)
{
node *l=x,*r=x;
if(l->c[0]!=null) {l=l->c[0]; while(l->c[1]!=null) l=l->c[1];}
else {while(l==l->fa->c[0]) l=l->fa; l=l->fa;}
if(r->c[1]!=null) {r=r->c[1]; while(r->c[0]!=null) r=r->c[0];}
else {while(r==r->fa->c[1]) r=r->fa; r=r->fa;}
splay(l,null); splay(r,root);
root->c[1]->c[0]=null;
root->c[1]->pushup();
root->pushup();
free(x);
}
//=======================================================end
void Insert()
{
int id=hash_id(st+1),x,y=-1; scanf("%d",&x);
for(int i=head[id];i;i=nxt[i])
if(check(nam[to_id[i]],st+1))
{y=to_id[i];break;}
if(y==-1)
{
++tot; add(id,tot); memcpy(nam[tot],st+1,strlen(st+1));
a[tot]=new node(x,tot);
insert(a[tot]); num++;
}
else
{
del(a[y]);
a[y]=new node(x,y);
insert(a[y]);
}
}
void Index()
{
int len=strlen(st+1),x=0;
for(int i=1;i<=len;i++)
x=(x<<1)+(x<<3)+st[i]-'0';
find(root,max(num-x-10,1),null);
find(root,num-x+1,root);
top=0; output(root->c[1]->c[0]);
for(int i=1;i<=top;i++)
printf("%s%c",nam[z[i]],(i==top)?'\n':' ');
}
void Q_name()
{
int id=hash_id(st+1),x,tmp=0;
for(int i=head[id];i;i=nxt[i])
if(check(nam[to_id[i]],st+1))
{x=to_id[i]; break;}
node *p=a[x];
if(p->c[1]!=null) tmp+=p->c[1]->siz;
while(p!=root)
{
if(p==p->fa->c[0]) tmp+=p->fa->c[1]->siz+1;
p=p->fa;
}
printf("%d\n",tmp);
}
int main()
{
initialize();
scanf("%d",&n);
while(n--)
{
scanf("%s",st);
if(st[0]=='+') Insert();
else if(st[1]<'A'||st[1]>'Z') Index();
else Q_name();
}
return 0;
}