Range query with minimum number having specific property

Правка en1, от dreamplayDaddy, 2019-04-12 16:22:47

I have a vector of pairs of length N. Now i have Q queries of type, given range let say L to R, find the minimum value of second element of pair whose first element is equal to given number K.

For example : vector of 6 elements [{2,5},{8,7},{2,3},{8,6},{2,1},{8,4}] Now for query : L=3 R=6 (1-based indexing) and K=8

Answer would be -> 4 which corresponds to this pair {8,4}

There are 10^5 queries and N can be upto 10^5.

can someone give me an idea how to approach this problem more efficiently?

Теги segment tree, c++, #logic, #algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский dreamplayDaddy 2019-04-12 16:25:03 0 (published)
en2 Английский dreamplayDaddy 2019-04-12 16:23:29 0 (saved to drafts)
en1 Английский dreamplayDaddy 2019-04-12 16:22:47 568 Initial revision (published)