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

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!Can you share link to the problem?

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

How would you solve it with sqrt decomposition?

Split and rebuild style

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

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.

Thank you very much joomas

It can also be solved online with dynamic segment tree, with complexity

O(QlogY)cool..., the core idea of Li Chao Tree.