题目描述
牛可乐得到了一个长度为 n 且非严格单调递增的序列 a,然而这个序列被 q 层魔法封印了,其中第 i 层封印的问题包含两个整数 xi,yi(xi≤yi),牛可乐必须正确回答序列中大于等于 xi且小于等于 yi 的数字个数才能够解开该层封印。
牛可乐觉得这个问题太难了,于是他想请你帮助他解开序列的 qqq 层封印。
输入描述:
第一行包含一个整数 n(1≤n≤10^5),表示序列的长度。 第二行包含 n 个整数,其中 −10^9≤ai≤10^9。 第三行包含一个整数 q(1≤q≤10^5),代表封印层数。 之后 q 行,每行两个整数 xi,yi(−10^9≤xi≤yi≤10^9),代表该层封印的询问。
输出描述:
对于每层封印,输出一行一个整数,代表在范围内的数字个数。
示例1
输入
5 1 2 3 4 5 3 2 6 1 5 3 3
输出
4 5 1
说明
对于第一层封印,2,3,4,5 在范围内,答案为 4。 对于第二层封印,1,2,3,4,5 在范围内,答案为 5。 对于第三层封印,3在范围内,答案为 1。
示例2
输入
5 1 1 2 3 3 3 1 1 2 3 1 3
输出
2 3 5
思路:
运用STL中的二分函数求解
AC代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,i,x,y,q,a[1000005],ans=0;
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];
}
cin>>q;
while(q--){
cin>>x>>y;
ans=upper_bound(a+1,a+n+1,y)-lower_bound(a+1,a+n+1,x);
cout<<ans<<endl;
}
return 0;
}
标签:yi,10,xi,魔法,整数,----,封印,序列
From: https://blog.csdn.net/2302_80983064/article/details/140691213