Can anyone tell me the suitable algorithm/approach to solve this problem
2 Likes
I think this can be solved by sqrt decomposition in O(Q * M * log(N)) time where M = sqrt(N). The basic idea is to divide the given array into M blocks each of size M, Now we change each element a[i] to its prefix sum. Then a sum of range l…r is zero if and only if a[l - 1] == a[r]. Now each query range l…r can be covered by at most M blocks of size M and at most 2*M-2 trailing and leading elements. For each distinct element we can store all its occurrences at separate places and we can to binary search to find the right most elements which is less than or equal to r. Similarly we can do for each block we pre-process and store what is the answer for each right in O(N) so total of O(N * M) for M blocks and answer in O(1) for query on each block. And I also guess that we can remove the log(N) factor of binary search by doing offline programming.