Giao Nhau Của Những Người Bạn

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:

$$\text{Kết quả}=\text{Tổng giao nhau}-\text{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|\le K$) mà giao nhau.

Nhận xét quan trọng

1. Gọi $ra[x]$ là vị trí của giống bò $x$ ở bên trái, $rb[x]$ là vị trí ở bên phải. Hai giống $x$ và $y$ giao nhau khi và chỉ khi $(ra[x]-ra[y])$ và $(rb[x]-rb[y])$ trái dấu.

2. Tổng giao nhau bằng số nghịch thế trong dãy $rb[a[1]],rb[a[2]],\dots ,rb[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)$.

3. Để đếm giao nhau thân thiện, xét các cặp $(a[i],a[j])$ với $i<j$ (tức $ra[a[i]]<ra[a[j]]$) mà $|a[i]-a[j]|\le K$ và $rb[a[i]]>rb[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]=rb[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ó $ra[a[i]]=i$. Ta cần đếm số $j<i$ thỏa:

• $|a[j]-a[i]|\le K$ (thân thiện theo giống)
• $rb[a[j]]>rb[a[i]]$ (giao nhau vì $ra[a[j]]<ra[a[i]]$ nhưng $rb[a[j]]>rb[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ị $rb$ 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ó $rb>rb[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],rb[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ả

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

Độ phức tạp

• Thời gian: $O(N{\log }^{2}N)$
  • 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ử