【bzoj1056&1862】[HAOI2008]排名系统

2015.05.28 11:56 Thu | 22次阅读 | 旧日oi | 固定链接 | 源码

Description

排名系统通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回10条记录。
题解
round1还没结束,但我已经弃疗……
裸的平衡树,但是还真不太好写……前前后后写了3遍,每次写着写着发现搞不了就放弃了。对于删除操作,必须多维护一个时间值……话说这题为啥不是spj啊……。。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define N 250005
using namespace std;
map<string,int> mp;
map<int,string> _mp;
int n,cnt,root,tot;
char s[15];
int score[N],tim[N];
struct Treap{
    int l[N],r[N],rnd[N],name[N],val[N],siz[N],tim[N];
    void update(int x)
    {
        siz[x]=siz[l[x]]+siz[r[x]]+1;
    }
    void lturn(int &k)
    {
        int t=r[k];r[k]=l[t];l[t]=k;
        siz[t]=siz[k];update(k);k=t;
    }
    void rturn(int &k)
    {
        int t=l[k];l[k]=r[t];r[t]=k;
        siz[t]=siz[k];update(k);k=t;
    }
    void insert(int &rt,int v,int t,int nam)
    {
        if(!rt)
        {
            rt=++tot;
            val[rt]=v;
            siz[rt]=1;
            rnd[rt]=rand();
            name[rt]=nam;
            tim[rt]=t;
            return;
        }
        siz[rt]++;
        if(val[rt]<v)
        {
            insert(r[rt],v,t,nam);
            if(rnd[r[rt]]<rnd[rt]) lturn(rt);
        }
        else
        {
            insert(l[rt],v,t,nam);
            if(rnd[l[rt]]<rnd[rt]) rturn(rt);
        }
    }
    void del(int &rt,int v,int t)
    {
        if(val[rt]==v)
        {
            if(tim[rt]==t)
            {
                if(l[rt]*r[rt]==0) rt=l[rt]+r[rt];
                else
                {
                    if(rnd[l[rt]]<rnd[r[rt]]) rturn(rt),del(rt,v,t);
                    else lturn(rt),del(rt,v,t);
                }
            }
            else if(tim[rt]<t) siz[rt]--,del(l[rt],v,t);
            else siz[rt]--,del(r[rt],v,t);
        }
        else if(val[rt]<v) siz[rt]--,del(r[rt],v,t);
        else siz[rt]--,del(l[rt],v,t);
    }
    int get_rank(int k,int x,int time)
    {
        if(k==0)return 0;
        if(val[k]==x)
        {
            if(tim[k]>time) return get_rank(r[k],x,time);
            else if(tim[k]<time)return 1+siz[r[k]]+get_rank(l[k],x,time);
            else return siz[r[k]]+1;
        }
        else if(val[k]<x)return get_rank(r[k],x,time);
        else return 1+siz[r[k]]+get_rank(l[k],x,time);
    }
    void get_name(int k)
    {
        int x=root;
        while(x)
        {
            if(siz[r[x]]+1==k) 
            {
                cout<<_mp[name[x]];
                return;
            }
            else if(siz[r[x]]>=k) x=r[x];
            else k-=siz[r[x]]+1,x=l[x];
        }
    }
}trp;
int main()
{
    cin>>n;
    for(int x,i=1;i<=n;i++)
    {
        scanf("%s",s);
        if(s[0]=='+')
        {
            scanf("%d",&x);
            if(!mp[s+1]) mp[s+1]=++cnt,_mp[cnt]=s+1;
            int tmp=mp[s+1];
            if(score[tmp]) trp.del(root,score[tmp],tim[tmp]);
            tim[tmp]=i;score[tmp]=x;
            trp.insert(root,score[tmp],tim[tmp],tmp);
        }
        else
        {
            if(isalpha(s[1])) printf("%d\n",trp.get_rank(root,score[mp[s+1]],tim[mp[s+1]]));
            else
            {
                int ret=0;
                for(int i=1;i<strlen(s);i++) ret=ret*10+s[i]-'0';
                for(int i=ret;i<=ret+9&&i<=cnt;i++)
                {
                    trp.get_name(i);
                    if(i<ret+9&&i<cnt) printf(" ");
                }
                puts("");
            }
        }
    }
    return 0;
}```