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

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

Hello all, I have a question from hackerearth which is tagged under segment tree. Can anyone tell me what approach to use to solve it using segment tree? Link

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It could be solved without segment tree also.Refer https://www.hackerearth.com/submission/15779371/

»
8 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +6 Проголосовать: не нравится

Question is saying given an array of N elements, in each query give the number of pairs in [L, R] that have the same number of divisors.

  • The key observation here is that upto a million, the number of factors a number can have is not too large. In fact, it's about a 100.

  • Maintain a 100 segment trees. Each segment tree contains the frequency of divisor i.

  • Suppose you have to replace element x with element y. Then update segment tree d(x) and segment tree d(y).

  • To answer the other query, go over all 100 segment trees. If a pair has frequency f in range [L, R], add to the answer.

Note — I've explained a harder version of the question. In the given question, you only have to answer queries reporting the number of pairs in range [L, R], you don't have to deal with point updates. So, segment tree is unnecessary overhead here and prefix arrays are better. If the question said that in some queries you must replace certain numbers, then you can use segment trees :)