I_love_Saundarya's blog

By I_love_Saundarya, history, 5 years ago, In English

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 !

  • Vote: I like it
  • -11
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

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.