### PROBLEM LINK:

**Author:** Aniket Marlapalle

**Tester:** Devamanyu Hazarika

**Editorialist:** Aniket Marlapalle

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

sqrt-decomposition

### PROBLEM:

Given an array of size n, having elements from 0 to n-1. Two operations are defined the array.

**1 l r x** : set all the elements from l to r equal to a_{i}=(a_{i}+x)%n

**2 l r x** : find the number of occurences of x in the range l to r.

### EXPLANATION:

The idea is to use **sqrt decomposition** to solve this problem. Divide the array into **sqrt(n)** parts. Then have an array of size **n * sqrt(n)** to store the frequencies of elements in that block.

Lets say that the first type of operation rotates every element of the range by an amount of x.

To tackle the operations of the first type keep one more array of size **sqrt(n)** to represent the rotation of elements in the particular block of size **sqrt(n)**.

So for every operation of 1st type just iterate over all the blocks falling in that range and update their rotation value.

Now to get the frequency of an element x in k^{th} block look for the frequency of the element (x-rotation[k]) in that block.

In this way every operation will take **sqrt(n)** operations.

Total complexity for the pre-calculation of frequencies : **O(n)**

Total complexity for the queries : **O(q*sqrt(n))** where n is the size of the array and q is the number of queries.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.