You can use a treap to support all 4 types of queries in $$$O(n lg n)$$$. This is the most basic and common use of a treap.

But I'd like to discuss a sqrt decomposition solution as well (not supporting remove queries). We will store all the values in a sorted array. Whenever an insert query comes, we will put it into a buffer. When the size of the buffer becomes more than $$$\sqrt n$$$ we will rebuild the whole array. The increase query can be done pretty easily, just keep a lazy value for the array, and update all the current buffer values manually. Now, the kth element. We can easily do it with binary search, but it will bring something like $$$O(\sqrt n \lg n)$$$ complexity. So we are going to do another sqrt decomp. on the array. We will split the array into $$$\sqrt n$$$ chunks as well. Then we can easily do two pointer walk through our buffer and the array, achieving $$$O(\sqrt n)$$$ per query.

EDIT: You can also support remove queries using the same idea as buffer. Whenever a remove query comes, two cases can happen. It removes an element from the buffer or from the array. If it removes from the buffer, it's very easy to do. On the other case, it creates a hole in the array. We just mark it as deleted, but keep it in the array. When the number of holes become more than $$$\sqrt n$$$ — rebuild. Modify all the other queries likewise.

Note: It can't solve the whole problem, but it seems interesting.

You can use treap, like arman_ferdous mentioned. You can also use some policy-based data structures like ordered_set to maintain some of the operations. Where you will be able to perform these operations:

• insert an element
• delete an element
• Find the kth largest element in the set
• find number of elements which is less than k.(if you give him a number, it'll find out the number of elements which are less than that number)

Although it can't handle updates, I think it may help. Actually it can but the complexity is high. here is a link for ordered_set.