← 返回题目列表

Codeforces · 1476/G

G. 最小差异

中文机器翻译题面 查看原题

给定一个整数数组 $$$a$$$,大小为 $$$n$$$。

您必须执行 $$$m$$$ 查询。每个查询都有两种类型之一:

- "$$$1$$$ $$$l$$$ $$$r$$$ $$$k$$$" — 计算最小值 $$$dif$$$,使得存在 $$$k$$$ 不同的整数 $$$x_1, x_2, \dots, x_k$$$ 使得 $$$cnt_i > 0$$$ (对于每个 $$$i \in [1, k]$$$) 和 $$$|cnt_i - cnt_j| \le diff$$$ (对于每个 $$$i \in [1, k], j \in [1, k]$$$),其中 $$$cnt_i$$$ 是 $$$x_i$$$ 在子数组 $$$a[l..r]$$$ 中出现的次数。如果无法选择 $$$k$$$ 整数,请报告;
- "$$$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$$$。

示例

输入 #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