思路

排序 + 二分/双指针

过程

alt

代码

#include <iostream>
#include <algorithm>

using namespace std;

using LL = long long;

const int N = 2e5 + 10;
int n, l, r, a[N];

int main()
{
    cin >> n >> l >> r;
    for(int i = 0;i < n;i ++) cin >> a[i];
    sort(a, a + n);
    LL ans = 0;
    for(int i = 0;i < n;i ++)
    {
        int x = i + 1, y = n - 1;
        while(x < y)
        {
            int mid = (x + y) >> 1;
            if(a[mid] >= a[i] + l) y = mid;
            else x = mid + 1;
        }
        int begin = 0;
        if(a[x] < a[i] + l) begin = x + 1;
        else begin = x;
        x = i + 1, y = n - 1;
        while(x < y)
        {
            int mid = (x + y + 1) >> 1;
            if(a[mid] > a[i] + r) y = mid - 1;
            else x = mid;
        }
        int end = x;
        ans += end - begin + 1;
    }
    cout << ans << endl;
    return 0;
}
#include <iostream>
#include <algorithm>

using namespace std;

using LL = long long;

const int N = 2e5 + 10;
int n, l, r, a[N];

LL find(int x)
{
    int i = 0, j = 0;
    LL ans = 0;
    while(j < n)
    {
        while(a[j] - a[i] > x) i ++;
        ans += j - i;
        j ++;
    }
    return ans;
}

int main()
{
    cin >> n >> l >> r;
    for(int i = 0;i < n;i ++) cin >> a[i];
    sort(a, a + n);
    cout << find(r) - find(l - 1) << endl;
    return 0;
}