Hiểu bài toán

Cho một dãy số $A$ gồm $N$ phần tử. Gọi $T$ là tổng số cặp chỉ số $(i, j)$ với $i < j$ sao cho $A[i] = A[j]$ (tức là số lượng cặp phần tử bằng nhau trong toàn dãy). Với mỗi $k$ từ $1$ đến $N$, hãy tính số lượng cặp phần tử bằng nhau trong dãy khi ta loại bỏ phần tử $A[k]$ (chỉ loại bỏ 1 phần tử tại vị trí $k$, không thay đổi thứ tự các phần tử còn lại). In ra kết quả cho mỗi $k$.

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

Cách Hash Map Tính Toàn Cục

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("LONGK.inp", "r", stdin);
    freopen("LONGK.out", "w", stdout);

    int N;
    cin >> N;
    vector<long long> a(N + 1);
    unordered_map<long long, long long> freq;

    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        freq[a[i]]++;
    }

    // Tính tổng số cặp toàn cục
    long long total = 0;
    for (auto &p : freq) {
        long long f = p.second;
        total += f * (f - 1) / 2;
    }

    // Với mỗi k, số cặp còn lại là total - (số cặp bị mất)
    // Số cặp bị mất khi loại bỏ a[k] là số lần xuất hiện của a[k] trừ đi 1
    for (int k = 1; k <= N; k++) {
        long long f = freq[a[k]];
        cout << total - (f - 1) << "\n";
    }

    return 0;
}

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

Phương pháp này dựa trên quan sát toán học.

1. Xác định tần suất xuất hiện của mỗi giá trị trong toàn bộ dãy bằng unordered_map.
2. Tính tổng số cặp phần tử bằng nhau ($T$) của toàn dãy bằng công thức $T = \sum \frac{fi(fi-1)}{2}$ với $f_i$ là tần suất của giá trị thứ $i$.
3. Khi loại bỏ phần tử $A[k]$:
   • Nếu $A[k]$ xuất hiện $f$ lần, số cặp bị mất là $f - 1$ (tức là phần tử $A[k]$ này đã tham gia vào bao nhiêu cặp với các phần tử cùng giá trị khác).
   • Do đó, số cặp còn lại là $T - (f - 1)$. Cách này rất nhanh và chỉ cần duyệt qua mảng 2 lần.

Cách Hash Map Từng Bước (Sliding Map)

#include <bits/stdc++.h>

using namespace std;
int C(int n){
    return (n*(n-1))/2;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("LONGK.inp","r",stdin);
    freopen("LONGK.out","w",stdout);
    int n;
    cin>>n;
    vector<int> arr(n);
    for (int i=0;i<n;i++){
        cin>>arr[i];
    }
    map<int,int> mp;

    // Đếm tần suất toàn cục
    for (int i=0;i<n;i++){
        mp[arr[i]]++;
    }
    int res=0;
    // Tính tổng số cặp ban đầu
    for (auto x:mp){
        if (x.second>=2){
            res+=C(x.second);
        }
    }

    for (int i=0;i<n;i++){
        // Logic cập nhật tần suất động để tính số cặp
        if (mp[arr[i]]>=2){
            res-=C(mp[arr[i]]);
        }
        mp[arr[i]]--; // Giảm tần suất hiện tại (tương tự loại bỏ phần tử i)
        if(mp[arr[i]]>=2){
            res+=C(mp[arr[i]]);
        }

        // Logic này là sai so với yêu cầu đề bài (tính giá trị khi loại bỏ i)
        // Đoạn code này đang mô phỏng sliding window sang phải, in ra res của window hiện tại
        // Tuy nhiên, đề bài yêu cầu in giá trị khi loại bỏ phần tử tại chỉ số đó
        if (i>0){
            if (mp[arr[i-1]]>=2){
                res-=C(mp[arr[i-1]]);
            }
            mp[arr[i-1]]++; // Tăng lại phần tử trước đó
            if (mp[arr[i-1]]>=2){
                res+=C(mp[arr[i-1]]);
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Code này sử dụng map (Cây đỏ-đen) và cố gắng cập nhật t tổng số cặp một cách động. Tuy nhiên, logic trong vòng lặp for (int i=0;i<n;i++) của giải pháp này có vẻ không hoàn toàn khớp với yêu cầu "tính giá trị khi loại bỏ A[i]". Nó thực hiện các thao tác:

1. Giảm tần suất arr[i] (tương đương loại bỏ).
2. Tăng tần suất arr[i-1] (tương đương thêm lại). Hành động này giống như duy trì một "cửa sổ" đang trượt, in ra số cặp của dãy con còn lại sau khi loại bỏ arr[i] và thêm lại arr[i-1]. Nếu mục đích là in giá trị khi chỉ loại bỏ arr[i] (không thêm lại phần tử nào), code này có thể in sai kết quả hoặc chỉ đúng trong một số trường hợp đặc biệt (ví dụ nếu chỉ xét res -= C(mp[arr[i]]) và mp[arr[i]]--). Tuy nhiên, đây là một cách tiếp cận sinh ra từ suy nghĩ "cập nhật t tổng số cặp thay vì tính lại từ đầu".

Cách Mảng Đếm (Array Counting)

#include <bits/stdc++.h>
using namespace std;
int main() {
  freopen ("LONGK.INP" , "r" , stdin);
  freopen ("LONGK.OUT" , "w" , stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<int> a(n+1), cnt(n+1, 0);
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }

    long long tong = 0;
    for (int i=1;i<=n;i++)
        if (cnt[i]>1) tong += 1LL * cnt[i] * (cnt[i]-1) / 2;

    for (int i=1;i<=n;i++)
        cout << tong - (cnt[a[i]] - 1) << "\n";
}

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

Đây là cách tiếp cận tối ưu nhất và cũng là biến thể của Approach 1.

1. Vì giá trị các phần tử nằm trong khoảng $[1, N]$, ta có thể dùng mảng cnt kích thước $N+1$ thay vì Hash Map để đếm tần suất. Điều này giúp giảm chi phí hao tốn bộ nhớ và tăng tốc độ truy cập.
2. Tính tổng số cặp toàn cục tong.
3. Với mỗi phần tử $A[i]$, số cặp còn lại sau khi loại bỏ nó là tong - (cnt[A[i]] - 1). Đây là cách hiệu quả và ổn định nhất về mặt độ phức tạp.

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

Bài học kinh nghiệm

• Bài toán có tính đối xứng cao: Số cặp bị mất khi loại bỏ một phần tử chỉ phụ thuộc vào tần suất của giá trị đó, không phụ thuộc vào vị trí của các phần tử khác.
• Công thức toán học: Số cặp tạo bởi $k$ phần tử giống nhau là $\frac{k(k-1)}{2}$. Khi giảm $k$ xuống $k-1$, số cặp giảm đi $k-1$.
• Tối ưu hóa cấu trúc dữ liệu: Nếu giá trị đầu vào nằm trong giới hạn nhỏ (như $1 \dots N$), mảng thường nhanh hơn Hash Map.

Lỗi thường gặp

• Sử dụng long long cho biến lưu tổng số cặp vì $N$ có thể lên tới $10^5$, số cặp có thể lên tới $\approx 5 \cdot 10^9$, vượt quá giới hạn của kiểu int.
• Lỗi logic khi cập nhật t tổng số cặp: Cần phân biệt rõ việc tính giá trị mới (sau khi loại bỏ) so với việc duy trì một trạng thái trượt (sliding window).
• Quên xử lý trường hợp tần suất bằng 1 hoặc 0 (trừ đi 0 hoặc 1).