Official
B - First Query Problem Editorial by MMNMM
この問題のようなクエリ形式の問題は、「クエリを受け取りながら、クエリの操作を効率よくシミュレーションする」ことや、「クエリをまとめて受け取ることで、操作を全部行うことなく答えを効率よく求める」ことで解くことが多いです。
この問題は、配列を用いることで、(クエリの操作をその場でシミュレーションしながら)解くことができます。
具体的には、C++ では生配列や std::vector
などを用いることで、python ではリストを用いることで、この問題を解くことができます。
実装例は以下のようになります。 実装に際しては、クエリの形式ごとに入力すべき値の個数が異なることなどに注意してください。
C++ (生配列)
#include <iostream>
using namespace std;
int A[100000];
int main() {
int N;
cin >> N;
// A の入力
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
int Q;
cin >> Q;
// クエリの入力
for (int i = 0; i < Q; ++i) {
int type;
cin >> type;
if (type == 1) {
// 1 番目の形式なら、A を更新
int k, x;
cin >> k >> x;
A[k - 1] = x;
} else {
// 2 番目の形式なら、A を出力
int k;
cin >> k;
cout << A[k - 1] << endl;
}
}
return 0;
}
C++ (std::vector
)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
// A の入力
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
int Q;
cin >> Q;
// クエリの入力
for (int i = 0; i < Q; ++i) {
int type;
cin >> type;
if (type == 1) {
// 1 番目の形式なら、A を更新
int k, x;
cin >> k >> x;
A[k - 1] = x;
} else {
// 2 番目の形式なら、A を出力
int k;
cin >> k;
cout << A[k - 1] << endl;
}
}
return 0;
}
python
N = int(input())
# A の入力
A = list(map(int, input().split()))
Q = int(input())
# クエリの入力
for i in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
# 1 番目の形式なら、A を更新
type, k, x = query
A[k - 1] = x
else:
# 2 番目の形式なら、A を出力
type, k = query
print(A[k - 1])
posted:
last update: