Задача №113771. Машинное обучение
На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из n чисел.
В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число b1 встречается k1 раз, b2 — k2 раз, и т.д. Тогда равномерностью массива называется такое минимальное целое число c ≥ 1, что c ≠ ki для любого i.
В рамках вашего исследования вы хотите последовательно проделать q операций.
- Операция ti = 1, li, ri задаёт запрос исследования. Необходимо вывести равномерность массива, состоящего из элементов на позициях от li до ri включительно.
- Операция ti = 2, pi, xi задаёт запрос уточнения данных. Начиная с этого момента времени pi-му элементу массива присваивается значения xi.
Первая строка содержит n и q (1 ≤ n, q ≤ 100 000) — размер массива и число запросов соответственно.
Во второй строке записаны ровно n чисел — a1, a2, ..., an (1 ≤ ai ≤ 109).
Каждая из оставшихся q строк задаёт очередной запрос.
Запрос первого типа задаётся тремя числами ti = 1, li, ri, где 1 ≤ li ≤ ri ≤ n — границы соответствующего отрезка.
Запрос второго типа задаётся тремя числами ti = 2, pi, xi, где 1 ≤ pi ≤ n — позиция в которой нужно заменить число, а 1 ≤ xi ≤ 109 — его новое значение
Для каждого запроса первого типа выведите одно число — равномерность соответствующего отрезка массива.
Первый запрос состоит из ровно одного элемента — 1. Минимальное подходящее c = 2.
Отрезок второго запроса состоит из четырёх 2, одной 3 и двух 1. Минимальное подходящее c = 3.
Отрезок четвёртого запроса состоит из трёх 1, трёх 2 и одной 3. Минимальное подходящее c = 2.
- Подзадача 0 (0 баллов) тест из условия.
- Подзадача 1 (10 баллов) \(n, q \le 100, a_i, x_i \le 100 \). Необходимые подгруппы: 0.
- Подзадача 2 (10 баллов) \(n, q \le 5000, a_i, x_i \le 2500\). Необходимые подгруппы: 0-1.
- Подзадача 3 (10 баллов) \(n, q \le 5000 \). Необходимые подгруппы: 0-2.
- Подзадача 4 (20 баллов) \(a_i, x_i \le 50 \). Необходимые подгруппы: 0.
- Подзадача 5 (25 баллов) \(a_i, x_i \le 2500 \). Необходимые подгруппы: 0-2, 4.
- Подзадача 6 (25 баллов) без дополнительных ограничений. Необходимые подгруппы: 0-5.
10 4 1 2 3 1 1 2 2 2 9 9 1 1 1 1 2 8 2 7 1 1 2 8
2 3 2