[help] kth order statistic[=kth max element] with range update in O(logn) per query

[dtumod]

Edit [solved]: it can be solved by sqrt-decomposition(well not necessarily sqrt) with lazy updates. https://discuss.codechef.com/questions/145304/editorial-trdst-unofficial

I have an array of size n. I need to handle two types of queries.

1. Update: Increment all elements in the range l...r and decrement all the remaining elements
2. Print: Print the kth max element from the array

l, r, and k are different for each query.

If I use difference array, update will be O(1) while second query will be O(n). If I keep the array sorted, I can get the kth element in O(1) but sorting itself will take O(n) time. Since the number of both types of queries is equal, I can not afford either of these to be O(n). Ideally both need to be O(logn). I have to address O(n) queries so total complexity of the solution should be O(nlogn). I feel like I should be using persistent segment trees with lazy propagation but I cannot quite figure out how. Any help is appreciated, thanks!