Minimum Difference

题意翻译

有一个长为 $n$ 的数组，进行 $m$ 次询问，每次为以下两种中的一种： `1 l r k`：给定区间 $[l,r]$，你需要求出最小的 $\text{dif}$，使得能够选出 $k$ 个互不相同的数 $a_1,a_2,\cdots,a_k$，令这些数在区间中的出现次数分别为 $cnt_1,cnt_2,\cdots,cnt_k$（任意 $cnt_i > 0$），则 $\text{dif}$ 为这些 $cnt_i$ 的极差；若无法选出 $k$ 个数，则输出 $-1$. `2 p x`：将位置 $p$ 赋值为 $x$。 输入的所有数值值域 $[1,10^5]$。

题目描述

You are given an integer array $ a $ of size $ n $ . You have to perform $ m $ queries. Each query has one of two types: - " $ 1 $ $ l $ $ r $ $ k $ " — calculate the minimum value $ dif $ such that there are exist $ k $ distinct integers $ x_1, x_2, \dots, x_k $ such that $ cnt_i > 0 $ (for every $ i \in [1, k] $ ) and $ |cnt_i - cnt_j| \le dif $ (for every $ i \in [1, k], j \in [1, k] $ ), where $ cnt_i $ is the number of occurrences of $ x_i $ in the subarray $ a[l..r] $ . If it is impossible to choose $ k $ integers, report it; - " $ 2 $ $ p $ $ x $ " — assign $ a_{p} := x $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 10^5 $ ) — the size of the array $ a $ and the number of queries. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^5 $ ). Next $ m $ lines contain queries (one per line). Each query has one of two types: - " $ 1 $ $ l $ $ r $ $ k $ " ( $ 1 \le l \le r \le n; 1 \le k \le 10^5 $ ) - " $ 2 $ $ p $ $ x $ " ( $ 1 \le p \le n; 1 \le x \le 10^5 $ ). It's guaranteed that there is at least one query of the first type.

输出格式

For each query of the first type, print the minimum value of $ dif $ that satisfies all required conditions, or $ -1 $ if it is impossible to choose $ k $ distinct integers.

输入输出样例

输入样例 #1

12 11
2 1 1 2 1 1 3 2 1 1 3 3
1 2 10 3
1 2 11 3
2 7 2
1 3 9 2
1 1 12 1
1 1 12 4
2 12 4
1 1 12 4
2 1 5
1 3 12 2
1 1 4 3

输出样例 #1

5
4
1
0
-1
5
0
1