F. Kazaee
data structures; hashing; probabilities
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"".
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"".