P1102 A-B 数对（加深对lower_bound 和upper_bound的理解）

妖狐艹你老母 2022-11-11 06:17 65阅读 0赞

[传送门][Link 1]

直接暴力，两个for循环， 2 ∗ 1 0 5 2\*10^5 2∗105爆炸  
2021/3/20  
疑问：`ans += ((upper_bound(a+1,a+n+1,a[i]+c)-a)-(lower_bound(a+1,a+n+1,a[i]+c)-a));`  
c = 1  
假设1 1 2 2 3  
那么对于第一个1来说有两个2成立，用上式来套，成立吗？这需要深层次来理解lower\_bound() 和upper\_bound()  
[  
点击理解][Link 2]

//#include<bits/stdc++.h>
    #include <stdio.h>
    #include <iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<vector>
    #include<queue>
    #define ll long long
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    #define scf(x) scanf("%lld",&x)
    #define prf(x) printf("%lld\n",x)
    #define deprf(x) printf("[%lld]\n",x)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define inf 2147483647
    const int mod=1e9+7;
    const int maxn=1e6+7;
    using namespace std;
    ll a[maxn];
    
    int read(){ //快读
        int x=0,f=1;
        char c=getchar();
        while(c<'0'||c>'9'){ 
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){ 
            x=x*10+c-'0';
            c=getchar();
        }
        return x*f;
    }
    
    
    
    int main()
    { 
        ios;
        ll n=read(),c=read();
        rep(i,1,n){ 
            a[i] = read();
        }
        sort(a+1,a+n+1);
        ll ans =0;
        rep(i,1,n){ 
            ans += ((upper_bound(a+1,a+n+1,a[i]+c)-a)-(lower_bound(a+1,a+n+1,a[i]+c)-a));
        }
        cout << ans;
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1102
[Link 2]: https://blog.csdn.net/luker6/article/details/115025742