Hướng dẫn giải của Tô Màu Theo Số

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Tô Màu Theo Số

Hướng tiếp cận

Bài toán yêu cầu đếm số vùng liên thông của các ô cùng màu trong một hình chữ nhật con tùy ý. Có hai cách tiếp cận chính: dùng công thức Euler cho đồ thị phẳng (Euler's formula), hoặc dùng cây đoạn 2 chiều (2D segment tree).

Nhận xét quan trọng

Với một hình chữ nhật con, ta cần đếm số thành phần liên thông (TPLT) của đồ thị mà các đỉnh là ô và cạnh nối các ô liền kề cùng màu.
Cây đoạn 2D (2D Segment Tree): Phân rã hình chữ nhật thành các đoạn được lưu sẵn trong cây đoạn. Mỗi nút lưu số TPLT và danh sách ID thành phần ở các biên (trên, dưới, trái, phải). Khi truy vấn, ghép các đoạn và dùng union-find để hợp nhất TPLT tại các biên chung.
Union-Find với timestamp: Để tránh reset union-find $O (N + M)$ lần mỗi truy vấn, dùng mảng seen[] lưu timestamp. Khi truy cập phần tử lần đầu trong một truy vấn mới, tự động khởi tạo nó.

Thuật toán

Xây dựng cây đoạn 2D

Cây đoạn ngoài phân chia theo hàng ( $Y$ ), cây đoạn trong phân chia theo cột ( $X$ ).
Mỗi nút [ny][nx] bao phủ hình chữ nhật [sy1,sy2] x [sx1,sx2] lưu:
- amt: số TPLT trong hình chữ nhật này
- top[x], bot[x]: ID TPLT của ô ở hàng đầu/cuối, cột $x$
- lft[y], rgt[y]: ID TPLT của ô ở hàng $y$ , cột đầu/cuối
Khi ghép hai đoạn theo chiều dọc (hàng midy và midy+1):
- Với mỗi cột $x$ : nếu canvas[midy][x] == canvas[midy+1][x], hợp nhất hai TPLT.
Khi ghép hai đoạn theo chiều ngang: tương tự với cột.

Trả lời truy vấn

Khởi tạo timestamp mới, cur_res = 0.
Dùng cây đoạn tìm các nút bao phủ [r1,r2] x [c1,c2].
Với mỗi nút được chọn, thêm amt[ny][nx] vào cur_res và hợp nhất tại các biên chung.
Kết quả sau khi hợp nhất là cur_res.

Độ phức tạp

Xây dựng: $O (N M \log N \log M)$
Mỗi truy vấn: $O ((N + M) \log N \log M)$
Tổng: $O (N M \log N \log M + Q (N + M) \log N \log M)$

Với $N = M = 1000$ , $Q = 1000$ : vừa đủ trong giới hạn thời gian mở rộng.

Bình luận

Không có bình luận tại thời điểm này.