自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 21:39:20，当前版本为作者最后更新于2018-09-28 15:09:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

HAOI2008也考了这题，一模一样！。

Solution：

本题纯pbds模拟平衡树+hash。

这种动态加点、改值、查询排名和k大值的问题，直接想到平衡树。

题目中需要用到的信息有：字符串、得分、时刻，其中时刻就是该字符串得到当前分数是第几次操作，维护时刻是因为对于得分相同的字符串，时刻小的要排在前面。

我们用一棵Splay来维护pbds中的rb_tree来维护。

对于每个字符串，把其和插入的时刻进行map映射，然后每个节点以分数为第一关键字、时刻为第二关键字，构建平衡树。对于每种操作：1、插入节点，直接可以insert ; 2、改变节点分数和时刻，我们直接改为删除这个节点，并加入新的值的节点 ; 3、查询排名，我们有order_of_key ; 4、查询第k大值，我们有find_by_order。

只需要模拟就好了，减少了很多冗余的码农操作（pbds大法好！）

$\quad\;\;$欢迎来踩博客：five20（蒟蒻写题解不易，转载请注明出处，万分感谢！～）

代码：

    /*Code by 520 -- 9.21*/
    #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;
    const int 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;
            }
        }
        return 0;
    }