We have an array of numbers and we are supposed to do the following queries on it:

1. Add number x to all elements on the subarray with indices [ L, R ] of the array.
2. 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.

I am facing a really weird fast execution time on Codeforces on submission 75468775. On test #6, the code runs for 1153 ms on Codeforces servers, but when I run it on my own computer, it takes me 5682 ms to run! Yes there is difference on hardware of course, but it runs about 5 times faster on Codeforces! I am wondering if there is any optimization on Codeforces servers or compile instructions which makes it run as fast as this?

UPD: That is actually because of -O2 compile flag. Never knew it affects the running time as much as making it run 5 times faster.