Hướng dẫn giải của TKNP05: Đoạn chỉ số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Dãy đã sắp xếp. Với mỗi ~X~, in chỉ số đầu và chỉ số cuối (đánh số từ 1) của đoạn có các phần tử bằng ~X~, hoặc in ~0 0~ nếu ~X~ không có trong dãy.
Sub 1: Vét cạn — ~O(n \cdot Q)~, dùng khi ~n \cdot Q \le 10^7~
Mỗi truy vấn quét cả dãy, ghi vị trí đầu và vị trí cuối gặp được. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: lowerbound và upperbound — ~O(Q \log n)~
~lower_bound(X)~ cho vị trí đầu, ~upper_bound(X)~ cho vị trí sau cuối của đoạn bằng ~X~. Nếu hai vị trí trùng nhau thì không có ~X~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc dữ liệu. Nếu ~n \cdot Q \le 10^7~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, Q;
vector<long long> A;
vector<long long> qs;
// Sub 1: vet can. Moi truy van quet ca day, ghi lai vi tri dau va cuoi cua X. O(n*Q).
void sub1() {
for (long long x : qs) {
int L = 0, R = 0;
for (int i = 0; i < n; i++)
if (A[i] == x) {
if (L == 0) L = i + 1;
R = i + 1;
}
cout << L << " " << R << "\n";
}
}
// Sub 2: day sap xep, dung lower_bound va upper_bound. O(Q log n).
void sub2() {
for (long long x : qs) {
int lo = lower_bound(A.begin(), A.end(), x) - A.begin();
int hi = upper_bound(A.begin(), A.end(), x) - A.begin();
if (lo == hi) cout << "0 0\n";
else cout << lo + 1 << " " << hi << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> Q;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
qs.resize(Q);
for (int i = 0; i < Q; i++) cin >> qs[i];
if ((long long)n * Q <= 10000000) sub1();
else sub2();
return 0;
}
Bình luận