CF1476G Minimum Difference

给定一个大小为 $n$ 的整数数组 $a$。 你需要进行 $m$ 次操作。每次操作有两种类型： - “$1$ $l$ $r$ $k$”——计算最小的 $dif$，使得存在 $k$ 个互不相同的整数 $x_1, x_2, \dots, x_k$，满足对于每个 $i \in [1, k]$，都有 $cnt_i > 0$，且对于任意 $i, j \in [1, k]$，都有 $|cnt_i - cnt_j| \le dif$，其中 $cnt_i$ 表示 $x_i$ 在子数组 $a[l..r]$ 中出现的次数。如果无法选择 $k$ 个不同的整数，输出 $-1$。 - “$2$ $p$ $x$”——将 $a_p$ 赋值为 $x$。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^5$），分别表示数组 $a$ 的大小和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）。 接下来的 $m$ 行，每行表示一次操作，格式如下： - “$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$） 保证至少有一次第一类操作。

对于每个第一类操作，输出满足条件的最小 $dif$，如果无法选择 $k$ 个不同的整数，则输出 $-1$。

由 ChatGPT 4.1 翻译