题解：ABC389F Rated Range

发表于 分类于 ， ， 本文字数： 560 阅读时长 ≈ 2 分钟
ABC389F Rated Range 的题解

分析

显然一个初始评分经过同样的操作后的结果是不变的, 试试离线. 维护一个数组, 其下标即为初始评分. 而每次比赛会使一部分评分处于 $[l,r]$ 的评分 $+1$, 观察到不管多少次修改后最终数组仍单调不减, 所以每次修改在初始评分序列上是连续的.

那么, 可以用线段树进行区间修改. 首先在线段树上二分, 找到值在 $[l,r]$ 区间对应的下标区间, 然后区间加一即可.

查询时, 直接单间查询对应初始评分修改后的评分即可.

参考代码

不理解的看代码应该能明白

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
#include <iostream>
using namespace std;
const int N = 5e5;
typedef long long ll;
ll mx[4 * N + 5], lz[4 * N + 5];
#define mid ((l + r) / 2)
#define lc (u * 2)
#define rc (u * 2 + 1)
void build(int u, int l, int r) {
    if (l == r) {
        mx[u] = l;
        return;
    }
    build(lc, l, mid);
    build(rc, mid + 1, r);
    mx[u] = max(mx[lc], mx[rc]);
}
void lazy(int u, int l, int r, int v) {
    lz[u] += v;
    mx[u] += v;
}
void pd(int u, int l, int r) {
    if (!lz[u]) return;
    lazy(lc, l, mid, lz[u]);
    lazy(rc, mid + 1, r, lz[u]);
    lz[u] = 0;
}
void update(int u, int l, int r, int xl, int xr, int v) {
    if (xl <= l && r <= xr) {
        lazy(u, l, r, v);
        return;
    }
    pd(u, l, r);
    if (xl <= mid) update(lc, l, mid, xl, xr, v);
    if (mid + 1 <= xr) update(rc, mid + 1, r, xl, xr, v);
    mx[u] = max(mx[lc], mx[rc]);
}
ll query(int u, int l, int r, int x) {
    if (l == r) {
        return mx[u];
    }
    pd(u, l, r);
    if (x <= mid)
        return query(lc, l, mid, x);
    else
        return query(rc, mid + 1, r, x);
}
int lower_search(int u, int l, int r, int x) {
    if (mx[u] < x) return -1;
    if (l == r) {
        return l;
    }
    pd(u, l, r);
    int res = lower_search(lc, l, mid, x);
    if (res != -1) return res;
    res = lower_search(rc, mid + 1, r, x);
    return res;
}
int upper_search(int u, int l, int r, int x) {
    if (mx[u] <= x) return -1;
    if (l == r) {
        return l;
    }
    pd(u, l, r);
    int res = upper_search(lc, l, mid, x);
    if (res != -1) return res;
    res = upper_search(rc, mid + 1, r, x);
    return res;
}
int main() {
    int n;
    cin >> n;
    build(1, 1, N);
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        int pl = lower_search(1, 1, N, l), pr = upper_search(1, 1, N, r);
        if (pl == -1) continue;
        if (pr == -1)
            pr = N;
        else
            pr -= 1;
        update(1, 1, N, pl, pr, 1);
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << query(1, 1, N, x) << endl;
    }
    return 0;
}