Hướng dẫn giải của Thi thử HSG9 2026 - Ngày 2 - Dãy số đẹp
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.
Tác giả:
Nhận xét: Nếu đoạn ~[l, r]~ thỏa mãn đề bài, thì đoạn ~[l - 1, r]~ cũng thỏa mãn đề bài.
Vì vậy, với mỗi ~r~, thì ta cần tìm ~l~ nhỏ nhất để đoạn ~[l, r]~ thỏa mãn đề bài. Ta sử dụng hai con trỏ, và nhiệm vụ của ta là duy trì hai con trỏ này.
Subtask 4. ~n, q \le 3636~
Ta có thể kiểm tra một đoạn có thỏa mãn không bằng cách sắp xếp lại sau đó kiểm tra.
Độ phức tạp: ~O~ (~n^2 \times log~ ~n~).
Subtask 5. Mảng gồm tối đa ~6~ giá trị phân biệt
Ta có thể kiểm tra một đoạn có thỏa mãn không, bằng cách xem đoạn có có các giá trị nào, sau đó sắp xếp lại chỉ ~6~ giá trị đó và kiểm tra.
Độ phức tạp: ~O~ (~n \times 6~).
Subtask 6. Không có ràng buộc gì thêm
Ta duy trì một std::multiset thể hiện các số ta đang có.
Khi thêm một số ~x~ vào, để kiểm tra dãy có thỏa mãn không, ta chỉ cần kiểm tra số lớn nhất nhỏ hơn ~x~, và số nhỏ nhất lớn hơn ~x~.
Độ phức tạp: ~O~ (~n \times log~ ~n~).
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"
const int N = 1e6 + 9;
const int inf = 2e18;
int n, q;
int a[N];
int minReq[N];
set <int> s;
map <int, int> cnt;
signed main (){
ios_base::sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
s.insert (a[1]);
cnt[a[1]]++;
int L = 1;
for (int R = 2; R <= n; R++){
while (1){
if (cnt[a[R]]) break;
set <int> :: iterator it = s.upper_bound (a[R]);
bool valid = 1;
if (it != s.end ()){
if ((*it) % a[R] != 0) valid = 0;
}
if (it != s.begin ()){
set <int> :: iterator preit = prev (it);
if (a[R] % (*preit) != 0) valid = 0;
}
if (valid) break;
cnt[a[L]]--;
if (cnt[a[L]] == 0) s.erase (s.find (a[L]));
L++;
}
minReq[R] = L;
cnt[a[R]]++;
if (cnt[a[R]] == 1) s.insert (a[R]);
}
int res = 0;
minReq[1] = 1;
for (int i = 1; i <= n; i++){
res += i - minReq[i] + 1;
}
cout << res << '\n';
}
// <33
Bình luận