查找不重复元素出现的位置

Luogu

IDLGB2166

Time1000ms

Memory512MB

DifficultyP2

二分

输入 $n$ 个不超过 $10^9$ 的**严格递增**的正整数组成的数列 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中出现的下标。如果序列中不包含该数字，请输出 $-1$ 。注意：下标从 $1$ 开始。 ## Input 第一行，包含两个正整数 $n$ 和 $m$，分别表示数列的长度和询问的次数。第二行，包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。接下来 $m$ 行，每行包含一个正整数 $q$，表示一次询问。 ## Output 输出共 $m$ 行。对于每次询问，如果数字 $q$ 存在于数列中，则输出它在数列中的下标；如果不存在，则输出 $-1$。 [samples] ## Note 对于所有测试点，保证： * $1 \leq n, m \leq 10^6$ * $1 \leq a_i, q \leq 10^9$ * 对于 $1 \leq i < n$，保证 $a_i < a_{i+1}$。本题输入输出量较大，请使用较快的 IO 方式。

Samples

Input #1

5 4
10 20 30 40 50
30
10
50
35

Output #1

API Response (JSON)

{
  "problem": {
    "name": "查找不重复元素出现的位置",
    "description": {
      "content": "输入 $n$ 个不超过 $10^9$ 的**严格递增**的正整数组成的数列 $a_1,a_2,\\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中出现的下标。如果序列中不包含该数字，请输出 $-1$ 。 注意：下标从 $1$ 开始。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB2166"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "输入 $n$ 个不超过 $10^9$ 的**严格递增**的正整数组成的数列 $a_1,a_2,\\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中出现的下标。如果序列中不包含该数字，请输出 $-1$ 。\n\n注意：下标从 $1$ 开始。\n\n## Input\n\n第一行，包含两个正整数 $n$ 和 $m$，分别表示数列的长度和询问的次数。\n\n第...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments