Description

qw喜歡上了一個美麗的女孩，并勇敢向她表白。但女神喜歡算法厲害的男生，便給他出了一道題：
給定包含n 個整數的數列a 和m 個詢問，每個詢問包含兩個整數L ，R ，對于每一個詢問，要求輸出數列中有多少個數ai ，滿足L≤a2i≤R ，即有多少個數平方后取值范圍在[L,R] 之間。
單身二十年的qw非常想談戀愛，你能幫幫他嗎？

Input

多組數據。
第一行給出數據組數T（1≤T≤50 ）
每組數據首先給定兩個整數n ,m ，表示數列中數的個數和詢問個數。（1≤n,m≤50000 ）
隨后一行給出n 個整數 a1,a2,a3...an （1≤ai≤1e9 ）
隨后m 行，每行兩個整數 L , R ，表示當前詢問的數值范圍區間。（1≤L≤R≤1e9 ）

Output

對于每個詢問，單獨輸出一行，包含一個整數，表示數列中滿足條件的數個數

Sample Input

1

5 3

1 2 3 4 5

1 4

4 9

1 25

Sample Output

2

2

5

題解：

二分搜啊

開long long?

排序

二分搜搜

然后就哦了

#include <iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; int t,n,m; long long a[50000+100],temp,l,r; int main() { scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&temp);a[i]=temp*temp;}sort(a+1,a+n+1);for(int i=1;i<=m;i++){scanf("%lld%lld",&l,&r);printf("%d\n",upper_bound(a+1,a+n+1,r)-lower_bound(a+1,a+n+1,l));} }return 0; }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的qw的表白的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。