题意:
给一个数组,求元组个数满足:
\(l<=a[i]+a[j]<=r,i<j\)
思路:
移项后:\(l-a[i]<=a[j]<=r-a[i]\)
二分查找即可。
注意最后答案会爆\(int\)
代码:
const int maxn=2e5+100;
int n,a[maxn],l,r;
int main(){
int _=read;
while(_--){
n=read,l=read,r=read;
rep(i,1,n) a[i]=read;
sort(a+1,a+1+n);
ll res=0;
//l<=a[i]+a[j]<=r
///l-a[i]<=a[j]<=r-a[i]
rep(i,1,n){
int pos1=lower_bound(a+i+1,a+1+n,l-a[i])-(a+1);
int pos2=upper_bound(a+i+1,a+1+n,r-a[i])-(a+1);
res+=pos2-pos1;
}
printf("%lld\n",res);
}
return 0;
}