Range query with minimum number having specific property

Revision en1, by 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?

Tags segment tree, c++, #logic, #algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English dreamplayDaddy 2019-04-12 16:25:03 0 (published)
en2 English dreamplayDaddy 2019-04-12 16:23:29 0 (saved to drafts)
en1 English dreamplayDaddy 2019-04-12 16:22:47 568 Initial revision (published)