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

Hackerearth question on segment tree
Автор Kakashi_150, история, 6 лет назад, По-английски

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

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

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

→ Ответить
»
6 лет назад, # |
← 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 :)

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ok thank you ghoshsai5000 . Here is another problem this time of fenwick tree. Please tell me the logic to solve it. Thanks once again :-) Link

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      lazy propagation + seg tree.try to maintain maximum and minimums in a segment and propagate in the tree. Refer this : https://www.hackerearth.com/submission/17727529/

      → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If you want a segment tree question from HackerEarth, here's one that I've actually solved.

      Now in the other question you sent.

      Here's what's done ... Maintain the array in such a way that if you sum from [1, i] you will get A[i]. We do this by inserting A[i] at position i and  - A[i] at position (i + 1).

      For each subtraction query, put a  - 1 at A[1] and 1 at x + 1

      For each finding query, perform binary search with the help of the segment tree.

      → Ответить