English · Original
Chinese · Translation
Formal · Original
_You come home and fell some unpleasant smell. Where is it coming from?_
You are given an array _a_. You have to answer the following queries:
1. You are given two integers _l_ and _r_. Let _c__i_ be the number of occurrences of _i_ in _a__l_: _r_, where _a__l_: _r_ is the subarray of _a_ from _l_\-th element to _r_\-th inclusive. Find the **Mex** of {_c_0, _c_1, ..., _c_109}
2. You are given two integers _p_ to _x_. Change _a__p_ to _x_.
The **Mex** of a multiset of numbers is the smallest non-negative integer **not in** the set.
Note that in this problem all elements of _a_ are positive, which means that _c_0 = 0 and 0 is never the answer for the query of the second type.
## Input
The first line of input contains two integers _n_ and _q_ (1 ≤ _n_, _q_ ≤ 100 000) — the length of the array and the number of queries respectively.
The second line of input contains _n_ integers — _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109).
Each of the next _q_ lines describes a single query.
The first type of query is described by three integers _t__i_ = 1, _l__i_, _r__i_, where 1 ≤ _l__i_ ≤ _r__i_ ≤ _n_ — the bounds of the subarray.
The second type of query is described by three integers _t__i_ = 2, _p__i_, _x__i_, where 1 ≤ _p__i_ ≤ _n_ is the index of the element, which must be changed and 1 ≤ _x__i_ ≤ 109 is the new value.
## Output
For each query of the first type output a single integer — the **Mex** of {_c_0, _c_1, ..., _c_109}.
[samples]
## Note
The subarray of the first query consists of the single element — 1.
The subarray of the second query consists of four 2s, one 3 and two 1s.
The subarray of the fourth query consists of three 1s, three 2s and one 3.
_你回到家，闻到一股难闻的气味。它从哪里来的？_
给你一个数组 #cf_span[a]。你需要回答以下查询：
一个多重集合的 *Mex* 是不在该集合中的最小非负整数。
注意，在本题中，数组 #cf_span[a] 的所有元素均为正数，这意味着 #cf_span[c0] = 0，且对于第二类查询，#cf_span[0] 永远不会是答案。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 100 000]) —— 分别表示数组长度和查询数量。
第二行包含 #cf_span[n] 个整数 —— #cf_span[a1], #cf_span[a2], #cf_span[...], #cf_span[an] (#cf_span[1 ≤ ai ≤ 109])。
接下来的 #cf_span[q] 行每行描述一个查询。
第一类查询由三个整数 #cf_span[ti = 1], #cf_span[li], #cf_span[ri] 描述，其中 #cf_span[1 ≤ li ≤ ri ≤ n] —— 子数组的边界。
第二类查询由三个整数 #cf_span[ti = 2], #cf_span[pi], #cf_span[xi] 描述，其中 #cf_span[1 ≤ pi ≤ n] 是待修改元素的索引，#cf_span[1 ≤ xi ≤ 109] 是新值。
对于每个第一类查询，输出一个整数 —— #cf_span[{c0, c1, ..., c109}] 的 *Mex*。
第一个查询的子数组仅包含一个元素 —— #cf_span[1]。
第二个查询的子数组包含四个 #cf_span[2]、一个 #cf_span[3] 和两个 #cf_span[1]。
第四个查询的子数组包含三个 #cf_span[1]、三个 #cf_span[2] 和一个 #cf_span[3]。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 100 000]) —— 分别表示数组长度和查询数量。第二行包含 #cf_span[n] 个整数 —— #cf_span[a1], #cf_span[a2], #cf_span[...], #cf_span[an] (#cf_span[1 ≤ ai ≤ 109])。接下来的 #cf_span[q] 行每行描述一个查询。第一类查询由三个整数 #cf_span[ti = 1], #cf_span[li], #cf_span[ri] 描述，其中 #cf_span[1 ≤ li ≤ ri ≤ n] —— 子数组的边界。第二类查询由三个整数 #cf_span[ti = 2], #cf_span[pi], #cf_span[xi] 描述，其中 #cf_span[1 ≤ pi ≤ n] 是待修改元素的索引，#cf_span[1 ≤ xi ≤ 109] 是新值。
## Output
对于每个第一类查询，输出一个整数 —— #cf_span[{c0, c1, ..., c109}] 的 *Mex*。
[samples]
## Note
第一个查询的子数组仅包含一个元素 —— #cf_span[1]。第二个查询的子数组包含四个 #cf_span[2]、一个 #cf_span[3] 和两个 #cf_span[1]。第四个查询的子数组包含三个 #cf_span[1]、三个 #cf_span[2] 和一个 #cf_span[3]。
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the length of the array and number of queries, respectively.
Let $ A = (a_1, a_2, \dots, a_n) $ be an array of positive integers, where $ a_i \in [1, 10^9] $.
**Constraints**
1. $ 1 \leq n, q \leq 100{,}000 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
3. For each query:
- Type 1: $ t_i = 1 $, $ 1 \leq l_i \leq r_i \leq n $ — query Mex over subarray $ A[l_i:r_i] $
- Type 2: $ t_i = 2 $, $ 1 \leq p_i \leq n $, $ 1 \leq x_i \leq 10^9 $ — update $ a_{p_i} \gets x_i $
**Objective**
For each query of type 1, compute the **Mex** of the multiset $ S = \{ a_j \mid l_i \leq j \leq r_i \} $, defined as:
$$
\mathrm{Mex}(S) = \min \left( \mathbb{Z}_{\geq 0} \setminus S \right)
$$
(Note: Since all $ a_i \geq 1 $, $ 0 \notin S $, so $ \mathrm{Mex}(S) = 0 $ if $ 0 \notin S $, otherwise the smallest missing non-negative integer.)
API Response (JSON)
{
"problem": {
"name": "F. Machine Learning",
"description": {
"content": "_You come home and fell some unpleasant smell. Where is it coming from?_ You are given an array _a_. You have to answer the following queries: 1. You are given two integers _l_ and _r_. Let _c__i_ ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF940F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_You come home and fell some unpleasant smell. Where is it coming from?_\n\nYou are given an array _a_. You have to answer the following queries:\n\n1. You are given two integers _l_ and _r_. Let _c__i_ ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_你回到家，闻到一股难闻的气味。它从哪里来的？_\n\n给你一个数组 #cf_span[a]。你需要回答以下查询：\n\n一个多重集合的 *Mex* 是不在该集合中的最小非负整数。\n\n注意，在本题中，数组 #cf_span[a] 的所有元素均为正数，这意味着 #cf_span[c0] = 0，且对于第二类查询，#cf_span[0] 永远不会是答案。\n\n输入的第一行包含两个整数 #cf_span[n] 和...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the length of the array and number of queries, respectively. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be an array of positive integers, where $ a_i \\...",
"is_translate": false,
"language": "Formal"
}
]
}