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