Link to the problem :- http://www.spoj.com/problems/TEMPLEQ/
In this question for answering type 3 queries where we have to update the nodes with value greater than x, we create a segment tree and do lazy propagation. In segment tree, internal nodes are maximum of left and right child.
For answering type 1 queries (updating), I need the last index of a particular element. If array is 1 2 2 2 2 5, last index of 2 is 5.
My question is how can I find the last index of a particular using the above segment where the max of left and right child are stored in O(logn) time ?
Thanks.