首页 题解

# Description

Luogu传送门

# Solution

挺板子的平衡树。

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#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.