Minimum Difference

题目描述

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

题意翻译

### 题目大意 这是一个关于数组查询的问题。给定一个整数数组 $a$ 和一系列查询操作，每个查询操作可以是计算最小差异值或更新数组中的元素。最小差异值的计算基于子数组中不同整数的出现次数，要求满足一定条件。查询操作的类型和参数会在输入中给出，需要根据查询操作进行相应的处理并输出结果。 ### 输入格式： - 第一行包含两个整数 $n$ 和 $m$，表示数组 $a$ 的大小和查询的数量。 - 第二行包含 $n$ 个整数$a_{1}$，$a_{2}$，$\dots$，$a_{n}$，表示数组 $a$ 的元素。 - 接下来的 $m$ 行，每行包含一个查询操作。每个查询操作有两种类型之一： - `1 l r k`：计算最小值`dif`，使得在子数组 $a[l..r]$ 中存在 $k$ 个不同的整数，满足每个整数出现次数的差的绝对值不超过`dif`。其中 $1 \le l \le r \le n$，$1 \le k \le 10^{5}$。 - `2 p x`：将数组 $a$ 的第 $p$ 个元素赋值为 $x$。其中$1 \le p \le n$，$1 \le x \le 10^{5}$。 ### 输出格式： - 对于每个第一类型的查询，输出满足所有要求条件的最小`dif`值，如果无法选择 $k$ 个不同的整数，则输出 $-1$。每个结果占一行。