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

Can anyone help with this question?
Автор noobcoderdsa, 10 месяцев назад, По-английски

There is an empty container. 2 types of queries are supported in this container: (i) 1 V X: Insert an element in the container with value V and power equal to X (ii) 2 V 0: Let N be the number of bits in the binary representation of V without leading zeros. Consider all the elements in the container till now, you need to count the number of elements which when divided by 2^N leaves a remainder equal to V and also find the sum of powers of such numbers. Mathematically, count the number of elements Y such that Y is present in the container and Y mod 2^N = V. For all such Y, you need to find the sum of their powers also. Given Q queries, answer queries of type 2 V 0. For time complexity, Q has an upper limit of 2*10^5.

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

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

Hint: Time complexity $$$O(\log (Q \log V))$$$ per query is not hard to reach

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

    Please could you tell how the approach to that time complexity!

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

      For each update query given, the number of remainder that can appear is $$$O(\log_2 V)$$$. Now the rest is just using some data structures for storing answers for each remainder (array if $$$V$$$ is small, map if $$$V$$$ is moderately big) Also deterministic $$$O(\log V)$$$ per query is possible as well, using the (read spoiler below)

      Spoiler
      → Ответить