D. Vitya and Strange Lesson

Codeforces

IDCF842D

Time2000ms

Memory256MB

Difficulty—

binary searchdata structures

English · Original

Chinese · Translation

Formal · Original

Today at the lesson Vitya learned a very interesting function — _mex_. _Mex_ of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, _mex_(\[4, 33, 0, 1, 1, 5\]) = 2 and _mex_(\[1, 2, 3\]) = 0. Vitya quickly understood all tasks of the teacher, but can you do the same? You are given an array consisting of _n_ non-negative integers, and _m_ queries. Each query is characterized by one number _x_ and consists of the following consecutive steps: * Perform the bitwise addition operation modulo 2 (_xor_) of each array element with the number _x_. * Find _mex_ of the resulting array. _Note that after each query the array changes._ ## Input First line contains two integer numbers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 3·105) — number of elements in array and number of queries. Next line contains _n_ integer numbers _a__i_ (0 ≤ _a__i_ ≤ 3·105) — elements of then array. Each of next _m_ lines contains query — one integer number _x_ (0 ≤ _x_ ≤ 3·105). ## Output For each query print the answer on a separate line. [samples]

今天在课堂上，Vitya 学习了一个非常有趣的函数——_mex_。一个数列的 _mex_ 是指该序列中不存在的最小非负整数。例如，#cf_span[mex([4, 33, 0, 1, 1, 5]) = 2] 和 #cf_span[mex([1, 2, 3]) = 0]。 Vitya 迅速理解了老师的所有题目，但你能做到吗？给你一个包含 #cf_span[n] 个非负整数的数组，以及 #cf_span[m] 个查询。每个查询由一个数字 #cf_span[x] 描述，并按以下连续步骤进行： _注意：每次查询后数组会发生变化。_ 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和查询个数。下一行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[0 ≤ ai ≤ 3·105]）——数组的元素。接下来的 #cf_span[m] 行每行包含一个查询——一个整数 #cf_span[x]（#cf_span[0 ≤ x ≤ 3·105]）。对于每个查询，请在单独一行输出答案。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和查询个数。下一行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[0 ≤ ai ≤ 3·105]）——数组的元素。每行接下来的 #cf_span[m] 行包含一个查询——一个整数 #cf_span[x]（#cf_span[0 ≤ x ≤ 3·105]）。 ## Output 对于每个查询，请在单独一行输出答案。 [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of array elements and queries, respectively. Let $ A = (a_1, a_2, \dots, a_n) $ be the initial array of non-negative integers. Let $ x_1, x_2, \dots, x_m \in \mathbb{Z}_{\ge 0} $ be the sequence of query values. For each query $ j \in \{1, \dots, m\} $: - Let $ A^{(j)} $ denote the array state before the $ j $-th query. - Let $ \text{mex}(S) = \min \left( \mathbb{Z}_{\ge 0} \setminus S \right) $ for any finite set $ S \subseteq \mathbb{Z}_{\ge 0} $. - The query updates the array: $ A^{(j+1)} = A^{(j)} \setminus \{x_j\} $ if $ x_j \in A^{(j)} $, otherwise $ A^{(j+1)} = A^{(j)} $. **Constraints** 1. $ 1 \le n, m \le 3 \cdot 10^5 $ 2. $ 0 \le a_i \le 3 \cdot 10^5 $ for all $ i \in \{1, \dots, n\} $ 3. $ 0 \le x_j \le 3 \cdot 10^5 $ for all $ j \in \{1, \dots, m\} $ **Objective** For each query $ j \in \{1, \dots, m\} $, compute and output: $$ \text{mex}\left( A^{(j)} \right) $$ where $ A^{(1)} = A $, and $ A^{(j)} $ is updated by removing one occurrence of $ x_{j-1} $ from $ A^{(j-1)} $ for $ j \ge 2 $.

Samples

Input #1

Output #1

1
0

Input #2

Output #2

2
0
0

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Vitya and Strange Lesson",
    "description": {
      "content": "Today at the lesson Vitya learned a very interesting function — _mex_. _Mex_ of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, _m",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF842D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Today at the lesson Vitya learned a very interesting function — _mex_. _Mex_ of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, _m...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "今天在课堂上，Vitya 学习了一个非常有趣的函数——_mex_。一个数列的 _mex_ 是指该序列中不存在的最小非负整数。例如，#cf_span[mex([4, 33, 0, 1, 1, 5]) = 2] 和 #cf_span[mex([1, 2, 3]) = 0]。\n\nVitya 迅速理解了老师的所有题目，但你能做到吗？\n\n给你一个包含 #cf_span[n] 个非负整数的数组，以及 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of array elements and queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial array of non-negative integers.  \nLet...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments