Vòi Phun Nước

Lời giải: Vòi Phun Nước (Sprinklers)

Nhận xét quan trọng

Trước hết, cần xác định điều kiện để một điểm $(x,y)$ là hợp lệ:

• Được tưới nước: tồn tại vòi tại $(i,j)$ với $i\le x$ và $j\le y$.
• Được bón phân: tồn tại vòi tại $(i,j)$ với $i\ge x$ và $j\ge y$.

Do các vòi tạo thành một hoán vị (mỗi hàng và cột có đúng một vòi), ta có thể xác định:

• Điểm $(x,y)$ được tưới nước $\iff$ tồn tại $i\le x$ sao cho $A[i]\le y$ (với $A[i]$ là tọa độ $y$ của vòi ở cột $x=i$).
• Điểm $(x,y)$ được bón phân $\iff$ tồn tại $i\ge x$ sao cho $A[i]\ge y$.

Định nghĩa:

• $\text{lft}[y]$ = giá trị nhỏ nhất của $x$ sao cho $(x,y)$ hợp lệ (tức là tọa độ $x$ nhỏ nhất để cột đó "kích hoạt" phân bón cho $y$).
• $\text{top}[x]$ = giá trị $y$ lớn nhất sao cho $x$ có thể là cạnh phải của một hình chữ nhật.

Thuật toán

Bài toán yêu cầu đếm số cặp $(x_1,y_1,x_2,y_2)$ với $x_1<x_2$, $y_1<y_2$ sao cho toàn bộ hình chữ nhật $[x_1,x_2]\times [y_1,y_2]$ hợp lệ.

Ý tưởng chính: Duyệt $x_2$ từ 1 đến $N-1$, với mỗi $x_2$ cố định, đếm số cặp $(x_1,y_1,y_2)$ hợp lệ.

Tính $\text{top}[i]$ và $\text{lft}[j]$

• $\text{top}[i]=max(A[i],A[i+1],\dots ,A[N-1])$: $y$-tối đa để cột $i$ có thể là cạnh trái.
• $\text{lft}[j]$: với mỗi $j$, đây là $x$-tối thiểu để điểm $(x,j)$ hợp lệ. Tính bằng cách duyệt giảm dần: với vòi tại cột $i$ (tọa độ $y$ là $A[i]$), cập nhật tất cả $j<A[i]$ có $\text{lft}[j]=i$.

Đếm tổng hình chữ nhật

Với $x_2$ cố định, số cặp $(y_1,y_2)$ hợp lệ với $x_1$ cố định là: $$\text{tot}(x_2)=i·\frac{\text{top}[i]·(\text{top}[i]+1)}{2}$$ (tổng số cặp $(y_1,y_2)$ với $0\le y_1<y_2\le \text{top}[i]$, nhân với số lựa chọn $x_1\in [0,i-1]$).

Trừ các hình chữ nhật không hợp lệ (bad)

Một hình chữ nhật không hợp lệ khi có điểm $(x_1,y_1)$ không hợp lệ, tức là $x_1<\text{lft}[y_1]$.

Với $j=$ cận dưới của vùng $y$ được xét, ta chia thành 2 trường hợp:

1. $y_1<j$: Dùng công thức trực tiếp ${\text{bad}}_2=i·(j·j-j(j-1)/2)\left(\mathrm{mod}MOD\right)$.
2. $y_1\ge j$: Dùng prefix sum: ${\text{bad}}_1={\sum }_{y=j}^{\text{top}[i]-1}\text{lft}[y]·(N-y)-(N-\text{top}[i])·{\sum }_{y=j}^{\text{top}[i]-1}\text{lft}[y]$.

Với mỗi $x_2=i$, con trỏ $j$ di chuyển đơn điệu (do tính đơn điệu của $\text{lft}$), nên tổng thời gian xử lý là $O(N)$.

Tổng kết

$$\text{ans}=\sum _{i=1}^{N-1}(\text{tot}(i)-\text{bad}(i))\left(\mathrm{mod}{10}^9+7\right)$$

Độ phức tạp

• Thời gian: $O(N)$
• Bộ nhớ: $O(N)$

Điểm mấu chốt là tính đơn điệu của mảng $\text{lft}$ (không tăng khi $j$ tăng) và $\text{top}$ (không tăng khi $i$ tăng), cho phép dùng hai con trỏ và prefix sum để giải trong $O(N)$.