---
# System prepended metadata

title: Water Solution

---

$\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).