SPOJ Segment tree problem (TEMPLE queues)

Revision en2, by rr459595, 2018-04-18 09:00:07

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 element using the above segment tree (where internal nodes have max of left and right child) in O(logn) time ?

Thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English rr459595 2018-04-19 11:34:32 18
en4 English rr459595 2018-04-19 11:33:17 2 Tiny change: 'of $O(log^2n)$?\n\nTh' -> 'of $O(log^{2}n)$?\n\nTh'
en3 English rr459595 2018-04-19 11:32:53 24
en2 English rr459595 2018-04-18 09:00:07 42
en1 English rr459595 2018-04-18 08:58:57 635 Initial revision (published)