Editorial for median: Truy vấn trung vị

Hiểu bài toán

Bài toán yêu cầu xử lý một dãy số nguyên dương không giảm ban đầu và một loạt m truy vấn. Với mỗi truy vấn, ta cần in ra phần tử trung vị của dãy hiện tại (tức là phần tử ở vị trí thứ [(n+1)/2] nếu dãy được sắp xếp tăng dần), và sau đó loại bỏ phần tử này khỏi dãy. Dãy số ban đầu có thể rất lớn (n <= 10^6), do đó cần một giải pháp hiệu quả về thời gian và bộ nhớ.

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

Cách Mô phỏng trực tiếp (Dùng mảng và xóa phần tử)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n, Q;
    scanf("%d%d", &n, &Q);
    int a[n], i, j;
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (j = 0; j < Q; j++) {
        int position = (n + 1) / 2;
        printf("%d ", a[position - 1]);
        // Shift elements to the left to remove the median
        for (i = position; i < n; i++) {
            a[i - 1] = a[i];
        }
        n--;
    }
    return 0;
}

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

Cách tiếp cận này sử dụng một mảng để lưu trữ dãy số. Sau mỗi truy vấn, ta tìm vị trí trung vị, in ra giá trị tại vị trí đó, và sau đó dồn các phần tử phía sau lên để xóa phần tử đó khỏi mảng. Với mỗi truy vấn, việc dồn mảng mất O(n) thời gian. Tổng thời gian thực hiện là O(n*m), dẫn đến khả năng bị TLE (Time Limit Exceeded) với n, m lên tới 10^6.

Cách Giả lập thông minh (Duy trì chỉ số)

#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int a[n+1];
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int g=(n+1)/2;
    int back=g;
    printf("%d ",a[g]);
    for(int u=2;u<=m;u++){
        int d=(n+2-u)/2;
        if(d<back){
            printf("%d ",a[d]);
        }
        else{
            printf("%d ",a[d+u-1]);
        }
        back=d;
    }
}

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

Phương pháp này nhận thấy rằng chúng ta không cần phải thực sự xóa phần tử khỏi mảng. Dãy ban đầu đã được sắp xếp. Ta chỉ cần theo dõi chỉ số của phần tử trung vị trong mảng ban đầu.

• Truy vấn 1: In ra a[(n+1)/2]. Giả sử chỉ số này là mid.
• Khi xóa phần tử này, các phần tử bên trái của nó không thay đổi vị trí tương đối, nhưng các phần tử bên phải sẽ bị shift trái 1 đơn vị.
• Truy vấn 2: Phần tử trung vị mới sẽ nằm ở vị trí trừu tượng mới. Ta có thể tính toán vị trí thực tế trong mảng ban đầu dựa trên số lượng phần tử đã xóa. Công thức c cụ thể: Với mỗi truy vấn u (tính từ 2), ta tính vị trí trừu tượng d. Nếu d nhỏ hơn chỉ số của phần tử vừa xóa (back), ta lấy phần tử tại a[d]. Ngược lại, ta lấy a[d + u - 1] (bù cho số lượng phần tử đã xóa nằm trước nó). Cách này loại bỏ hoàn toàn thao tác dồn mảng, chạy rất nhanh O(m).

Cách Cấu trúc dữ liệu Heap (Mid-Heap)

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Max heap chứa nửa bên trái (nhỏ hơn hoặc bằng trung vị)
    // Min heap chứa nửa bên phải (lớn hơn trung vị)
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (left.empty() || x <= left.top()) {
            left.push(x);
        } else {
            right.push(x);
        }
    }

    // Cân bằng để left luôn có số lượng phần tử bằng hoặc nhiều hơn right đúng 1 đơn vị
    // Trung vị sẽ luôn là left.top()
    while (left.size() > right.size() + 1) {
        right.push(left.top());
        left.pop();
    }
    while (right.size() > left.size()) {
        left.push(right.top());
        right.pop();
    }

    for (int i = 0; i < m; i++) {
        cout << left.top() << " ";
        left.pop();

        // Cân bằng lại sau khi xóa
        while (left.size() > right.size() + 1) {
            right.push(left.top());
            left.pop();
        }
        while (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }

    return 0;
}

• Time Complexity: O((n + m) log n)
• Space Complexity: O(n)

Sử dụng cấu trúc dữ liệu Heap (Priority Queue) để quản lý động dãy số. Ta duy trì 2 heap:

1. Max-Heap (left): chứa nửa dãy bên trái (các số nhỏ hơn hoặc bằng trung vị).
2. Min-Heap (right): chứa nửa dãy bên phải (các số lớn hơn trung vị). Luôn đảm bảo size(left) == size(right) hoặc size(left) == size(right) + 1. Phần tử trung vị luôn là left.top(). Với mỗi truy vấn:

• In ra left.top() và xóa nó.
• Nếu kích thước bị lệch, ta di chuyển phần tử từ heap này sang heap kia để cân bằng lại. Phương pháp này linh hoạt và có thể xử lý các bài toán tương tự với dãy số đến từ nhiều nguồn hoặc thay đổi giá trị liên tục (Dynamic Median).

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

Bài học kinh nghiệm

• Dãy ban đầu đã được sắp xếp không giảm, đây là chìa khóa để tối ưu hóa.
• Việc xóa phần tử khỏi mảng là thao tác đắt đỏ (O(n)). Thay vào đó, ta có thể tính toán vị trí ẩn của phần tử trung vị tiếp theo dựa trên các phần tử đã xóa trước đó.
• Cấu trúc dữ liệu Mid-Heap (2 Heap) là kỹ thuật chuẩn để tìm trung vị động.

Lỗi thường gặp

• Lỗi truy cập ngoài mảng (Out of bounds) khi tính toán chỉ số ẩn, đặc biệt khi chỉ số âm hoặc vượt quá n.
• Sử dụng thuật toán O(n*m) cho dữ liệu lớn (n, m ~ 10^6) chắc chắn会导致 Time Limit Exceeded.
• Quên xử lý các trường hợp biên như khi dãy có 1 phần tử.