Machine Learning

题意翻译

给你一个数组$\{a_i\}$支持两种操作： 1、查询区间$[l,r]$中每个数字出现次数的mex。 2、单点修改某一个位置的值。 mex指的是一些数字中最小的未出现的自然数。值得注意的是，区间$[l,r]$总有数字是没有出现过的，所以答案不可能为0. $n,Q\le10^5$ 感谢@租酥雨 提供的翻译

题目描述

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_{10^{9}}} $ 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.

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ q $ ( $ 1<=n,q<=100000 $ ) — 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}<=10^{9} $ ). 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}<=10^{9} $ is the new value.

输出格式

For each query of the first type output a single integer — the Mex of $ {c_{0},c_{1},...,c_{10^{9}}} $ .

输入输出样例

输入样例 #1

10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8

输出样例 #1

2
3
2

说明

The subarray of the first query consists of the single element — $ 1 $ . The subarray of the second query consists of four $ 2 $ s, one $ 3 $ and two $ 1 $ s. The subarray of the fourth query consists of three $ 1 $ s, three $ 2 $ s and one $ 3 $ .