原始题目

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函数。

解题代码

#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（越界了）。