Problem Statement : https://www.codechef.com/problems/QCHEF?tab=statement
I was practicing MO's algorithm and encountered this question, but I am getting TLE here is my submission : https://www.codechef.com/viewsolution/1036034418
I'll explain my approach here : So for every range $$$[L, R]$$$ you need to answer the query asked in question i.e. $$$\mathrm{max} { |x-y| | L \leq x, y \leq R \; \mathrm{and} \; A_x = A_y }$$$
Since all the values are bounded above by $$$M$$$, I could use MO's algorithm to solve this problem by maintaining current max difference corresponding to each distinct value present in current range
In other words, I could maintain an array $$$T$$$, where $$$T[x]$$$ stores current range's max difference value corresponding to value $$$x$$$.
It is easy to maintain this array as you're adding or removing elements from the range, if you add an element say $$$A[idx]$$$, you simply update $$$T[A[idx]]$$$, say you're adding it from the left, then you need to find the rightmost index in the range whose value is also $$$A[idx]$$$. You can realise this easily using binary search by storing indices of each value occurring in array in increasing order.
Similarly, you can handle the cases where an element is removed
Since, I need max of this array $$$T$$$ after every query, I am using a segment tree to do that.
Time complexity of solution is $$$O((N+K)\sqrt{N} \log M)$$$, because each add/remove/get_answer methods from MO's algorithm takes $$$O(\log M)$$$ time (binary search, segtree update, segtree query)
Any help would be greatly appreciated, Thanks
Look, let's maintain the maximum distance between the elements in the root structure, then you can update the MO in O(1), and then take the maximum for this root structure in O(sqrtn), which will not worsen the asymptotics, you can also maintain the left and right occurrences of each number simply in an array. Write if something is unclear PS: sorry for the bad English
By root data structure, you mean sqrt-root decomposition right? how do you update in sqrt structure with max operation ?
Yes, I mean sqrt-root decomposition. You can make it for each length of the segment, and when a new length appears, you make +1 in place of this length, and if such a length does not exist now, then you make -1 for this length. Now we need to maintain the amount on the block, this is done easily, again just +-1 when updating. Now, to get the maximum element, we need to find the rightmost number that is not equal to 0, we are looking for the rightmost block with a sum of not 0, and then the rightmost non-zero number in it
There is a version of Mo's algorithm that doesn't require remove method link.