Atcoder Beginner Contest 306E
题目描述
長さ $ N $ の数列 $ A=(A_1,A_2,\dots,A_N) $ があり、最初全ての項が $ 0 $ です。
入力で与えられる整数 $ K $ を用いて関数 $ f(A) $ を以下のように定義します。
- $ A $ を降順に (広義単調減少となるように) ソートしたものを $ B $ とする。
- このとき、 $ f(A)=B_1\ +\ B_2\ +\ \dots\ +\ B_K $ とする。
この数列に合計 $ Q $ 回の更新を行うことを考えます。
数列 $ A $ に対し以下の更新を $ i=1,2,\dots,Q $ の順に行い、各更新ごとにその時点での $ f(A) $ の値を出力してください。
- $ A_{X_i} $ を $ Y_i $ に変更する。
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ K $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $
输出格式
全体で $ Q $ 行出力せよ。そのうち $ i $ 行目には $ i $ 回目の更新を終えた時点での $ f(A) $ の値を整数として出力せよ。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
7
8
9
10
11
| 4 2 10
1 5
2 1
3 3
4 2
2 10
1 0
4 0
3 1
2 0
3 0
|
输出 #1
1
2
3
4
5
6
7
8
9
10
| 5
6
8
8
15
13
13
11
1
0
|
说明/提示
制約
- 入力は全て整数
- $ 1\ \le\ K\ \le\ N\ \le\ 5\ \times\ 10^5 $
- $ 1\ \le\ Q\ \le\ 5\ \times\ 10^5 $
- $ 1\ \le\ X_i\ \le\ N $
- $ 0\ \le\ Y_i\ \le\ 10^9 $
Sample Explanation 1
この入力では $ N=4,K=2 $ です。 $ Q=10 $ 回の更新を行います。 - $ 1 $ 回目の更新を受けて $ A=(5,0,0,0) $ となります。このとき $ f(A)=5 $ です。 - $ 2 $ 回目の更新を受けて $ A=(5,1,0,0) $ となります。このとき $ f(A)=6 $ です。 - $ 3 $ 回目の更新を受けて $ A=(5,1,3,0) $ となります。このとき $ f(A)=8 $ です。 - $ 4 $ 回目の更新を受けて $ A=(5,1,3,2) $ となります。このとき $ f(A)=8 $ です。 - $ 5 $ 回目の更新を受けて $ A=(5,10,3,2) $ となります。このとき $ f(A)=15 $ です。 - $ 6 $ 回目の更新を受けて $ A=(0,10,3,2) $ となります。このとき $ f(A)=13 $ です。 - $ 7 $ 回目の更新を受けて $ A=(0,10,3,0) $ となります。このとき $ f(A)=13 $ です。 - $ 8 $ 回目の更新を受けて $ A=(0,10,1,0) $ となります。このとき $ f(A)=11 $ です。 - $ 9 $ 回目の更新を受けて $ A=(0,0,1,0) $ となります。このとき $ f(A)=1 $ です。 - $ 10 $ 回目の更新を受けて $ A=(0,0,0,0) $ となります。このとき $ f(A)=0 $ です。
算法
STL 模拟
吐槽
这题写的极为复杂，花费了大概2小时的时间调整细节，赛时绝对寄了
代码
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
| #include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n"
#define EPS 1e-8
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define all(v) v.begin(),v.end()
using namespace std;
using i64 = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<long long,long long>;
static constexpr int ALPHABET_SIZE = 26;
static constexpr i64 N = 1000000 + 5;
static constexpr int MOD = 998244353;
void solve() {
//有q个查询, 每次询问将数列中的axi -> yi(1 - based), 求前k个数的和
//一个set维护备选数组， 一个set维护已选数组(size <= k)
//每次操作先判断是否赋值, 然后然后判断是否大于已选set里最小的数
//同时维护sum
//额外维护state和nums, 代表每个索引的状态和数值, 0: 未赋值, 1: 在已选数组, 2: 在备选数组
//当一个索引已经赋值，则删掉对应数组里的元素，重新插入
int n, k, q;
cin >> n >> k >> q;
i64 sum = 0;
vector<int> states(n + 1);
vector<i64> nums(n + 1);
set<pl> chosen, candidate;
//每次都要更新state, nums
while (q--) {
i64 idx, newNum;
cin >> idx >> newNum;
if (chosen.size() < k) {
int state = states[idx];
if (state == 0) {
states[idx] = 1;
nums[idx] = newNum;
sum += newNum;
chosen.insert({newNum, idx});
} else {
//state只能为1
i64 oldNum = nums[idx];
nums[idx] = newNum;
sum -= oldNum;
sum += newNum;
chosen.erase({oldNum, idx});
chosen.insert({newNum, idx});
}
} else {
int state = states[idx];
if (state == 0) {
nums[idx] = newNum;
pl minChosen = *chosen.begin();
if (newNum > minChosen.first) {
states[idx] = 1;
states[minChosen.second] = 2;
sum -= minChosen.first;
sum += newNum;
//minChosen调整位置
chosen.erase(minChosen);
candidate.insert(minChosen);
chosen.insert({newNum, idx});
} else {
states[idx] = 2;
candidate.insert({newNum, idx});
}
}
else if (state == 1) {
//防止==k的情况出现re
i64 oldNum = nums[idx];
sum -= oldNum;
nums[idx] = newNum;
chosen.erase({oldNum, idx});
if (candidate.size()) {
pl maxCandidate = *candidate.rbegin();
if (newNum >= maxCandidate.first) {
sum += newNum;
chosen.insert({newNum, idx});
} else {
states[idx] = 2;
states[maxCandidate.second] = 1;
sum += maxCandidate.first;
candidate.erase(maxCandidate);
candidate.insert({newNum, idx});
chosen.insert(maxCandidate);
}
} else {
sum += newNum;
chosen.insert({newNum, idx});
}
}
else {
i64 oldNum = nums[idx];
nums[idx] = newNum;
candidate.erase({oldNum, idx});
pl minChosen = *chosen.begin();
if (newNum > minChosen.first) {
states[idx] = 1;
states[minChosen.second] = 2;
sum -= minChosen.first;
sum += newNum;
//minChosen调整位置
chosen.erase(minChosen);
candidate.insert(minChosen);
chosen.insert({newNum, idx});
} else {
candidate.insert({newNum, idx});
}
}
}
cout << sum << "\n";
}
}
int main()
{
IOS;
int t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
|
