硬核手搓二分题解

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],b[100001],l,r,mid,ans=-1;
int find_first_equal(int i){
    l=1,r=n;
    while(l<=r){
        mid=(l+r)/2;
        if(a[mid]>=b[i]){
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    if(ans==-1)
        return -1;
    else{
        if(a[ans]==b[i])
            return ans;
        else
            return -1;
    }
}
int find_last_equal(int i){
    l=1,r=n;
    while(l<=r){
        mid=(l+r)/2;
        if(a[mid]<=b[i]){
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    if(ans==-1)
        return -1;
    else{
        if(a[ans]==b[i])
            return ans;
        else
            return -1;
    }
}
int upper_bound(int i){
    l=1,r=n;
    while(l<=r){
        mid=(l+r)/2;
        if(a[mid]>b[i]){
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    if(ans==-1)
        return -1;
    else{
        if(a[ans]>b[i])
            return ans;
        else
            return -1;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>b[i];
    for(int i=1;i<=m;i++)
        cout<<find_first_equal(i)<<" "<<find_last_equal(i)<<" "<<upper_bound(i)<<endl;
    return 0;
}