首页 题解

# Description

Luogu 传送门

# Solution

挺板子的平衡树。

题目要求我们支持三个操作：

  • 插入 / 更新 一个点的值。
  • 查询一个点的排名。
  • 查询从第 xx 名开始后面最多 10 名玩家的名字。

这些操作看着就很板子。。

唯一比较恶心的是要 hash\text{hash} 一下，所以开个 map\text{map} 存一下编号。

小技巧，存每个人的得分时存负数，这样 split\text{split} 时的边界要稍微好调一点。

传参数一定要写对啊，千万不要像我一样打错了调半天 QwQ

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1e6 + 10;
int n, root, tot;
int siz[N], val[N], ch[N][2], fa[N], wei[N];
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
inline void pushup(int x){
    if(ls(x)) fa[ls(x)] = x;
    if(rs(x)) fa[rs(x)] = x;
    siz[x] = siz[ls(x)] + siz[rs(x)] + 1;
}
inline void split_val(int x, int k, int &a, int &b){
    if(!x) return a = b = 0, void();
    if(val[x] <= k) a = x, split_val(rs(x), k, rs(x), b);
    else b = x, split_val(ls(x), k, a, ls(x));
    pushup(x);
}
inline void split_siz(int x, int k, int &a, int &b){
    if(!x) return a = b = 0, void();
    fa[x] = 0;
    if(siz[ls(x)] + 1 <= k) a = x, split_siz(rs(x), k - siz[ls(x)] - 1, rs(x), b);
    else b = x, split_siz(ls(x), k, a, ls(x));
    pushup(x);
}
inline int merge(int x, int y){
    if(!x || !y) return x | y;
    if(wei[x] < wei[y]){
        rs(x) = merge(rs(x), y);
        return pushup(x), x;
    }else{
        ls(y) = merge(x, ls(y));
        return pushup(y), y;
    }
}
inline int get_rk(int x){
    int res = siz[ls(x)] + 1;
    while(fa[x]){
        if(rs(fa[x]) == x) res += siz[ls(fa[x])] + 1;
        x = fa[x];
    }
    return res;
}
map <string, int> mp;
string s, name[N];
inline int newnode(int k){
    mp[s] = ++tot, siz[tot] = 1, wei[tot] = rand(), name[tot] = s, val[tot] = -k;
    return tot;
}
inline void update(int k){
    int a = 0, b = 0, c = 0;
    if(mp[s]){
        int rk = get_rk(mp[s]);
        split_siz(root, rk, a, b);
        split_siz(a, rk - 1, a, c);
        val[c] = -k;
        root = merge(a, b);
        split_val(root, -k, a, b);
        root = merge(merge(a, c), b);
    }else{
        split_val(root, -k, a, b);
        root = merge(merge(a, newnode(k)), b);
    }
}
inline int calc(string s){
    int res = 0, len = s.length();
    for(int i = 0; i < len; ++i) res = res * 10 + s[i] - '0';
    return res;
}
inline void print(int x){
    if(ls(x)) print(ls(x));
    cout << name[x] << " ";
    if(rs(x)) print(rs(x));
}
inline void query(){
    int a, b, c;
    if(isdigit(s[0])){
        int k = calc(s);
        split_siz(root, k + 9, a, b);
        split_siz(a, k - 1, a, c);
        print(c);
        root = merge(merge(a, c), b);
    }else write(get_rk(mp[s]));
}
signed main(){
    n = read();
    for(int i = 1; i <= n; ++i){
        char ch = getchar();
        while(ch != '+' && ch != '?') ch = getchar();
        cin >> s;
        if(ch == '+') update(read());
        else query(), puts("");
    }
    return 0;
}
// X.K.