### Tóm tắt bài toán
Bài toán yêu cầu đếm số cặp chỉ số $(i, j)$ với $i < j$ sao cho:
$$
l \leq A_i + A_j \leq r
$$
với $l, r$ và mảng $A$ được cho trước.
---
### Hướng giải
Ta nhận thấy rằng:
$$
l \leq A_i + A_j \leq r
\quad \Leftrightarrow \quad
l - A_j \leq A_i \leq r - A_j
$$
Khi cố định chỉ số $j$, bài toán trở thành việc **đếm số phần tử $A_i$** nằm trong đoạn $[l - A_j, r - A_j]$.
Để làm điều này một cách hiệu quả, ta có thể **sắp xếp mảng $A$** và sử dụng **thuật toán tìm kiếm nhị phân** (binary search) để xác định nhanh số lượng phần tử thỏa mãn điều kiện.
Ta có thể thực hiện việc này bằng hai cách:
- **(C++)** Sử dụng các hàm built-in `lower_bound` và `upper_bound`.
- **(Python hoặc thủ công)** Thực hiện **chặt nhị phân** bằng cách tìm chỉ số $ll$ nhỏ nhất sao cho $A_{ll} \ge l - A_j$ và chỉ số $rr$ lớn nhất sao cho $A_{rr} \le r - A_j$.
Cuối cùng, ta cộng tổng số phần tử nằm trong các đoạn tìm được để thu được kết quả.
---
#### Code tham khảo
````cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, l, r;
cin >> n >> l >> r;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
long long ans = 0;
for (int i = 0; i < n; i++)
{
int nl = l - a[i];
int nr = r - a[i];
int left = i + 1, right = n;
while (left < right)
{
int mid = (left + right) / 2;
if (a[mid] < nl)
left = mid + 1;
else
right = mid;
}
int ll = left;
// int ll = lower_bound(a.begin() + i + 1, a.end(), nl) - a.begin();
left = i + 1, right = n;
while (left < right)
{
int mid = (left + right) / 2;
if (a[mid] <= nr)
left = mid + 1;
else
right = mid;
}
int rr = left;
// int rr = upper_bound(a.begin() + i + 1, a.end(), nr) - a.begin();
ans += rr - ll;
}
cout << ans;
}
````
Defylogicguy
Created at
0 likes