By shahadat03, history, 3 months ago, ,

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

•
• +5
•

 » 3 months ago, # | ← Rev. 2 →   0 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, # |   0 Can you share link to the problem?
 » 3 months ago, # | ← Rev. 2 →   +5 Offline solution: BIT + map. Online solution: treap, splay tree or sqrt descomposition.
•  » » 3 months ago, # ^ |   0 How would you solve it with sqrt decomposition?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +5
•  » » 3 months ago, # ^ |   0 Can you please explain what do you mean by 'offline' and 'online' solutions ?
•  » » » 3 months ago, # ^ |   +5 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, # ^ |   0 Thank you very much joomas
•  » » 3 months ago, # ^ |   +10 It can also be solved online with dynamic segment tree, with complexity O(QlogY)
•  » » » 3 months ago, # ^ |   +5 cool..., the core idea of Li Chao Tree.