C. Number of Pairs div3_atcoder given an n, find the number of pairs (i,j)

C. Number of Pairs
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given an array a of n integers. Find the number of pairs (i,j) (1≤i<j≤n) where the sum of ai+aj is greater than or equal to l and less than or equal to r (that is, l≤ai+aj≤r).

For example, if n=3, a=[5,1,2], l=4 and r=7, then two pairs are suitable:

i=1 and j=2 (4≤5+1≤7);
i=1 and j=3 (4≤5+2≤7).
Input
The first line contains an integer t (1≤t≤104). Then t test cases follow.

The first line of each test case contains three integers n,l,r (1≤n≤2⋅105, 1≤l≤r≤109) — the length of the array and the limits on the sum in the pair.

The second line contains n integers a1,a2,…,an (1≤ai≤109).

It is guaranteed that the sum of n overall test cases does not exceed 2⋅105.

Output
For each test case, output a single integer — the number of index pairs (i,j) (i<j), such that l≤ai+aj≤r.

Example
input

4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1
1
2
3
4
5
6
7
8
9

output

2
7
0
1

1
2
3
4
5

题意：
给出一个数组找出有多少对两两相加处于【l,r】中。

题解：
题意非常的简单，就是数据范围比较大，要是枚举每对会超时，所以我们可将问题转换。
求出小于等于 r 的对数 A， 在求出小于等于 l-1 的对数B，即A-B为处于【l,r】中的对数。
一样的道理：处于【l,r】中的对数=处于【l,INF】中的对数 – 处于【r+1,INF】中的对数。

介绍两个二分函数：

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

别人眼中一道简单的题目到了我这就变的无比困难啊，蒻蒻的说句要走的路还很长。

AC：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N=2e5+110;
int a[N];
int t,n,l,r;
ll cnt(int x){
    int j=n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        while(j>i&&a[i]+a[j]>x){//找到坐标最大的a[j]能和a[i]相减处于【0，x】中
            j--;
        }
        if(j>i){//坐标相减即为a[i]最多有j-i对数在【0，x】中。
            ans+=j-i;
        }
    }
    return ans;
}
int main()
{
    cin >> t;
    while(t--){
        cin >> n >> l >> r;
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        sort(a+1,a+1+n);
        //将小于 r 的对数算出 - 小于 l-1 的对数算出等于 [l,r] 中的对数
        
        cout << cnt(r)-cnt(l-1) << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

AC:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N=2e5+100;

int a[N];
int t,n,l,r;
ll solve(int cur){
    ll ans=0;
    for(int i=1;i<=n;i++){
        int idx=lower_bound(a+1,a+i,cur-a[i])-a;//二分找到大于cur-a[i]的最大值
        ans+=i-idx;
    }
    return ans;
}
int main()
{

    cin >> t;
    while(t--){
        cin >> n >> l >> r;
        for(int i=1;i<=n;i++)cin >> a[i];
        sort(a+1,a+1+n);
        cout << solve(l)-solve(r+1) << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

不要固定自己的思维，解题方法可能就在你的思维之外的不远处。转换思想非常重要。