LG#P2249. 查找

查找

P2249 【深基13.例1】查找

题目描述

\hspace{15pt}输入 nn 个不超过 10910^9 的单调不降的非负整数 a1,a2,…,ana_1,a_2,\dots,a_n,然后进行 mm 次询问。对于每次询问,给出一个整数 qq,要求输出这个数字在序列中第一次出现的编号;如果没有找到,输出 −1-1。

\hspace{15pt}【名词解释】

∙ \hspace{23pt}\bullet\, 单调不降:对于数组 aa 中从左向右数的第 ii 个元素 aia_i,如果 ai+1a_{i+1} 存在,那么 ai≦ai+1a_i \leqq a_{i+1}。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m \left(1 \leqq n \leqq 10^6;\ 1 \leqq m \leqq 10^5\right)$,分别代表数字个数和询问次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(0 \leqq a_i \leqq 10^9\right)$,代表这些待查询的数字,保证这些数字单调不降。

\hspace{15pt}第三行输入 mm 个整数 $q_1,q_2,\dots,q_m \left(0 \leqq q_i \leqq 10^9\right)$,代表每次询问的数字。

输出格式

\hspace{15pt}在一行上输出 mm 个整数,整数之间使用空格隔开,第 ii 个整数代表 qiq_i 在序列中第一次出现的编号;如果序列中不存在 qiq_i,则该位置输出 −1-1。

测试样例

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
1 2 -1 

数据范围与提示

\hspace{15pt}本题输入输出量较大,请使用较快的 IO 方式。