Luogu

BZOJ

分析

双份的快乐

代码

//It is made by M_sea
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define re register
using namespace std;
using namespace __gnu_pbds;

const int N=500000+10;

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

tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> T;
//BZOJ上请将null_type改为null_mapped_type

map<string,int> id;
string name[N];
int val[N];
int cnt=0,tot=0;

int main() {
    ios::sync_with_stdio(false);
    int n; cin>>n;
    while (n--) {
        char op; string s; cin>>op>>s;
        if (op=='+') {
            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 (op=='?') {
            if (s[0]>='0'&&s[0]<='9') {
                int x=0,l=s.length();
                for (re int i=0;i<l;++i) x=x*10+s[i]-'0';
                for (re 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;
}