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 !
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.
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
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
hmm
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.