zcmimi's blog
查看原题

点击跳转

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
using namespace __gnu_pbds;
#define N 500005;
int n,val[N],cnt,tot;
map<string,int> mp;
string ss[N];
struct node{
    int v,id;
    bool operator < (const node &x) const {return v==x.v?id<x.id:v>x.v;}
};
tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> T;
il bool isdig(char x){return x>='0'&&x<='9';}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;char c;string s;int x,tp;
    while(n--){
        cin>>c>>s;
        if(c=='+'){
            if(mp[s]){
            tp=mp[s],T.erase(node{val[tp],tp});tot--;
        }
        mp[s]=++cnt,cin>>val[cnt],T.insert(node{val[cnt],cnt});tot++;
            ss[cnt]=s;
        }
        else if(c=='?'&&!isdig(s[0])){
            x=mp[s];cout<<T.order_of_key(node{val[x],x})+1<<endl;
        }
        else{
            x=0;
            For(i,0,s.size()-1) x=(x<<3)+(x<<1)+(s[i]^48);
            tp=min(tot,x+9);
            For(i,x-1,tp-1)cout<<ss[T.find_by_order(i)->id]<<' ';cout<<endl;
        }
    }
} 
LG 4291 [HAOI2008]排名系统
comment评论
Search
search