Trái Đất Lang Thang

Mô tả bài toán

Mặt trời già hóa nhanh chóng, để tồn tại, nhân loại đã khởi động kế hoạch di tản quy mô lớn mang tên "Trái Đất Lang Thang". Khi kế hoạch bắt đầu, nhân loại phải trả giá đắt. Sự khởi động của động cơ hành tinh khiến Trái Đất ngừng quay, gây ra sóng thần khổng lồ. Để cứu sống nhiều người nhất, chính phủ liên minh cần đánh giá thiệt hại. Nhiệm vụ của Cuber QQ là xử lý khu vực Trung Quốc.

Cuber QQ chia Trung Quốc thành lưới n hàng m cột, mỗi ô có độ cao nhất định. Mực nước biển mỗi ngày tăng 1m. Ban đầu, toàn bộ Trung Quốc là một khối liên thông. Cuber QQ cần báo cáo số lượng khối đất liền còn lại sau mỗi ngày.

Lưu ý: Hai ô được coi là liên thông nếu có chung cạnh.

Định dạng đầu vào

Dữ liệu gồm nhiều test case. Dòng đầu tiên chứa T (số test case). Mỗi test case:

• Dòng 1: n và m (kích thước lưới)
• n dòng tiếp theo: m số nguyên h[i][j] (độ cao ô tại hàng i cột j)
• Dòng tiếp theo: q (số truy vấn)
• Dòng cuối: q số nguyên x_i (truy vấn số lượng khối sau x_i ngày)

Định dạng đầu ra

Mỗi test case in ra q số nguyên cách nhau khoảng trắng, là kết quả cho các truy vấn tương ứng.

Ví dụ

Đầu vào mẫu

1
4 5
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5
1 2 3 4 5

Đầu ra mẫu

2 3 1 0 0

Giải thích

Sau 1 ngày có 2 khối liên thông, sau 2 ngày có 3 khối.

Giới hạn dữ liệu

• 1 ≤ T ≤ 5
• 1 ≤ n, m ≤ 1000
• 1 ≤ h[i][j] ≤ 10^9
• 1 ≤ q ≤ 10^5

Phân tích bài toán

Giải pháp thô là thực hiện BFS cho mỗi truy vấn, nhưng độ phức tạp O(T×nmq) quá cao. Ta nhận thấy:

• Ngày x tương ứng với việc đếm số khối có độ cao > x
• Các truy vấn có thể xử lý theo thứ tự giảm dần của x

Sử dụng kỹ thuật Union-Find:

• Ban đầu, mỗi ô là một tập hợp riêng biệt
• Khi xử lý từng ô từ cao xuống thấp, hợp nhất các ô liền kề có cùng độ cao
• Số lượng khối liên thông = tổng số ô chưa bị ngập - số lần hợp nhất thành công

Chi tiết thực hiện:

1. Ghép tất cả ô và truy vấn vào mảng theo độ cao
2. Sắp xếp mảng theo độ cao giảm dần, ưu tiên xử lý truy vấn trước ô có cùng độ cao
3. Duyệt mảng và cập nhật kết quả cho các truy vấn

Mã nguồn hoàn chỉnh

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

const int MAXN = 1100005;
int T, n, m, cnt, q, parent[MAXN], ans[MAXN], grid[1100][1100];
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};

struct Cell {
    bool is_query; // true nếu là truy vấn
    int row, col, height;
    
    // Sắp xếp theo chiều cao giảm dần, ưu tiên truy vấn
    bool operator<(const Cell& other) const {
        if(height != other.height) return height > other.height;
        return is_query < other.is_query;
    }
} cells[MAXN];

// Tìm gốc của tập hợp
int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}

// Hợp nhất hai tập hợp
void merge(int x1, int y1, int x2, int y2) {
    int id1 = (x1-1)*m + y1;
    int id2 = (x2-1)*m + y2;
    int root1 = find(id1), root2 = find(id2);
    
    if(root1 != root2) {
        parent[root1] = root2;
    }
}

int main() {
    cin >> T;
    while(T--) {
        cin >> n >> m;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                cin >> grid[i][j];
                cells[cnt++] = {false, i, j, grid[i][j]};
                parent[cnt] = cnt;
            }
        }
        
        cin >> q;
        for(int i=1; i<=q; i++) {
            int x;
            cin >> x;
            cells[cnt++] = {true, 0, i, x};
        }
        
        sort(cells, cells + cnt);
        
        int block_count = 0;
        for(int i=0; i<cnt; i++) {
            if(cells[i].is_query) {
                ans[cells[i].col] = block_count;
            } else {
                int r = cells[i].row;
                int c = cells[i].col;
                block_count++;
                
                for(int d=0; d<4; d++) {
                    int nr = r + dx[d];
                    int nc = c + dy[d];
                    if(nr < 1 || nc < 1 || nr > n || nc > m) continue;
                    if(grid[nr][nc] < cells[i].height) continue;
                    merge(r,c,nr,nc);
                }
            }
        }
        
        for(int i=1; i<=q; i++) {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
    return 0;
}