Editorial for conseq: Dãy con kỳ vọng

Hiểu bài toán

Cho một dãy số nguyên A có độ dài N. Nhiệm vụ là đếm số lượng dãy con liên tiếp từ chỉ số l đến r sao cho:

• Gọi k là giá trị nhỏ nhất trong dãy con đó.
• Các số nguyên liên tiếp k, k+1, k+2, ..., k+(r-l) đều xuất hiện đúng 1 lần trong dãy con. Nói cách khác, một dãy con thỏa mãn nếu nó chứa các số nguyên phân biệt và当我们 xếp các số này theo thứ tự tăng dần, chúng tạo thành một dãy liên tiếp không thiếu số nào. Đây chính là bài toán đếm số dãy con có các phần tử là một hoán vị của một đoạn số nguyên liên tiếp.

Các cách tiếp cận

Cách Brute Force

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    int res = 0;
    for(int l = 0; l < N; l++){
        int min_val = A[l], max_val = A[l];
        unordered_set<int> seen;
        for(int r = l; r < N; r++){
            if(seen.count(A[r])) break;
            seen.insert(A[r]);
            min_val = min(min_val, A[r]);
            max_val = max(max_val, A[r]);
            if(max_val - min_val == r - l) res++;
        }
    }

    cout << res << "\n";
}

• Time Complexity: O(N^2) trong trường hợp xấu nhất (vì có thể có dãy con dài), nhưng thực tế nhanh hơn nếu có số trùng lặp sớm.
• Space Complexity: O(N) cho bộ nhớ lưu trữ mảng và set (tối đa kích thước dãy con)

Đây là cách tiếp cận trực tiếp nhất. Ta duyệt qua tất cả các cặp (l, r) để kiểm tra dãy con từ l đến r. Với mỗi dãy con, ta cần kiểm tra:

1. Các phần tử có phân biệt không (dùng unordered_set).
2. Khoảng cách giữa giá trị lớn nhất và nhỏ nhất có bằng độ dài dãy con - 1 không (max - min == r - l). Nếu cả hai điều kiện trên đúng, thì dãy con đó thỏa mãn. Ta có thể tối ưu bằng cách dừng vòng lặp ngay khi gặp phần tử trùng lặp. Ví dụ với dãy [1, 3, 2]: min=1, max=3, r-l=2, max-min=2 => thỏa mãn.

Cách Optimized Brute Force with Early Stopping

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    int res = 0;
    for (int l = 0; l < n; ++l) {
        int mn = a[l], mx = a[l];
        unordered_set<int> seen;
        for (int r = l; r < n; ++r) {
            if (seen.count(a[r])) break;
            seen.insert(a[r]);
            mn = min(mn, a[r]);
            mx = max(mx, a[r]);
            if (mx - mn + 1 == r - l + 1)
                res++;
        }
    }
    cout << res;
    return 0;
}

• Time Complexity: O(N^2) trong trường hợp xấu nhất, nhưng thực tế nhanh hơn.
• Space Complexity: O(N)

Cách tiếp cận này tương tự Brute Force nhưng có một điểm khác biệt nhỏ trong công thức kiểm tra: mx - mn + 1 == r - l + 1. Đây là cách kiểm tra trực tiếp xem có bao nhiêu số nguyên từ mn đến mx (tức mx - mn + 1) có bằng số phần tử trong dãy con (tức r - l + 1) không. Điều này đảm bảo các số trong dãy con là một đoạn số nguyên liên tiếp không thiếu số nào. Ưu điểm của cách này là code rõ ràng về mặt ý nghĩa toán học.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Đặc điểm của một dãy con thỏa mãn: (1) Các phần tử phân biệt. (2) max - min = length - 1 (hoặc max - min + 1 = length).
• Khi duyệt qua dãy con từ l đến r, ta có thể duy trì min và max một cách hiệu quả trong O(1) mỗi bước.
• Việc kiểm tra điều kiện 'các số k, k+1,... xuất hiện đủ' tương đương với việc kiểm tra xem tập hợp các số có phải là một hoán vị của một đoạn số nguyên liên tiếp.

Lỗi thường gặp

• Quên kiểm tra điều kiện các phần tử phải phân biệt (distinct). Nếu chỉ kiểm tra max-min==r-l, ta có thể nhầm lẫn với các dãy có phần tử lặp nhưng vẫn thỏa mãn điều kiện về khoảng giá trị.
• Sử dụng sai công thức: ví dụ dùng max - min == r - l thay vì max - min + 1 == r - l + 1 (tương đương) có thể gây lỗi Off-by-one.
• Lỗi tràn số khi tính max - min nếu số rất lớn, nhưng trong bài này dữ liệu đầu vào thường nằm trong giới hạn của int.