PROBLEM LINK:
Author: Vaibhav Daga
DIFFICULTY
Medium-Hard
PREREQUISITES
MO’s Algorithm, Segment Tree
PROBLEM
Given an array and m queries of the form (l,r). Find the maximum length of all the continuous subarray in the range (l,r), inclusive, such that the sum of the elements of the subarray is divisible by k.
EXPLANATION
The naive solution is trivial. For each query (l,r) traverse the array from l to r and store the prefix (starting from l) sum modulo k. Then find two indices p and q such that presum[q] - presum[p] is equal to 0 and (q-p) is maximum among all possible pair of indices. This is a common problem and can be done in O(n) by storing the indices for all values of modulo k and finding the pair of indices with maximum difference belonging to the same value modulo k. The naive solution takes O(m*N) which is sure to give TLE.
So the naive solution needs to be optimised. Instead of traversing the queries from l to r, we can process the queries offline using MO’s algorithm. MO’s algorithm can be read here. I will use the notations used in the link given. But to use MO’s allgorithm we must be able to write add and remove functions. This is the main task in using MO’s algorithm so I will explain how to write the functions for this problem.
Before coming to the functions we need to do some preprocessing. Compute the prefix sums modulo k and store the all the indexes in increasing order having same prefix sum in a vector for each sum. Lets call this vector prefixSum, prefixSum[sum] will give all indices having prefix sum modulo k equal to sum. For each sum also store two pointers, left and right, which tells the leftmost index active in the current range and rightmost active index for a particular prefix sum.
Add function:
Case 1: Elements are added from left side of the previous query. When elements are getting added when moving the currentL left, then the left pointer of the prefix sum that becomes active has to be changed. Since we have stored the indices of prefix sums in increasing order, this can be easily done by moving the left pointer one step backward.Case 2: Elements are added from right side of the previous query.
When elements are getting added when moving the currentR right, then the right pointer of the prefix sum that becomes active has to be changed. Since we have stored the indices of prefix sums in increasing order, this can be easily done by moving the right pointer one step forward.
if(f){//second case
right[val]++;
if(left[val]==-1)
left[val]++;
}
else{
left[val]--;
}
Remove function:
Case 1: Elements are removed from left side of the previous query. When elements are getting removed when moving the currentL right, then the left pointer of the prefix sum that becomes inactive has to be changed. Since we have stored the indices of prefix sums in increasing order, this can be easily done by moving the left pointer one step forward.Case 2: Elements are removed from right side of the previous query.
When elements are getting removed when moving the currentR left, then the right pointer of the prefix sum that becomes inactive has to be changed. Since we have stored the indices of prefix sums in increasing order, this can be easily done by moving the right pointer one step backward.
if(f){//second case
right[val]--;
}
else{
left[val]++;
}
After performing all the update operations using Add and Remove functions, we need to get two indices p and q such that prefixSum[p]== prefixSum[q] and abs(p-q) is maximum. For a particular sum, p = left[sum] and q = right[sum]. We need to find the maximum of (q-p) for every value of sum. To do this, make a segment tree over all the possible values of sum, (total possible values = k). In each node store the maximum value of (q-p) for that range. On updating the left and right pointers, update the value of the sum in the segment tree with the value prefixSum[sum][right[sum]] - prefixSum[sum][left[sum]], which will be the new update for the sum in segment tree.
TIME COMPLEXITY
O(N*SQRT(N)*LOGN)