思维+二分+暴力
思路
题目中描述的 i<j 这一条可以忽略,这题就是想让求 i!=j且l<=a[i]+a[j]<=r 这样的 (i,j) 一共有多少对.利用二分查找大于等于l-a[j]和小于等于r-a[j]在a数组的两个位置,并计算r-l+1即可.
我感觉我这题是误打误撞混对的
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=2e5+10;
typedef long long ll;
int t,n,l,r,a[N];
int main()
{
cin>>t;
while(t--)
{
memset(a,0,sizeof a);
cin>>n>>l>>r;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
long long res=0;//这里不定义long long这题过不了
for(int i=1;i<n;i++)
{
int l1,r1;
l1=lower_bound(a,a+n,l-a[i])-a;
int left=1,right=n,x=r-a[i];
while(left<right)
{
int mid=(left+right+1)>>1;
if(a[mid]<=x) left=mid;
else
right=mid-1;
}
r1=left;
if(a[r1]+a[i]>=l&&a[i]+a[i+1]<=r)
{
if(l1<=i&&r1>i)
res+=r1-i;
else if(l1>i&&r1>i)
res+=r1-l1+1;
//去重操作,也可以每轮直接加l-r+1最后除2
}
}
cout<<res<<endl;
}
return 0;
}