Skip to content

BZOJ - 1901. Dynamic Rankings

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

给定一个含有 nn 个数的序列 a1,a2ana_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,a2ana_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\% 的数据,1n,m1001 \le n,m \le 100
对于 40%40\% 的数据,1n,m10001 \le n,m \le 1000
对于 100%100\% 的数据,1n,m1041 \le n,m \le 10^41lrn1 \le l \le r \le n1krl+11 \le k \le r-l+11xn1\le x \le n0ai,y1090 \le a_i,y \le 10^9

#思路

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

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

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

#代码

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;
}