/ / 题库 /

「模板」有序序列查找

「模板」有序序列查找

测试数据来自 oistream/1057

背景

这是一道模板题。

  • Idea: 人类
  • Data: oistream
  • Std: oistream
  • 题面: oistream

描述

给定一个整数序列 \(A=<a_1,a_2,\cdots , a_n>\) 和 \(m\) 个整数 \(k_1,k_2,\cdots ,k_m\),求满足 \(k_j=a_i\) 的 \(i\)。

输入格式

第一行,两个整数 \(n,m\)。

第二行,\(n\) 个整数,为 \(A\),以空格分隔。

此后 \(m\) 行,每行一个整数,第 \(i\) 行的整数为 \(k_{i-2}\)。

输出格式

\(m\) 行,每行一个整数。第 \(i\) 行的整数为对 \(k_i\) 所求的值。

样例

输入样例1

5 3
1 2 3 4 5
1
4
5

输出样例1

1
4
5

样例解释

无。

数据规模与约定

对于 \(50\%\) 的数据,\(1\leq m\leq n\leq 10^4\)。

对于 \(80\%\) 的数据,\(1\leq m\leq n\leq 10^5\)。

对于 \(90\%\) 的数据,\(1\leq m\leq 10^5\leq n\leq 10^6\)。

另有 \(10\%\) 的数据,\(1\leq m\leq 5\times 10^5\leq n\leq 10^6\),此部分数据限时 \(2~~\text{s}\)。

对于 \(100\%\) 的数据,对于任意的 \(1\leq i\lt j\leq n\),有 \(0\leq a_i\lt a_j\leq 10^9\),对于任意的 \(1\leq j\leq m\),保证存在 \(1\leq i\leq n\) 使得 \(a_i=k_j\)。

除特殊说明的测试点外,所有测试点均限 \(1~~\text{s},128~~\text{MB}\)。

信息

ID
2530
难度
(无)
分类
二分查找分治 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者