题解 CF600B 【Queries about less or equal elements】
TRZ_2007
2020-12-23 17:54:15
**[题解 CF600B 【Queries about less or equal elements】](https://www.luogu.com.cn/problem/CF600B)**
# Solution
观察一下数据，发现 $1\le n,m\le 2\times 10 ^ 5$，因此 $\mathcal{O(n\times m)}$，的暴力做法明显不会过。因此我们考虑**二分**。
~~如果有同学不会二分呢？~~
那么……就讲一下吧……
看这个图：
当然，数据要有序。
我们现在取一下这组数据的中点，发现这个数字大于我们的 mid ，那么在 mid 左边的数字都不可能会是解，因为它们都比 mid 小。继续，
发现比 mid 大，那么答案在左边，但是区间长度为0了，输出答案就是数字 7 的位置。
但是，我们要的答案不是 7 的位置，而是 5 的位置，怎么办？ 减一就好了。
其实用函数也可以，就是比较慢，要吸氧。
听说平衡树或者树状数组也可以过，这里就不讲了。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
struct node {
int val,size;
int lson,rson;
}tree[N * 4];
int n,m,l,r;
int a[N],key,ans;
inline int find(int key) {
l = 1;r = n + 1;
int cnt = 0;
while(l <= r) {
// cout << l << " " << r << "\n";
int mid = (l + r) >> 1;
if(a[mid] > key) {
cnt = mid;
r = mid - 1;
}
else l = mid + 1;
}
return cnt;
}
int main() {
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;i++) {
scanf("%d",&a[i]);
}
sort(a + 1,a + n + 1);
a[n + 1] = INT_MAX; //定义一个哨兵为 inf 以防关键字太大了。
for(int i = 1;i <= m;i++) {
scanf("%d",&key);
ans = find(key);
printf("%d ",ans - 1);
}
return 0;
}
```