shahadat03's blog

By shahadat03, history, 3 months ago, In English,

You have an empty set. You have to support Q queries in the form —

1 X: Insert an element X in the set. It is guaranteed that X isn't already present in the set.

2 X: Delete an element X from the set. It is guaranteed that X is present in the set.

3 Y: Find and print sum of maximum Y elements in the set. If there are less than Y elements in the set, you need to print sum of all elements.

What is the best way to solve this problem? X<=10^9, Q<=10^5 Y<=10^5

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Since you've mentioned a set, I assume that at any instant, all numbers in the set will be distinct.This can be solved by using Policy Based Data Structure in C++ and segment tree. Here goes my solution. Since X<=1e5, So atmost 1e5 distinct numbers will be given in input.First save all the numbers you get in all the queries. We need to compress these numbers to smaller numbers so that all lie in the range [1,1e5]. This can be done using coordinate compression which is a fairly popular technique. Now we've mapped all numbers, its time to build the segment tree.Mapping of every number can be used as index in the segment tree. Side by side also maintain a PBDS of mappings. This can be used to find the (n-y+1)th element for queries of type 3. type 1 and type 2 queries are easy now. Just insert and delete the required number from PBDS and segment tree.This will be a log(n) operation.For query of type 3, find the (n-y+1)th element in PBDS. Now get the range sum in [(n-y+1)th element,100000] from the segment tree. This is also a log(n) operation. Hope it helps!

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

Can you share link to the problem?

»
3 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Offline solution: BIT + map. Online solution: treap, splay tree or sqrt descomposition.

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

    How would you solve it with sqrt decomposition?

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

    Can you please explain what do you mean by 'offline' and 'online' solutions ?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      An "offline" solution needs to know all the queries beforehand to work efficiently (for example it might reorder the queries for faster answering). An "online" solution works efficiently even if it is given one query at a time.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It can also be solved online with dynamic segment tree, with complexity O(QlogY)

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      cool..., the core idea of Li Chao Tree.