【二分—STL】lower

目录

• • • 一、基本用法：
    • 二、具体到题目中如何应用
    • • • 1、数的范围
        • 2、递增三元组
        • 3、���组元素的目标和

          一、基本用法：

          lower_bound() 用于二分查找区间内第一个 大于等于某值(>= x) 的迭代器位置

          upper_bound() 用于二分查找区间内第一个 大于某值(> x) 的迭代器位置

          函数前两个参数分别是已被排序的序列的起始迭代器位置和结束迭代器位置，

          将要被查询的范围为[ first, last )，是一个左闭右开区间的范围。

          第三个参数则是需要搜寻的元素的值。最后返回查询成功的迭代器的地址。

          搜索的序列当中若无合法答案返回 last 迭代器地址

          注意点：

          返回的是地址，不是那个要查找的数的下标。所以就注定了在这个函数的后边就要减去这个数组的首地址，即这个数组的数组名。只有这样才代表那个要查找的数字的下标

          若无合法答案：返回的是[first, last)的last

          二、具体到题目中如何应用

          1、数的范围

          AC代码：

          思路分析：

          这道题要分别找到区间第一个k和最后一个k。

          方法是用lower_bound()函数找到第一个>=k的下标x1，这是第一个k

          用upper_bound()函数找到第一个>k的下标，并-1得到x2，这是最后一个k

          特判一下：如果不存在，输出-1 -1。如果存在，输出x1, x2。

          #include using namespace std;int n,q,k,x1,x2,t;int a[100010];int main(){    cin >> n >> q;    for(int i = 0;i > a[i];    }    while(q--){        cin >> k;        x1 = lower_bound(a,a + n,k) - a;        x2 = upper_bound(a,a + n,k) - a - 1;        if(x1 == x2 + 1)        cout     scanf("%d", &n);    for (int i = 1; i         //直接用STL中的两个二分函数解决        lld x = ( lower_bound(a + 1, a + 1 + n, b[i]) - a ) - 1;             //在数组a中找比b[i]小的数        lld y = n - ( upper_bound( c + 1, c + 1 + n, b[i]) - c ) + 1;         //在数组c中找比b[i]大的数        sum += x * y;    }    printf("%lld", sum);    return 0;}    int n, m, x;    cin n  m  x;    for (int i = 0; i