Skip to content

BZOJ - 1901. Dynamic Rankings

题解852 字
# 洛谷 # BZOJ # 二分 # 整体二分
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

给定一个含有 nn 个数的序列 a1,a2…ana_1, a_2 \dots a_n，需要支持两种操作：

  • Q l r k 表示查询下标在区间 [l,r][l, r] 中的第 kk 小的数
  • C x y 表示将 axa_x 改为 yy

#输入格式

第一行两个正整数 n,mn, m，表示序列长度与操作个数。

第二行 nn 个整数，表示 a1,a2…ana_1, a_2 \dots a_n。

接下来 mm 行，每行表示一个操作，都为上述两种中的一个。

#输出格式

对于每一次询问，输出一行一个整数表示答案。

#输入输出样例

样例输入 #1

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

样例输出 #1

3
6

#数据范围与约定

对于 20%20\% 的数据，1≤n,m≤1001 \le n,m \le 100；
对于 40%40\% 的数据，1≤n,m≤10001 \le n,m \le 1000；
对于 100%100\% 的数据，1≤n,m≤1041 \le n,m \le 10^4，1≤l≤r≤n1 \le l \le r \le n，1≤k≤r−l+11 \le k \le r-l+1，1≤x≤n1\le x \le n，0≤ai,y≤1090 \le a_i,y \le 10^9。

#思路

使用整体二分一次性二分出所有答案。

对于修改操作，将其拆为一个删除操作和一个新增操作即可。

二分询问的时候不要忘记在右区间减去左区间的排名。

#代码

C++
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
#include <iostream>
#include <cstring>
#include <tuple>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e4 + 5;

int n, m, a[N], c[N], ans[N];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int y) {
    for (; x <= n; x += lowbit(x)) c[x] += y;
}

inline int sum(int x) {
    int ret = 0;
    for (; x > 0; x -= lowbit(x)) ret += c[x];
    return ret;
}

void solve(int l, int r, const std::vector<std::tuple<char, int, int, int, int>>& q) {
    if (q.empty()) return;

    if (r - l == 1) {
        for (const auto& e : q) {
            if (std::get<0>(e) == 'Q') {
                ans[std::get<4>(e)] = l;
            }
        }

        return;
    }

    int mid = l + r >> 1;
    std::vector<std::tuple<char, int, int, int, int>> left, right;

    for (const auto& e : q) {
        char op;
        int x, y, z, id;

        std::tie(op, x, y, z, id) = e;

        if (op == 'Q') {
            int k = sum(y) - sum(x - 1);

            if (k >= z) {
                left.push_back(e);
            } else {
                right.emplace_back(op, x, y, z - k, id);
            }
        } else {  // op == 'C'
            if (y < mid) {
                add(x, z);
                left.push_back(e);
            } else {
                right.push_back(e);
            }
        }
    }

    for (const auto& e : left) {
        char op;
        int x, y, z, id;

        std::tie(op, x, y, z, id) = e;

        if (op == 'C') {
            add(x, -z);
        }
    }

    solve(l, mid, left);
    solve(mid, r, right);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(ans, 0xff, sizeof(ans));

    cin >> n >> m;

    std::vector<std::tuple<char, int, int, int, int>> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        q.emplace_back('C', i, a[i], 1, 0);
    }

    for (int i = 1; i <= m; i++) {
        char op;
        int x, y, z;

        cin >> op >> x >> y;

        if (op == 'Q') {
            cin >> z;

            q.emplace_back('Q', x, y, z, i);
        } else {  // op == 'C'
            q.emplace_back('C', x, a[x], -1, 0);
            a[x] = y;
            q.emplace_back('C', x, y, 1, 0);
        }
    }

    solve(0, 1e9, q);

    for (int i = 1; i <= m; i++) {
        if (~ans[i]) {
            cout << ans[i] << endl;
        }
    }

    return 0;
}