Question Link: Link
This can easily be solved with lazy propagation and that is the first method that strikes the mind during the live contest. But after thinking about it for some time I thought of an approach to solve it without lazy propagation but rather a simple segment tree.
So rather than working on an array of size n, we work with an array arr of size n-1, such that
arr[i] = (input_arr[i] == input_arr[i+1])?0:1 for 0\leq i < n
There are two types of queries:
- Finding the number of adjacents pairs, that can easily be done by a segment tree which stores result of the sum of the array. Note that in the new array i^{th} term stores the result for i^{th} and (i+1)^{th} item. So though l remains the same but r need be reduced by 1 in order to calculate the correct result
- Note that if all the elements in L and R are complemented, there will be no change in any number in the range but only between these pairs (L-1,L) and (R,R+1), thus only indices saving these results need to be complimented. Thus only two update calls will work.
Solution Link for Reference: Link