Kazaee

题意翻译

#### 题目描述 给出一个长度为 $n$ 的数组 $a$ 和以下两种操作: - $1\ i\ x$:将 $a_i$ 修改为 $x$。 - $2\ l\ r\ k$:询问在数组区间 $[l, r]$ 内是否每个出现过的正整数的出现次数都是 $k$ 的倍数。(建议参照样例理解)若是则输出 `YES`,若否则输出 `NO`。 #### 输入格式 第一行两个整数 $n$、$q$,表示数组长度和操作数。 第二行 $n$ 个整数,为数组 $a$ 中的元素。(下标从1开始) 之后 $q$ 行,每行一个询问。 #### 输出格式 对于每个操作2,给出相应答案(YES 或 NO)。

题目描述

You have an array $ a $ consisting of $ n $ positive integers and you have to handle $ q $ queries of the following types: - $ 1 $ $ i $ $ x $ : change $ a_{i} $ to $ x $ , - $ 2 $ $ l $ $ r $ $ k $ : check if the number of occurrences of every positive integer in the subarray $ a_{l}, a_{l+1}, \ldots a_{r} $ is a multiple of $ k $ (check the example for better understanding).

输入输出格式

输入格式


The first line of the input contains two integers $ n $ and $ q $ ( $ 1 \le n , q \le 3 \cdot 10^5 $ ), the length of $ a $ and the number of queries. Next line contains $ n $ integers $ a_{1}, a_{2}, \ldots a_{n} $ ( $ 1 \le a_{i} \le 10^9 $ ) — the elements of $ a $ . Each of the next $ q $ lines describes a query. It has one of the following forms. - $ 1 $ $ i $ $ x $ , ( $ 1 \le i \le n $ , $ 1 \le x \le 10^9 $ ), or - $ 2 $ $ l $ $ r $ $ k $ , ( $ 1 \le l \le r \le n $ , $ 1 \le k \le n $ ).

输出格式


For each query of the second type, if answer of the query is yes, print "YES", otherwise print "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

说明

In the first query, requested subarray is $ [1234, 2, 3, 3, 2, 1] $ , and it's obvious that the number of occurrence of $ 1 $ isn't divisible by $ k = 2 $ . So the answer is "NO". In the third query, requested subarray is $ [1, 2, 3, 3, 2, 1] $ , and it can be seen that the number of occurrence of every integer in this sub array is divisible by $ k = 2 $ . So the answer is "YES". In the sixth query, requested subarray is $ [1, 2, 3, 3, 2, 1, 1, 2, 3] $ , and it can be seen that the number of occurrence of every integer in this sub array is divisible by $ k = 3 $ . So the answer is "YES".