P1102- A-B 数对(给一串数及一个数C,算 A-B=C 的数对的个数)

题目

输入样例#1：
4 1
1 1 2 3

输出样例#1：
3

说明 N≤2e5
所有输入数据都在longint范围内。

A-B=C,也就是对于每一个A找出来满足=A-C的B的个数。
1.排序完二分，对于每一个A，lower_bound，upper_bound (A-C) 的差就是对于A满足条件的值。(A的枚举顺序不要求,但是二分查找的时候还是要排序的)
2.既然都排好序了，那就A从小到大枚举。对于每个A，要做的就是找出B=A-C的那个范围的区间。A呈递增，区间的左右端点呈不递减。满足尺取要求。
while(a[r1]<a[i]-c) r1++;
while(a[r2]<=a[i]-c) r2++;

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define m(a,b) memset(a,b,sizeof a)
#define en '\n'
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N];
int main()
{
    int n;ll t;scanf("%d%lld",&n,&t);
    int tot=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int r1=1,r2=1;ll sum=0;
    for(int i=1;i<=n;i++)
    {
        while(a[r1]<a[i]-t&&r1<=n)
            r1++;//循环结束后r1是第一个=a[i]-t的位置。
        while(a[r2]<=a[i]-t&&r2<=n)
            r2++;//循环结束后r2-1是最后一个=a[i]-t的位置。
        sum+=r2-r1;
    }
    printf("%lld\n",sum);
}