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 ai=(ai+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 kth 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.