Блог пользователя I_love_Saundarya

Автор I_love_Saundarya, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
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.

»
5 лет назад, # |
  Проголосовать: нравится +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

»
5 лет назад, # |
  Проголосовать: нравится +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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится 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.