Luogu P1102 A-B number pair (dichotomy, map, double pointer)

Simple A-B

describe
This is a simple question , Give a string of numbers and a number C, Ask to calculate all A - B = C The number of pairs of （ The same number pairs in different positions count different number pairs ）.
Input
There are two lines of input .
first line , Two integers N, C.1=<N<=2e5 , C>=1
The second line ,N It's an integer , As the number of strings required to be processed .

Output
a line , Indicates that the number contained in the string satisfies A - B =C The number of pairs of .

sample input 1
4 1
1 1 2 3
sample output 1
3

sample input 2
6 1
1 1 1 2 2 2
sample output 2
9

It is worth noting that , May be violent int
such as

 Input 
200000 1
1e5 individual 1,1e5 individual 2
 Output 
1e10 > int type 
(int The maximum number of deposits is about 2e9)

Two points

Simple dichotomous template question
Prioritize , Find out bidi i It's a big number C Coordinates of the leftmost endpoint and the rightmost endpoint of ,( Right endpoint coordinates minus left endpoint coordinates plus 1) It means how many are better than i It's a big number C
Examples 2 in

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N=2e5+10;
int n,c,a[N];
ll res;
int main()
{
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // save cin,cout Time ;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
    
        int l=i+1,r=n;
        while(l<r)  // Find the leftmost endpoint ;r=mid;
      {
    
        int mid=l+r >>1;
         // amount to (l+r)/2, It looks a little more powerful hh,+ Priority is greater than >>( Move right ) priority ;
        if(a[mid]-a[i]>=c)
            r=mid;
        else
            l=mid+1;
      }
      int k=l;
      l=i+1,r=n;
      while(l<r)// Find the rightmost endpoint ;l=mid;
      {
    
          int mid=l+r+1 >> 1;// Change l, want +1, Prevent a dead cycle 
          if(a[mid]-a[i]<=c)
            l=mid;
          else
            r=mid-1;
      }
      int kk=l;
      if(a[kk]-a[i]==c&&a[k]-a[i]==c)
        res+=kk-k+1;
    }
    cout<<res<<endl;
    return 0;
}

lower_bound()
upper_bound()

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N=2e5+10;
int n,c,a[N],b[N];
ll res;
int main()
{
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // save cin,cout Time ;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
    
        cin>>a[i];
        b[i]=a[i]+c;// use b[N] Array storage ( Corresponding ) The big C Value 
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
    
       int k=lower_bound(a+1,a+n+1,b[i])-a;// Returns the first greater than or equal to b[i] Of a Index of the array 
       int kk=upper_bound(a+1,a+n+1,b[i])-a;// Return is greater than the 
       res+=kk-k;// because upper_bound Returns a subscript greater than , So there's no need to add 1

    }
    cout<<res<<endl;
    return 0;
}

Double pointer

The concrete realization is , We maintain two endpoints kk , k, Every time kk Move right to a[kk] - a[i] <= c Next to the last position of ,k Move right to meet a[k] - a[l] < c Last .
in other words , If at this time a[kk] - a[i] == c && a[k] - a[i] == c, The middle paragraph must meet the conditions , We let res += kk - k that will do .

#include <bits/stdc++.h>
using namespace std;
int const N=200010;
typedef long long ll;
int a[N],n,c;
ll res;
int main()
{
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     // save cin,cout Time ;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    int kk=2,k=2;
    for(int i=1;i<=n;i++)
    {
    
       while(kk<=n&&a[kk]-a[i]<=c)
        kk++; // Because it's orderly , Next time look for kk Start ; Reduce unnecessary enumeration 
       while(k<=n&&a[k]-a[i]<c)
        k++;
       if(a[kk-1]-a[i]==c&&a[k]-a[i]==c)
        res+=kk-k;
    }
    cout<<res<<endl;
    return 0;
}

MAP Time complexity O(n)

map Usage Summary

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map> //map The header file ;
using namespace std;
typedef long long ll;
int const N=2e5+10;
int n,c,a[N],b[N];
ll res;
map<int,int> mp;//key-value; Establish a number to occurrence mapping  map<a[i],times>
int main()
{
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // save cin,cout Time ;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
    
        cin>>a[i];
        mp[a[i]]++;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
    
      res+=mp[a[i]+c];
    }
    cout<<res<<endl;
    return 0;
}