Блог пользователя vasandani68

Help needed in persistent segment tree problem!!!
Автор vasandani68, история, 10 лет назад, По-английски

How can this problem be solved with persistent segment tree??Although there are other methods to solve this but i am interested in persistent segment tree!!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Since Ai <= 10**5, you could maintain a segment tree for each i such that it contains 1 in its jth position if arr[j] >= i.

You could form segment tree for ith index from i+1 index easily. Overall there would be total n updates. Hence O(nlogn) For querying start at root of Lth index and apply binary search to get position of kth value. O(qlogn)

AC code here

→ Ответить