二分:牛可乐和魔法封印

牛可乐和魔法封印
二分板子
真是丑陋, 写这么长
ac代码:

#include<bits/stdc++.h>
using namespace std;
//偷懒都是要还的
//刷题慢也没办法
//菜就多练

int num[100005];
int n ;

int first_bigger(int y)//返回从右往左第一个小于等于y的数的坐标
{
    int i = 0;
    int j = n-1;
    int mid;
    while(i<j)
    {
        mid = (i+j+1)/2;
        //细节 1 2 3 3 4 5 6 7 8 9 10
        //关于边界条件的确定
        if(num[mid]<=y)//考虑3 5 x= 6
        {
           i = mid;
        }
        else//num[mid]>y
        {
            j = mid - 1;//此时已知mid不合要求, 所以跳过
        }
    }
    if(i>j||num[i]>y) return -1;
    else return i;
}

int first_smaller(int x)//返回从左往右第一个大于等于x的数的坐标
{//没关系, 相信自己, 一定能写出来
    int i = 0;
    int j = n-1;
    int mid;
    while(i<j)
    {
        mid = (i+j)/2;//为什么?考虑 3 5, 如果(i+j+1)/2会死循环
        //细节 1 2 3 3 4 5 6 7 8 9
        //关于边界条件的确定
        if(num[mid]>=x)
        {
            j = mid;
        }
        else//num[mid]<x
        {
            i = mid+1;
        }
    }
    if(num[i]<x) return -1;
    else return i;
}

int main()
{
    //vector<int>num(n+1);
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        cin>>num[i];
    }
    int q;
    cin>>q;
    int x, y;
    for(int i = 0; i<q; i++)
    {
        cin>>x>>y;
        //思路有点混乱
        int l = first_smaller(x), r = first_bigger(y);
        if(l==-1||r==-1) cout<<'0'<<'\n';
        else cout<<max(r-l+1, 0)<<'\n';
    }
    return 0;
}#include<bits/stdc++.h>
using namespace std;
//偷懒都是要还的
//刷题慢也没办法
//菜就多练

int num[100005];
int n ;

int first_bigger(int y)//返回从右往左第一个小于等于y的数的坐标
{
    int i = 0;
    int j = n-1;
    int mid;
    while(i<j)
    {
        mid = (i+j+1)/2;
        //细节 1 2 3 3 4 5 6 7 8 9 10
        //关于边界条件的确定
        if(num[mid]<=y)//考虑3 5 x= 6
        {
           i = mid;
        }
        else//num[mid]>y
        {
            j = mid - 1;//此时已知mid不合要求, 所以跳过
        }
    }
    if(i>j||num[i]>y) return -1;
    else return i;
}

int first_smaller(int x)//返回从左往右第一个大于等于x的数的坐标
{//没关系, 相信自己, 一定能写出来
    int i = 0;
    int j = n-1;
    int mid;
    while(i<j)
    {
        mid = (i+j)/2;//为什么?考虑 3 5, 如果(i+j+1)/2会死循环
        //细节 1 2 3 3 4 5 6 7 8 9
        //关于边界条件的确定
        if(num[mid]>=x)
        {
            j = mid;
        }
        else//num[mid]<x
        {
            i = mid+1;
        }
    }
    if(num[i]<x) return -1;
    else return i;
}

int main()
{
    //vector<int>num(n+1);
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        cin>>num[i];
    }
    int q;
    cin>>q;
    int x, y;
    for(int i = 0; i<q; i++)
    {
        cin>>x>>y;
        //思路有点混乱
        int l = first_smaller(x), r = first_bigger(y);
        if(l==-1||r==-1) cout<<'0'<<'\n';
        else cout<<max(r-l+1, 0)<<'\n';
    }
    return 0;
}