We have an array of numbers and we are supposed to do the following queries on it:
- Add number
x
to all elements on the subarray with indices[ L, R ]
of the array. - Query for number of elements less than number
x
of the whole array.
Note that x
is given in each query and is not fixed.
I have a solution with time complexity $$$O(q \cdot log(n) \cdot \sqrt n)$$$ using Square root decomposition (Storing BST for each sqrt block or just sorted subarray in each block) where $$$n$$$ is the size of the array and $$$q$$$ is the number of the queries. However for constraints $$$n, q < 1e5$$$ with time limit of 2 seconds this is not efficient enough. So how to solve it on these constraints?
- As mentioned by lemelisk in the comments, this can be solved in $$$O(\sqrt{n \cdot log(n)})$$$ per query.