CF940F Machine Learning

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.

N/A

N/A

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 $ .