I was doing a problem on Hackerearth contest, it was similiar to a problem i solved in one of the codeforces round but was more difficult than that.
Problem : We start from nothing. There are 4 type of queries -> 1. A x -> adds element x in array 2. I x -> increases value of all elements in array A by x 3. D x -> decreases value of all elements in array A by y 4. P k -> print the kth greatest element in the array so far
I don't remember the constraints but they were large enough that brute force won't work.
I know these types of problems can be solved by using suffix array for updating values and i tried that but couldnt figure out how to handle the query of type 4.
Any help would be appreciated
Thanks in advance.
There are many ways to solve this problem, using fenwick tree, segement tree, ordered_set.
Instead of giving an exact solution, I'm dropping a hint and see if you can work it out.
Instead of increasing or decreasing all elements by a value x, keep a variable which keeps track of extra value to be added to each element. So, value of any element will be value of element while inserting it in the container (array, ordered_set, etc.), + value in this extra variable.
You should be able to solve it now, since query 2 and query 3 have become O(1). Try it out if you're still stuck, I can provide you with code for it.
i did the same lazily updated the values but how do i get the kth largest element and suppose you can't use ordered_set , with ordered set it's ez but suppose u can't use PBDS
Binary search the answer and count elements <= it
How do you find kth largest element using binary search ? Can you elaborate
Try solving MKTHNUM on Spoj and you can also look for some guidance on same on internet. This answers you question.
I could have told you answer directly but it's better if you learn things on way, and I guess this is why you're solving that question.
ok i saw that question, I didn't know about persistent segtree so i'll learn it. But even after using that how exactly do you make the increase and decrease the values in O(1). How can keeping a single variable handle updates for all elements as elements are getting added in queries and addition and subtraction is also been done in queries at different times.So when i get a P query i would use persistent segtree to find kth largest element but how do you know what all increase values and decrease values are to updated for that element, i would either update all elements during a P query and then one variable would work or i will make a suffix array of updates and then update the value accordingly depending on which item is kth largest one.
Can you elaborate your solution a bit. Thanks
First thing to note is that the extra value you are adding to/removing from all elements don't change the order of elements in sorted array.
So, the question reduces to finding Kth element (in sorted order) of a running input.
Using a fenwick or segment tree, you can store how many elements have value u, i.e arr[u] is the count of element having value 'u' initially. You need to binary search on fenwick / seg tree to find count of elements less than given value. When you reach the stage where count of elements till certain value is < k, you can say the next element having count > 0, is the kth element.
ohh ok thanks a lot i get it now
We can make all the updates in a single variable, let's say "sum" so when any element "n" comes for insertion ,we would simply insert n-sum. Use a fenwick tree, take the size of fenwick tree accordingly as any time element can get negative also, so take a constant value and take any element "n" as n + const. value so that we can guarantee that n + const.value > 0. Finding kth element can be done by binary search. Find no of elements less than equal to a given value. If it's >=k , store this value as the current answer and try for a lesser value i.e, "high=mid-1" otheriwse "low=mid+1".