Hiểu bài toán

Cho một dãy số $c$ gồm $n$ phần tử, mỗi phần tử có giá trị thuộc tập hợp ${1, 2, 3}$. Nhiệm vụ của bạn là đếm số lượng cặp chỉ số $(i, j)$ với $i < j$ sao cho:

1. $c[i]$ là số nhỏ nhất trong đoạn $[i, j]$.
2. $c[j]$ là số lớn nhất trong đoạn $[i, j]$. Nói cách khác, nếu $c[i] \le c[j]$ thì $c[i]$ phải là min và $c[j]$ phải là max của đoạn $[i, j]$. Ngược lại, nếu $c[i] > c[j]$ thì $c[j]$ phải là min và $c[i]$ phải là max của đoạn $[i, j]$. Giá trị $n$ có thể lên tới $2 \cdot 10^5$.

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

Cách Brute Force (Đối sánh trực tiếp)

void sub12() {
  rep(i, 2, n) {
    ll x = c[i], y = c[i];
    per(j, i - 1, 1) {
      x = min(x, c[j]);
      y = max(y, c[j]);
      if (min(c[i], c[j]) == x and max(c[i], c[j]) == y) ++ans;
    }
  }
  cout << ans;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là cách tiếp cận đơn giản nhất. Duyệt qua tất cả các cặp $(i, j)$ với $i < j$. Với mỗi cặp, ta duyệt lại toàn bộ đoạn $[i, j]$ để tìm giá trị nhỏ nhất (min) và lớn nhất (max). Sau đó ta kiểm tra xem $c[i]$ và $c[j]$ có phải là 2 giá trị này hay không.

• Tuy nhiên, giải thuật trong code lại duyệt $j$ từ $i-1$ trở về 1, và cập nhật min/max khi duyệt ngược. Nếu điều kiện thỏa mãn (min/max của đoạn $[j, i]$ là $c[i]$ và $c[j]$), ta tăng biến đếm.
• Cách này chỉ khả thi với $n$ nhỏ (khoảng 2000) do độ phức tạp $O(n^2)$.

Cách Prefix Count & Last Position Tracking

void sub3() {
    for (ll j = 1; j <= n; ++j) {
        p[c[j]] = j;
        for (ll x = 1; x <= 3; ++x) {
            ll Mn = min(c[j] , x), Mx = max(c[j] , x);
            ll pos = 1;
            for (ll i = 1; i <= Mn - 1; ++i) pos = max(pos, p[i] + 1);
            for (ll i = Mx + 1; i <= 3; ++i) pos = max(pos, p[i] + 1);
            ans += cnt[j - 1][x] - cnt[pos - 1][x];
        }
        cnt[j][1] = cnt[j - 1][1] + (c[j] == 1);
        cnt[j][2] = cnt[j - 1][2] + (c[j] == 2);
        cnt[j][3] = cnt[j - 1][3] + (c[j] == 3);
    }
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Giải thuật này tối ưu hóa bằng cách xử lý theo chiều duyệt $j$ (từ trái sang phải).

• Duyệt $j$ từ 1 đến $n$. Xét $c[j]$ là phần tử cuối.
• Để $(i, j)$ thỏa mãn, $i$ phải nhỏ hơn $j$. Phần tử $c[i]$ phải là min hoặc max của đoạn $[i, j]$.
• Ta cần xác định phạm vi hợp lệ của $i$. Cụ thể, không được có số nào nằm ngoài khoảng $[\min(c[i], c[j]), \max(c[i], c[j])]$ trong đoạn $[i, j]$.
• Duyệt qua tất cả các giá trị $x$ có thể là $c[i]$ (từ 1 đến 3).
• Xác định giới hạn dưới cho $i$: $i$ phải lớn hơn độ dài của mọi số nằm ngoài khoảng $[\min(x, c[j]), \max(x, c[j])]$. Ví dụ, nếu $x=1, c[j]=3$, thì đoạn $[i, j]$ không được chứa số 2. Do đó $i$ phải nhỏ hơn vị trí xuất hiện sau cùng của số 2.
• Sử dụng mảng cnt (mảng tiền tố) để đếm số lượng số $x$ trong đoạn $[pos, j-1]$ một cách nhanh chóng.
• Độ phức tạp: $O(n)$ vì với mỗi $j$, ta chỉ duyệt qua hằng số 3 giá trị $x$.

Cách Optimized Scan (Specialized for Values 1, 2, 3)

// Pseudocode based on combined logic
// Duyệt j từ 1 đến n
// Cập nhật vị trí cuối cùng (last_pos) cho các giá trị 1, 2, 3
// Với mỗi j, xét các trường hợp đặc biệt:
// 1. Cặp (1, 3): Tìm đoạn liên tiếp của các số 2 trước j, dùng mảng tiền tố để đếm số 1 trong đoạn đó.
// 2. Cặp (2, 3): Kiểm tra xem có số 1 nào nằm giữa không. Nếu không, tất cả các số 2 trước j đều hợp lệ.
// 3. Cặp (1, 2): Tương tự.
// 4. Các cặp bằng nhau: Đơn giản.

void solve() {
    // p[1], p[2], p[3] lưu vị trí cuối
    // cnt[i][v] lưu số lượng v từ 1 đến i
    // last_pos[v] lưu vị trí cuối của v
    for (int j = 1; j <= n; ++j) {
        int v = c[j];
        // Logic xử lý các trường hợp ở đây...
        // ...
        p[v] = j;
        // Cập nhật cnt
    }
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là biến thể của cách tiếp cận trên, có thể được viết lại để trực quan hơn dựa trên tính chất chỉ có 3 giá trị.

• Duyệt $j$ từ 1 đến $n$.
• Với mỗi $j$, ta đếm số lượng $i < j$ thỏa mãn.
• Phân tích theo giá trị của $c[j]$:
  • Nếu $c[j] = 3$: Ta có thể có cặp $(1, 3)$ hoặc $(2, 3)$ hoặc $(3, 3)$.
    • Với $(1, 3)$: $i$ phải là số 1, và đoạn $(i, j)$ chỉ được chứa số 2 (và số 1, 3). Điều này có nghĩa là $i$ phải nằm sau vị trí cuối cùng của các số nằm ngoài ${1, 2, 3}$ (trong dãy này là rỗng) nhưng thực tế là $i$ phải nằm trong đoạn mà ở đó không có số 3 nào khác ở giữa? Không, điều kiện là min/max là $c[i]$ và $c[j]$. Nếu $c[i]=1, c[j]=3$, đoạn $(i, j)$ không được có số nào > 3 hoặc < 1, và không được có số nào nằm ngoài $[1, 3]$. Thực tế, đoạn không được có số 3 nào khác (vì $c[j]$ là max duy nhất) và không được có số nào < 1. Đơn giản hơn: $i$ phải là số 1, và mọi số trong $(i, j)$ phải nằm trong $[1, 3]$. Vì chỉ có 1, 2, 3, nên chỉ cần đảm bảo không có số 3 nào ở giữa (trừ $c[j]$). Nếu có số 3 ở giữa, $c[j]$ không phải là max duy nhất? Không, max vẫn là 3, nhưng $c[i]$ có thể không còn là min nếu có số 1 ở giữa? $c[i]$ là min nếu nó là số 1 duy nhất? Không, $c[i]$ chỉ cần là min của đoạn $[i, j]$. Nếu có số 1 ở giữa, $c[i]$ vẫn là min.
    • Thực tế, điều kiện "$c[i]$ là min và $c[j]$ là max" của đoạn $[i, j]$ có nghĩa là:
      • Nếu $c[i] < c[j]$: $c[i]$ phải nhỏ hơn mọi phần tử trong $(i, j)$ và $c[j]$ phải lớn hơn mọi phần tử trong $(i, j)$.

• Phân tích chi tiết:
  • $c[j] = 3$:
    • $c[i] = 1$: Cần $1 < \text{phần tử trong } (i, j) < 3$. Nghĩa là đoạn $(i, j)$ chỉ được chứa số 2. Ta có thể dùng mảng cnt để đếm số 1 trong đoạn $[\text{vị trí sau số 3 trước đó}, j-1]$.
    • $c[i] = 2$: Cần $2 < \text{phần tử trong } (i, j) < 3$. Nghĩa là đoạn $(i, j)$ không được có số 1. Ta đếm số 2 trong đoạn $[\text{vị trí sau số 1 trước đó}, j-1]$.
    • $c[i] = 3$: Cần đoạn $(i, j)$ trống hoặc chỉ chứa 3. Đếm số 3.

Cách này hiệu quả và tránh được các vòng lặp lồng nhau lớn.

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

Bài học kinh nghiệm

• Bài toán chỉ涉及 3 giá trị (1, 2, 3), cho phép tối ưu hóa các cấu trúc dữ liệu (mảng thay vì map/BIT).
• Điều kiện 'min/max' tương đương với việc tất cả các phần tử trong đoạn $(i, j)$ phải nằm trong khoảng $[\min(c[i], c[j]), \max(c[i], c[j])]$. Với dãy chỉ có 1, 2, 3, điều này loại trừ các giá trị nằm ngoài.
• Sử dụng mảng tiền tố (prefix array) để tính số lượng phần tử $x$ trong một đoạn bất kỳ trong $O(1)$.

Lỗi thường gặp

• Quên kiểm tra điều kiện $i < j$.
• Xử lý sai trường hợp $c[i] = c[j]$ (cần đảm bảo đoạn $(i, j)$ chỉ chứa giá trị đó).
• Lỗi truy cập mảng khi xử lý các giới hạn (ví dụ: pos-1 khi pos là 1).