We have an array of numbers and we are supposed to do the following queries on it:
- Add number
xto all elements on the subarray with indices
[ L, R ]of the array.
- Query for number of elements less than number
xof the whole array.
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)$ where $n$ is the size of the array and $q$ is the number of the queries (Storing sorted subarray in each block). 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?
The only constraint is that the solution should work for 2 seconds when $n, q < 1e5$ and you can answer queries offline. Total complexity should fit in the constraints and the complexity for each query is not important.