C++14(g++5.4) 解法, 执行用时: 428ms, 内存消耗: 42132K, 提交时间: 2020-01-21 19:58:47

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

constexpr int MAXN = 30;
constexpr int MAX_LIST = 10;
char instruction[MAXN];

struct Node {
    int val{};
    int id{};
    string name;

    Node() = default;

    Node(int val, int id, string name) : val(val), id(id),
                                         name(std::move(name)) {}

    bool operator>(const Node &other) const {
        if (val == other.val) {
            return (id < other.id);
        }
        return (val > other.val);
    }
};

tree<Node, null_type, greater<>, rb_tree_tag,
        tree_order_statistics_node_update> Rbtree;
unordered_map<string, Node> Hashmap;

int main() {

    int n;
    int val;
    string temp_str;
    int rank;
    int counter;
    bool firstItem;
    scanf("%d", &n);
    for (int kase = 0; kase < n; ++kase) {
        scanf("%s", instruction);
        if (instruction[0] == '+') {
            // Example: +FRANK 12340000
            scanf("%d", &val);
            temp_str = "";
            for (int i = 1; instruction[i] != '\0'; ++i) {
                temp_str.push_back(instruction[i]);
            }

            if (Hashmap.find(temp_str) == Hashmap.end()) {
                Hashmap[temp_str].name = temp_str;
                Hashmap[temp_str].val = val;
                Hashmap[temp_str].id = kase;
                Rbtree.insert(Node(val, kase, temp_str));
            } else {
                Rbtree.erase(Node(Hashmap[temp_str].val, Hashmap[temp_str].id,
                                  temp_str));
                Hashmap[temp_str].val = val;
                Hashmap[temp_str].id = kase;
                Rbtree.insert(Node(val, kase, temp_str));
            }

        } else if (isdigit(instruction[1])) {
            // Example: ?2
            temp_str = "";
            for (int i = 1; instruction[i] != '\0'; ++i) {
                temp_str.push_back(instruction[i]);
            }
            rank = stoi(temp_str) - 1;
            firstItem = true;
            auto iter = Rbtree.find_by_order(rank);
            counter = 0;
            while (iter != Rbtree.end()) {
                if (counter == MAX_LIST) {
                    break;
                }
                if (firstItem) {
                    firstItem = false;
                } else {
                    printf(" ");
                }
                printf("%s", iter->name.c_str());
                ++counter;
                ++iter;
            }
            if (!firstItem) {
                printf("\n");
            }
        } else {
            // Example: ?KAINE
            temp_str = "";
            for (int i = 1; instruction[i] != '\0'; ++i) {
                temp_str.push_back(instruction[i]);
            }
            printf("%lu\n", Rbtree.order_of_key(
                    Node(Hashmap[temp_str].val, Hashmap[temp_str].id,
                         temp_str)) + 1);
        }
    }

    return 0;
}

C++ 解法, 执行用时: 467ms, 内存消耗: 46836K, 提交时间: 2022-04-16 23:06:23

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cctype>
#include<list>
#include<stack>
#define ri register int
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-10;
const int M=5e5+100;
int n,m,val[M],cnt,tot;
char c;
string s,ss[M];
map<string,int>mp;
struct Node
{
	int v,id;
	bool operator<(const Node&x) const
	{
		if(v==x.v) return id<x.id;
		return v>x.v;
	}
};
tree<Node,null_type,less<Node>,rb_tree_tag,tree_order_statistics_node_update>T;
inline int read(){
	int x=0,k=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') k=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*k;
}
inline void write(int x){
	if(x<0) x=~x+1,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
inline int GCD(int a,int b){return b?GCD(b,a%b):a;}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tem,x;
	cin>>n;
	while(n--)
	{
		cin>>c>>s;
		if(c=='+')
		{
			if(mp[s])
			{
				tem=mp[s];
				T.erase(Node{val[tem],tem});
				tot--;
			}
			mp[s]=++cnt;
			cin>>val[cnt];
			T.insert(Node{val[cnt],cnt});
			tot++;
			ss[cnt]=s;
		}
		else if(c=='?'&&!isdigit(s[0]))
		{
			x=mp[s];
			cout<<T.order_of_key(Node{val[x],x})+1<<endl;
		}
		else
		{
			x=0;
			for(int i=0;i<s.size();i++) x=x*10+s[i]-'0';
			tem=min(tot,x+9);
			for(int i=x-1;i<=tem-1;i++) cout<<ss[T.find_by_order(i)->id]<<' ';cout<<endl;
		}
	}
	return 0;
}