Hướng dẫn giải của Giao Nhau Của Những Người Bạn

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: Giao Nhau Của Những Người Bạn

Hướng tiếp cận

Đây là bài toán đếm nghịch thế (inversion counting) với điều kiện lọc. Thay vì đếm trực tiếp các cặp không thân thiện mà giao nhau, ta dùng:

$Kết quả = Tổng giao nhau - Giao nhau thân thiện$

trong đó:

Tổng giao nhau: tổng số cặp bò giao nhau (không kể điều kiện thân thiện).
Giao nhau thân thiện: số cặp thân thiện ( $| a - b | \leq K$ ) mà giao nhau.

Nhận xét quan trọng

Gọi $r a [x]$ là vị trí của giống bò $x$ ở bên trái, $r b [x]$ là vị trí ở bên phải. Hai giống $x$ và $y$ giao nhau khi và chỉ khi $(r a [x] - r a [y])$ và $(r b [x] - r b [y])$ trái dấu.
Tổng giao nhau bằng số nghịch thế trong dãy $r b [a [1]], r b [a [2]], \dots, r b [a [N]]$ (trong đó $a [i]$ là giống bò ở vị trí $i$ bên trái). Đây là bài toán đếm nghịch thế cổ điển, giải bằng BIT (Binary Indexed Tree) trong $O (N \log N)$ .
Để đếm giao nhau thân thiện, xét các cặp $(a [i], a [j])$ với $i < j$ (tức $r a [a [i]] < r a [a [j]]$ ) mà $| a [i] - a [j] | \leq K$ và $r b [a [i]] > r b [a [j]]$ . Ta cần đếm số nghịch thế trong không gian 2D: với điều kiện về giá trị giống bò VÀ về vị trí bên phải.

Thuật toán

Bước 1: Đếm tổng nghịch thế (O(N log N))

Xây dựng dãy $c [i] = r b [a [i]]$ với $i = 1 \dots N$ . Đếm số nghịch thế trong $c$ bằng BIT: duyệt từ trái sang phải, với mỗi $c [i]$ đếm số phần tử đã xét lớn hơn $c [i]$ .

Bước 2: Đếm nghịch thế thân thiện (O(N log² N))

Duyệt theo thứ tự bên trái ( $i = 1 \dots N$ ). Tại bước $i$ , giống bò $a [i]$ có $r a [a [i]] = i$ . Ta cần đếm số $j < i$ thỏa:

$| a [j] - a [i] | \leq K$ (thân thiện theo giống)
$r b [a [j]] > r b [a [i]]$ (giao nhau vì $r a [a [j]] < r a [a [i]]$ nhưng $r b [a [j]] > r b [a [i]]$ )

Dùng cây phân đoạn merge-sort (merge sort tree) đánh chỉ số theo giá trị giống bò $[1 \dots N]$ . Mỗi nút của cây lưu danh sách đã được sắp xếp các giá trị $r b$ của các giống bò đã được chèn vào phạm vi đó.

Truy vấn: với giống $a [i]$ , đếm các phần tử trong phạm vi giống $[max (1, a [i] - K), min (N, a [i] + K)]$ có $r b > r b [a [i]]$ . Mỗi truy vấn mất $O (\log^{2} N)$ (đi qua $O (\log N)$ nút, mỗi nút tìm nhị phân trong danh sách sắp xếp).
Chèn: sau khi truy vấn, chèn $(a [i], r b [a [i]])$ vào cây.

Lưu ý: Ta truy vấn trước khi chèn, đảm bảo chỉ đếm $j < i$ .

Kết quả

$Output = Tổng nghịch thế - Nghịch thế thân thiện$

Độ phức tạp

Thời gian: O(Nlog2N)
- Bước 1: $O (N \log N)$
- Bước 2: $O (N \log^{2} N)$ — mỗi trong $N$ bước có $O (\log^{2} N)$ cho truy vấn và $O (\log N)$ cho chèn
Bộ nhớ: $O (N \log N)$ — cây phân đoạn merge-sort lưu tổng $O (N \log N)$ phần tử

Bình luận

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