[HAOI2008]排名系统

第一行是一个整数n（n ≥ 10）表示请求总数目。
接下来n行,每行包含了一个请求。请求的具体格式如下：
+Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多8位的正整数。
?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。
?Index 返回自第Index名开始的最多10名玩家名字。
Index必定合法，即不小于1，也不大于当前有记录的玩家总数。

对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。

对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。

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的排名

C++14(g++5.4) 解法, 执行用时: 406ms, 内存消耗: 48476K, 提交时间: 2020-09-04 10:08:28

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

const int maxn=5e5+10;

struct node
{
    int val,id;
    bool operator < (const node &rhs) const{
        if(val!=rhs.val) return val>rhs.val;
        return id<rhs.id;
    }
};

tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> T;
map<string,int>id;
string name[maxn];
int val[maxn];
int cnt=0,tot=0;

int main()
{
    int n;
    cin>>n;
    while(n--){
        char ch;
        string s;
        cin>>ch>>s;
        if(ch=='+'){
            if(id[s]) T.erase((node){val[id[s]],id[s]}),tot--;
            cin>>val[++cnt],id[s]=cnt,name[cnt]=s;
            T.insert((node){val[cnt],cnt}),tot++;
        }
        else{
            if(s[0]>='0'&&s[0]<='9'){
                int x=0,len=s.size();
                for(int i=0;i<len;i++) x=x*10+s[i]-'0';
                    for(int i=x-1;i<min(tot,x+9);i++) cout<<name[T.find_by_order(i)->id]<<' ';
                cout<<endl;
            }
            else cout<<T.order_of_key((node){val[id[s]],id[s]})+1<<endl;
        }
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 399ms, 内存消耗: 46824K, 提交时间: 2021-01-01 13:06:02

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

const int maxn=5e5+10;

struct node
{
    int val,id;
    bool operator < (const node &rhs) const{
        if(val!=rhs.val) return val>rhs.val;
        return id<rhs.id;
    }
};

tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> T;
map<string,int>id;
string name[maxn];
int val[maxn];
int cnt=0,tot=0;

int main()
{
    int n;
    cin>>n;
    while(n--){
        char ch;
        string s;
        cin>>ch>>s;
        if(ch=='+'){
            if(id[s]) T.erase((node){val[id[s]],id[s]}),tot--;
            cin>>val[++cnt],id[s]=cnt,name[cnt]=s;
            T.insert((node){val[cnt],cnt}),tot++;
        }
        else{
            if(s[0]>='0'&&s[0]<='9'){
                int x=0,len=s.size();
                for(int i=0;i<len;i++) x=x*10+s[i]-'0';
                    for(int i=x-1;i<min(tot,x+9);i++) cout<<name[T.find_by_order(i)->id]<<' ';
                cout<<endl;
            }
            else cout<<T.order_of_key((node){val[id[s]],id[s]})+1<<endl;
        }
    }
    return 0;
}

详情