$\Huge\text{Water Solution}$ ---------- :::info 🔗 Links: 📌 Tags: `DSU` ✍ Writer: Hoàng Việt 📄 Content: [TOC] ::: --------- ## Thuật toán Ta có $k$ chiều cao khác nhau của các cột bê tông. Dùng một mảng $v$ chứa $k$ giá trị khác nhau đó theo thứ tự tăng dần. Ta sẽ xét mực nước thay đổi với $k - 1$ giai đoạn, với giai đoạn thứ $i (1 \le i < k)$ mực nước tăng độ cao từ $v_i$ lên $v_{i + 1}$. Mực nước ban đầu có độ cao là $v_1$. Với từng giai đoạn, ta có $f(i)$ là số cột bê tông có thể giữ được lượng nước có độ cao $v_{i + 1}$ mà không để nước chảy ra ngoài. Ta có kết quả bài toán là: $\sum_{i = 1}^{k - 1} f(i)$ * $(v_{i + 1} - v_i)$. Để tính được $f(i)$. Giả sử ta xóa hết các cột có độ cao lớn hơn $v_{i}$ và giữ lại các cột còn lại. Các cột còn lại sẽ tạo thành các vùng liên thông mà hai ô bất kì trong vùng liên thông đều có thể đi đến nhau bằng cách di chuyển qua 4 ô kề cạnh. Vùng liên thông nào chứa ít nhất một cột ở mép bảng thì nguyên cả vùng liên thông đó sẽ không chứa được mực nước lớn hơn $v_i$ mà sẽ làm nước chảy ra ngoài vì các cột được xét đều có độ cao bé hơn hoặc bằng $v_i$. Khi đó $f(i)$ sẽ là số lượng cột nằm trong vùng liên thông mà trong vùng liên thông đó không có bất kì một cột nào ở mép bảng. Sử dụng $DSU$ để duy trì các vùng liên thông. Ban đầu, tất cả các cột bê tông đều bị xóa. Xét các độ cao tăng dần, với độ cao $i$ thì thêm các cột có chiều cao $v_i$ vào bảng. Với mỗi cột được thêm vào, xét bốn ô kề cạnh nếu ô nào có chiều cao bé hơn hoặc bằng $v_i$ thì hợp nhất hai vùng liên thông lại với nhau và giữ một mảng chứa diện tích của mỗi vùng liên thông. Độ phúc tạp $O(n$ * $m$ * $log(n$ * $m))$. ------------ Tham khảo code mẫu ở [đây](https://ideone.com/dPq3UF).