Đếm Cặp Tổng Hợp Lệ

Lời giải: Đếm Cặp Tổng Hợp Lệ

Hướng tiếp cận

Sử dụng hai con trỏ (two pointers) sau khi sắp xếp mảng để đếm số cặp có tổng không vượt quá một giá trị $x$ cho trước. Kết quả là $\text{count}(r)-\text{count}(l-1)$.

Nhận xét quan trọng

1. Số cặp $(i,j)$ với $l\le a_i+a_j\le r$ bằng số cặp có tổng $\le r$ trừ đi số cặp có tổng $\le l-1$.
2. Sau khi sắp xếp, hàm $\text{count}(x)$ — đếm số cặp có tổng $\le x$ — có thể tính bằng hai con trỏ trong $O(n)$.

Thuật toán

1. Sắp xếp mảng $a$.
2. Hàm $\text{count}(x)$: dùng con trỏ $lo=0$, $hi=n-1$:
   • Nếu $a[lo]+a[hi]\le x$: có $hi-lo$ cặp hợp lệ (ghép $lo$ với $lo+1,\dots ,hi$), tăng $lo$.
   • Ngược lại: giảm $hi$.
3. Đáp án là $\text{count}(r)-\text{count}(l-1)$.

Độ phức tạp

• Thời gian: $O(n\log n)$ (sắp xếp) + $O(n)$ (hai con trỏ)
• Bộ nhớ: $O(n)$