Kazaee
Contest: Codeforces Global Round 23
Difficulty rating: 2800
Tags: 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).

Input format:
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$$$).

Output format:
For each query of the second type, if answer of the query is yes, print "YES", otherwise print "NO".

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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".

Example input:
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

Example output:
NO
YES
NO
YES
YES

Editorial:
Step 1:
First of all, we can compress $$$a_{i}$$$'s and $$$x$$$'s (in second type query). so we can assume that all numbers are less than $$$n+q \le 6 \cdot 10^5$$$.
Step 2:
Task: Lets first solve the problem for smaller constrains.
Solution: We can use data structures like fenwick tree or segment tree to count the number of occurrences of each number and check if it's divisible by $$$k$$$ to answer second type query. And we can simply update our data structure after each query of the first type.
So if we use something like fenwick tree, we can handle everything in $$$O((n+q) \cdot n + (n+q) \cdot q \cdot log_{2}(n))$$$.
Step 3:
Task: Obviously we can not use previous step solution for original constrains. In other words, we don't have enough time to check all numbers one by one. How can we do better? Checking them together?!
Solution: It's obviously not a good idea to check all numbers together (checking that sum of their occurrences is divisible by $$$k$$$). So what can we do? What if we check a random subset of numbers?
Step 4:
Task: Assume that $$$S$$$ is a random subset of all numbers, it's obvious that if the answer of the query is "YES" (number of occurrences of every number is divisible by $$$k$$$), the condition holds for $$$S$$$ too (sum of number of occurrences of numbers that belong to $$$S$$$ is divisible by $$$k$$$). What about the opposite? What is the probability that the answer of the query is "NO" and yet sum of occurrences of numbers belonging to $$$S$$$ is divisible by $$$k$$$?
Solution: It's not so hard to prove that the probability is equal to $$$\frac{1}{2}$$$ for $$$k = 2$$$ and it's less than $$$\frac{1}{2}$$$ for $$$k \ge 2$$$. So in general, the probability that a random subset $$$S$$$ leads to a wrong answer is less than or equal to $$$\frac{1}{2}$$$. So if we use something like $$$30$$$ random subsets, the probability will be less than $$$\frac{1}{2^30}$$$ which is reasonable for problem constrains and we can use this random method to solve the task.