I have a solution which will time out because its complexity is O(n √n log(√n)).
So as you would guess by the √n factor its obviously sqrt decomposition.
Divide the array into √n blocks and sort each block. Now for a given opearation don’t update the block(which is fully overlapping with the concerned range [L, R]) but instead maintain a counter array of size √n which maintains the information how many times the block was updated completely(i.e no times all the array elements of the block where reduced by 1). Update the partially intersecting blocks manually(Don’t forget to sort the 2 block which intersects partially with [L, R])
Now after update you consider range from [j, N] and check how many elements in each block is less than k which can be done with binary search(dont forget to count the no of times the block was updated completely).
I will think of some O(n log(n)^2) solution , because you can see clearly that my solution is not taking the advantage of the fact that upper bound for query is always N.
I will just update this post if I come up with some solution.
I liked the problem, may I know which company interview problem is this ?