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

HELP REQUIRED IN SPOJ K-QUERY
Автор FineLine, история, 8 лет назад, По-английски

Hi everyone,I have been trying this question SPOJ K-QUERYfor 2 days now.After unsuccessful attempts to come up with logic,I finally referred Blogs available online.But I am neither getting head nor tail of the logic. Can someone please tell me the formation of fenwick/segment tree that is used(especially the technique used).It will be a great help.Please! Thanks in advance.

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

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

try amd blog on segment tree he has explained it nicely segment tree. If you still need help then ask.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

That has been explained so many times... Just google it.

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

    I had tried it.But I did not get good explanation .All the blogs gave code .I tried understanding it using pen and paper literally.But I could not get the basic strategy behind it.The best blog I got was of PrinceOfPersia , But still could not understand it. Instead of showing me How to Google ,It would have been great that you could have explained it to me. Anyways Thanks radoslav11....

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

      Well the main idea is to solve the problem offline. At every query we should care just for elements with value < K. Lets make events. Every event will be either an adding of element at position POS with value VAL or a query.

      We sort these events by VAL and K (depends if event is an adding or a query). Then our problem becomes:

      For every query what is the number of added elements before it in range [L; R].

      This can be done with an range-query and point update on segment tree or with a BIT: For every adding we set the value of POS with 1 and for every query we get sum of [L; R].

      The complexity is O(Nlog(N) + (M+N)*log(N)) = O(Nlog(N)).

      PS: The problem can be also solved online with a merge sort tree in O(N*log^2(N)) time.

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

        Thanks radoslav11 and SORRY if you found my above comment offensive .I actually had tried lot before asking on the forum.Again Sorry!!

        → Ответить