牛可乐和魔法封印
二分板子
真是丑陋, 写这么长
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;
}