dreamplayDaddy's blog

Range query with minimum number having specific property
By dreamplayDaddy, history, 6 years ago, In English

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?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dreamplayDaddy (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is k fixed?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

We can try like this:

Make a vector for each value of K. The first value of the pair is the second element of the original pair, and the second value is the position in the original array. In the problem it will look like :

2->{5,1}{3,3}{1,5}

8->{7,2}{6,4}{4,6} (each vector is sorted on the basis of position(2nd value of pair))

then build a min-segment tree for each vector[K]. for each query, using lowerbound/upperbound, find the indexes for the search in the segment tree.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you can solve it offline you could order the queries by increasing k.

Then, for every different k, add to the segment tree all pairs that have the first element equal to k. Now you could simply query the segment tree for the minimum element of range [l, r] as we know that the condition will be always met. As soon as we are done processing all queries of the same k, remove the pairs we previously added.

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

You can probably use square root decomposition. Partition the vector of pairs into $$$\sqrt{N}$$$ blocks.

For each block maintain a map which stores the minimum second element corresponding to the first element in the pair.

For each query you'll be going over $$$ O(\sqrt{N}) $$$ complete blocks and $$$ O(\sqrt{N}) $$$ elements that don't belong to complete block and have to be catered to one by one.

Complexity per Query will be $$$ O(\sqrt{N} log(N)) $$$ which can be reduced to $$$ O(\sqrt{N}) $$$ with coordinate compression ( costs $$$ O(Nlog(N)) $$$ worth of pre-processing) if elements of the pair are large or using lookup array if they are smaller.

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

There exists better solution for XORMIN, which doesn't use this and finds both answers at same time.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can just use segment tree, where in every node you need to have a treap that contains all values in that subtree, and every node of the treap contains minimum of the second elements, now you can answer all queries in O(log^2n) time.

→ Reply