Hướng dẫn giải của Vòi Phun Nước

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: 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 \leq x$ và $j \leq y$ .
Được bón phân: tồn tại vòi tại $(i, j)$ với $i \geq x$ và $j \geq 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 $\Leftrightarrow$ tồn tại $i \leq x$ sao cho $A [i] \leq 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 $\Leftrightarrow$ tồn tại $i \geq x$ sao cho $A [i] \geq y$ .

Định nghĩa:

$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$ ).
$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 $top [i]$ và $lft [j]$

$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.
$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ó $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à: $tot (x_{2}) = i \cdot \frac{top [i] \cdot (top [i] + 1)}{2}$ (tổng số cặp $(y_{1}, y_{2})$ với $0 \leq y_{1} < y_{2} \leq 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} < 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:

$y_{1} < j$ : Dùng công thức trực tiếp ${bad}_{2} = i \cdot (j \cdot j - j (j - 1) / 2) (\mod M O D)$ .
$y_{1} \geq j$ : Dùng prefix sum: ${bad}_{1} = \sum_{y = j}^{top [i] - 1} lft [y] \cdot (N - y) - (N - top [i]) \cdot \sum_{y = j}^{top [i] - 1} 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 $lft$ ), nên tổng thời gian xử lý là $O (N)$ .

Tổng kết

$ans = \sum_{i = 1}^{N - 1} (tot (i) - bad (i)) (\mod 10^{9} + 7)$

Độ 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 $lft$ (không tăng khi $j$ tăng) và $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)$ .

Bình luận

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