noobcoderdsa's blog

Can anyone help with this question?
By noobcoderdsa, 10 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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
      → Reply