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

Segment Tree Problem
Автор rickgrimes07, история, 14 месяцев назад, По-английски

Given an array of positive integers , you have to perform Q queries . Each query can be of two types , 1 L X 0 , set arr[L]=X;

and other type be 2 L R X , find index p such that arr[p]<=X and if there is no such p , print -1.

arr size and Q are of order 1e5

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

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Store the index of the smallest element in the range of each node in the segment tree (take any if there are several). Queries of type 1 can be handled in $$$O(log(n))$$$ time. Queries of type 2 can be processed as follows: get indices $$$I_{1}, I_{2}, ..., I_{q}$$$ (where $$$q \le log (n)$$$), and find index with the smallest value. If it is larger than $$$X$$$, then print $$$-1$$$, otherwise print the index with the minimum value.

→ Ответить
»
14 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

We can use a minimum Segment Tree for this problem.

For type 1 queries, we can do Point Update in Segment Tree, which leads to a complexity of O(log N)

For type 2 queries, we can do Binary Search on Segment Tree, which also leads to a complexity of O(log N). More details regarding to this technique : https://mirror.codeforces.com/blog/entry/83883?#comment-712331

Total complexity : O(N) for building the segment tree, and O(log N) for each query.

→ Ответить