← 返回题目列表

Codeforces · 1746/F

F. 风绘

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

您有一个由 $$$n$$$ 正整数组成的数组 $$$a$$$,并且您必须处理以下类型的 $$$q$$$ 查询:

- $$$1$$$ $$$i$$$ $$$x$$$: 将 $$$a_{i}$$$ 更改为 $$$x$$$,
- $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$:检查子数组 $$$a_{l}, a_{l+1}, \ldots a_{r}$$$ 中每个正整数的出现次数是否是 $$$k$$$ 的倍数(检查示例以更好地理解)。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n , q \le 3 \cdot 10^5$$$)、$$$a$$$ 的长度和查询次数。

下一行包含 $$$n$$$ 整数 $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$1 \le a_{i} \le 10^9$$$) — $$$a$$$ 的元素。

接下来的 $$$q$$$ 行描述一个查询。它具有以下形式之一。

- $$$1$$$ $$$i$$$ $$$x$$$, ($$$1 \le i \le n$$$ , $$$1 \le x \le 10^9$$$), 或
- $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$, ($$$1 \le l \le r \le n$$$ , $$$1 \le k \le n$$$)。

输出

对于第二类型的每个查询,如果查询的答案为是,则打印“YES”,否则打印“NO”。

示例

输入 #1

10 8
1234 2 3 3 2 1 1 2 3 4
2 1 6 2
1 1 1
2 1 6 2
2 1 9 2
1 10 5
2 1 9 3
1 3 5
2 3 10 2

输出 #1

NO
YES
NO
YES
YES

注意

在第一个查询中,请求的子数组是$$$[1234, 2, 3, 3, 2, 1]$$$,显然$$$1$$$出现的次数不能被$$$k = 2$$$整除。所以答案是“不”。

在第三个查询中,请求的子数组为$$$[1, 2, 3, 3, 2, 1]$$$,可以看出该子数组中每个整数出现的次数可以被$$$k = 2$$$整除。所以答案是“是”。

在第六个查询中,请求的子数组为$$$[1, 2, 3, 3, 2, 1, 1, 2, 3]$$$,可以看出该子数组中每个整数出现的次数可以被$$$k = 3$$$整除。所以答案是“是”。