【CodeForces-600B】解题报告(二分,stl二分函数应用)

原始题目

B. Queries about less or equal elements

  • time limit per test2 seconds
  • memory limit per test256 megabytes
  • input:standard input
  • output:standard output

You are given two arrays of integers $a$ and $b$. For each element of the second array $b_j$ you should find the number of elements in array $a$ that are less than or equal to the value $b_j$.

Input

The first line contains two integers $n, m (1 ≤ n, m ≤ 2·10^5)$ — the sizes of arrays $a$ and $b$.

The second line contains n integers — the elements of array $a ( - 10^9 ≤ ai ≤ 10^9)$.

The third line contains m integers — the elements of array $b ( - 10^9 ≤ bj ≤ 10^9)$.

Output

Print m integers, separated by spaces: the j-th of which is equal to the number of such elements in array $a$ that are less than or equal to the value $b_j$.

Examples

input

5 4
1 3 5 7 9
6 4 2 8

output

3 2 1 4

input

5 5
1 2 1 2 5
3 1 4 1 5

output

4 2 4 2 5

题目大意

给定$a,b$两个数列,对$b$中每一项$b_i$,求$a$中小于等于$b_i$的项的个数。

解题思路

  • 排序后二分,由于寻找小于等于$b_i$的个数,使用stl里的upper_bound函数。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) (int(x).size())
typedef long long ll;
typedef vector <int> vi;
typedef pair<int,int> pii;
const int maxn=2e5+5;

vector <ll> va,vb;

ll pa,pb;
ll n,m;
int main(){
while(~scanf("%lld%lld",&n,&m)){
va.clear();
for(ll i=1;i<=n;i++){
scanf("%lld",&pa);
va.pb(pa);
}
sort(all(va));

for(ll i=1;i<=m;i++){
if(i!=1) printf(" ");
scanf("%lld",&pb);
if(pb>=*(--va.end())) printf("%lld",n);
else if(pb<*(va.begin())) printf("0");
else{

ll c=upper_bound(all(va),pb)-va.begin();
printf("%lld",c);
}
}
printf("\n");
}
}

收获与反思

  • 二分思想练习
  • upper_bound 与 lower_bound 使用的一些注意

    1. 前提:
      • 数组是一个非降序列
    2. 参数:

      一个数组元素的地址(或者数组名来表示这个数组的首地址,用来表示这个数组的开头比较的元素的地址,不一定要是首地址,只是用于比较的“首”地址),

      一个数组元素的地址(对应的这个数组里边任意一个元素的地址,表示这个二分里边的比较的”结尾’地址),

      一个你要二分查找的那个数。

    3. 返回值:

      • 是地址,不是指那个要查找的数的下标,所以就注定了在这个函数的后边就要减去一个尾巴,那就是这个数组用来比较的头地址。
      • upper_bound 返回的是键值为i的元素可以插入的最后一个位置(上界)
      • lowe_bound 返回的是键值为i的元素可以插入的位置的第一个位置(下界)。
      • 举例在升序的set里面:

        set里没有元素i的时候,两个元素的返回值是一样的。
        1 2 4 5 这个序列,upp(3)和low(3)都返回位置2(下标)

        如果只有一个元素i,low返回那个元素的位置,而upp返回那个元素的位置的后一个位置。
        1 2 4 5 这个序列upp(2)返回下标2而low(2)返回下标1

        多个元素i,low返回那个元素的位置,upp返回那多个元素中的最后一个的后一个位置。
        1 2 2 4 5 这个序列 upp(2)返回下标3的位置,low(2)返回下标1的位置。

    4. 不存在时的情况:
      • 特别注意:在一个升序的容器里,如果所有元素都大于i则,upp和low都返回begin。都小于i则返回end(越界了)。