PROBLEM LINK:
Author: Arkapravo Ghosh
Tester: Md Shahid
Editorialist: Arkapravo Ghosh
DIFFICULTY:
MEDIUM
PREREQUISITES:
Segment Tree with Lazy Updates, Sqrt Decomposition
PROBLEM:
We are given a string S. We need to perform Q queries on the string. There are two types of queries: -
- U L R V - Update the substring SL,SL+1,...,SR by incrementing each character in the substring by V. We increment a character in a cyclic manner, i.e. by adding 1 to ‘a’ becomes ‘b’, by adding 1 to ‘b’ becomes ‘c’, and by adding 1 to ‘z’ becomes ‘a’.
- F L R - Find the number of vowels in the substring SL,SL+1,...,SR.
EXPLANATION:
We can solve this problem by using segment tree. In each node of the tree we can store the frequency of each character (‘a’ – ‘z’) in the substring corresponding to the node. We can do this by creating an array of size 26 in each node. In this array, let the value at index 0 denote the frequency of ‘a’, index 1 denote the frequency of ‘b’, …, index 25 denote the frequency of ‘z’. So, in this array the indices corresponding to the vowels are: – 0 for ‘a’, 4 for ‘e’, 8 for ‘i’, 14 for ‘o’ and 20 for ‘u’.
Let us denote X[i] as the values in the array of each node in the tree, i.e. from X[0], X[1] … upto X[25], which is the frequency of each character (‘a’ - ‘z’) in the range of the node.
We also need to keep a lazy array for the range updates. Each node of the lazy array will contain the value by which we need to increment each character in the substring corresponding to the node.
Let us consider for an update query V = 4. So, in the given substring, the a’s will be incremented by 4 and will become e, the b’s will be incremented by 4 and will become f, … , the z’s will be incremented by 4 and will become d. When we update the values, suppose for a particular node which falls completely in the range of L to R, all the a’s will become e, i.e. the new frequency of e will be the old frequency of a, all the b’s will become f, i.e. the new frequency of f will be the old frequency of b, and so on. It will go on in a circular fashion for each index from 0 to 25 (remember value at index 0 represents frequency of ‘a’, 1 represents frequency of ‘b’, …). First, we can store the values for each index i (0 <= i <= 25) in a temporary array by shifting them to index (i+V)%26. When we finish calculating the new values for every index from 0 to 25, we can copy them over again. In this technique we can perform the range updates.
When we are querying the tree, we need the number of vowels in the substring SL,SL+1,…,SR. In a node of the tree the sum X[0]+X[4]+X[8]+X[14]+X[20] is the required value, i.e. the total number of vowels in the substring corresponding to the particular node of the tree. We can simple return the sum of all these values of the tree nodes which falls in the range L to R by doing a simple range query.
See solution for clarity.
TIME COMPLEXITY:
Time required to build the segment tree is O(|S|).
Each query for update or find will take O(log(|S|)).
So the total time complexity is O(|S| + Q*log(|S|)).
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.