Tô Màu Theo Số

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

1. 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.

2. 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.

3. 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

1. Khởi tạo timestamp mới, cur_res = 0.
2. Dùng cây đoạn tìm các nút bao phủ [r1,r2] x [c1,c2].
3. 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.
4. Kết quả sau khi hợp nhất là cur_res.

Độ phức tạp

• Xây dựng: $O(NM\log N\log M)$
• Mỗi truy vấn: $O((N+M)\log N\log M)$
• Tổng: $O(NM\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.