### I_love_Saundarya's blog

By I_love_Saundarya, history, 4 years ago,

We are give 2-arrays, one array is called the original array and other is the corresponding array.

Example : -

a:- [5,6,5,7,5,5,5,8,9]

a':-[1,2,3,1,2,3,1,2,1]

We are given 3-values:- 'l','r' and 'x'

Let l=3 and r=7, also x=5,

so we check the occurrences of '5' in the range [3,7] , so a[3],a[5],a[6],a[7] are the indices which contain '5' .

Now,we check the corresponding array's values,i.e, a'[3],a'[5],a'[6],a'[7] which are:- '3','2','3' and '1'. The minimum of these is '1' and hence the output will be :- "1" .

I know the brute-force approach for multiple queries like this, but I'm interested in an efficient approach !

• -11

| Write comment?
 » 4 years ago, # | ← Rev. 2 →   0 If online, dynamic segment tree on every possible value in the original array.Otherwise, sort queries by x, and keep a single segment tree which answers a query on given x. When switching to another x, update the segtree by resetting previous values and setting ones for the next x.
 » 4 years ago, # |   +8 You can solve it by using 2D segment tree I think, where 2nd dimension is the value being checked (x). Then use RMQ on each
 » 4 years ago, # |   +8 I think this can be solved similar to a merge-sort segment tree.For a given range {l,r} we can find store a vector of pairs {x,y} , such that x is the element we need to query on and y is the answer to x.Since number of distinct elements in the range can be atmost r-l+1 , that will be the max size of the vector.So space complexity is O(nlgn) and time is O(lg^2n) per query
 » 4 years ago, # |   0
 » 4 years ago, # |   0 The amount of people asking help on a problem that's from an ongoing contest is actually amazing. You're like the 5th person this week asking for help on Codechef's XORMIN.