1. Tóm tắt đề bài

Cho một dãy gồm ~N~ số nguyên có thể có giá trị rất lớn (lên tới ~10^9~). Hãy nén (rời rạc hóa) dãy số này về tập các số nguyên liên tiếp bắt đầu từ ~1~ sao cho vẫn giữ nguyên quan hệ thứ tự ban đầu giữa các phần tử:

~ A_i < A_j \iff \text{Compressed}(A_i) < \text{Compressed}(A_j) ~

Các giá trị bằng nhau sau khi nén sẽ có cùng một giá trị nén.

• Dữ liệu vào (Input):
  • Dòng 1: Số nguyên dương ~N~ (~1 \le N \le 10^5~).
  • Dòng 2: ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~-10^9 \le A_i \le 10^9~).
• Dữ liệu ra (Output):
  • Ghi trên một dòng gồm ~N~ số nguyên sau khi đã được nén giá trị, các số cách nhau bởi một khoảng trắng.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • ~N \le 10^5~.
  • Giá trị phần tử: ~-10^9 \le A_i \le 10^9~.
  • Vì khoảng giá trị lên tới ~10^9~, không thể sử dụng mảng đếm phân phối tĩnh cnt[1000000000] để đánh chỉ số.

• Kỹ thuật Rời rạc hóa tọa độ (Coordinate Compression):

  • Bản chất của bài toán là thay thế mỗi giá trị ~A_i~ bằng thứ hạng (rank) của nó trong danh sách các giá trị phân biệt đã được sắp xếp tăng dần.
  • Quy trình chuẩn gồm 3 bước:
    1. Sao chép dãy ban đầu ~A~ sang một mảng/vector phụ ~B~.
    2. Sắp xếp ~B~ tăng dần và loại bỏ tất cả các phần tử trùng nhau (bằng sort kết hợp unique).
    3. Với mỗi phần tử ~A_i~ trong dãy ban đầu, dùng tìm kiếm nhị phân (lower_bound) trên ~B~ để xác định vị trí của ~A_i~. Do bài toán yêu cầu các giá trị nén bắt đầu từ ~1~, giá trị nén chính là (vị trí tìm được trong B) + 1.

• Đánh giá thời gian & Bộ nhớ:

  • Bước sắp xếp và lọc trùng: ~\mathcal{O}(N \log N)~.
  • Bước tìm kiếm nhị phân cho ~N~ phần tử: ~N \times \mathcal{O}(\log N) = \mathcal{O}(N \log N)~.
  • Tổng số thao tác ~\approx 2 \times 10^5 \times 17 \approx 3.4 \times 10^6~ phép tính, thời gian thực thi ~< 0.05~ giây (hoàn toàn vượt qua giới hạn ~1.0~ giây).
  • Bộ nhớ: Lưu 2 vector kích thước ~10^5~ số nguyên chỉ tốn chưa đến ~2\text{ MB}~.

3. Thuật toán xử lý

• Cấu trúc lưu trữ:

  • vector<int> a: Lưu dãy số ban đầu để bảo toàn thứ tự xuất hiện.
  • vector<int> b: Bản sao của ~a~ dùng để sắp xếp và lọc bỏ phần tử trùng.

• Các bước thực hiện:

  1. Đọc số nguyên ~n~.
  2. Dùng vòng lặp ~i~ chạy từ ~0~ đến ~n - 1~: đọc từng số ~x~, lần lượt thêm vào cả a và b bằng push_back.
  3. Sắp xếp vector ~b~ tăng dần:
     • sort(b.begin(), b.end());
  4. Lọc bỏ các phần tử trùng lặp liên tiếp trong ~b~:
     • b.erase(unique(b.begin(), b.end()), b.end());
  5. Rời rạc hóa và in kết quả:
     • Duyệt từng phần tử a[i] trong dãy ban đầu:
       • Tìm vị trí xuất hiện của a[i] trong ~b~ bằng lower_bound: int val = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
       • In val kèm một dấu cách.
     • Xuống dòng bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(N \log N)~ — Tối ưu tuyệt đối.
  • Không gian (bộ nhớ): ~\mathcal{O}(N)~.

4. Mã nguồn cài đặt (C++)

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

int main() {
    // Tối ưu tốc độ nhập/xuất chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> b(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }

    // Sắp xếp tăng dần
    sort(b.begin(), b.end());

    // Loại bỏ các phần tử trùng lặp
    b.erase(unique(b.begin(), b.end()), b.end());

    // Tìm vị trí nén và in kết quả
    for (int i = 0; i < n; i++) {
        int val = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        cout << val << " ";
    }
    cout << endl;

    return 0;
}