Disclaimer: There's a good chance this won't quite run in time.

Divide the array into m equal-sized blocks. For each block, keep a binary indexed tree of the elements in that block. Then, for a query, you can make a single query to the BIT (to count elements less than k) for each complete block in the range, and for the two partial blocks on the end, just loop through the elements. Therefore, the query time is O(m * log(10000) + n/m). The update is just updating a single BIT = O(log(10000))

Let m = 50. Then, the total time for 200,000 queries is 200,000 * (50 * log(10000)) + 600), which is about 250 million operations.

I'm hoping there's a way to speed up the queries by slowing down the updates somehow but I can't think of any ways to do that right now.

With updates you can do it in O(n log^2) if you replace sorted arrays with treaps. It is a bit complicated solution, may be it is possible to use something easier.

Don't mind, it leads again to log^2.

Use 2D segment tree or store a persistent segment tree at each node :D.

The first time I AC this problem, I used 2D BIT, which cost so much memory (but it got AC). The main idea of this one is calculating S(x,y) which is number of elements lesser/greater than y in a[1], a[2], ... , a[x].

Later I changed to BIT and sqrt decomposition with the same idea above. You know that a 2D BIT is N 1D BITs in someway. Instead of using N 1D BITs (which is actually a 2D BIT) for N element, I used sqrt(N) 1D BITs which would be a 2D [sqrt(N) x N] BIT. That's all, the remains are just basic sqrt decomposition technique.

Complexity :

O(2*log(sqrt(N)) * log(N) + 2*sqrt(N)) = O(sqrt(N)) per query.

O(log(sqrt(N)) * log(N)) = O((log n)^2) per update operation.

...which is fast enough.

I have no idea how to solve this in O(log n) per operation/query.

Hi -

recently I submit this code to this problem; except I get TLE. Solution utilizes 2D segment tree. Anyone can suggest any optimizations that will help it pass?

Thanks in advanced-

Disguised

Has anyone been able to get AC in this problem by storing an implicit segment tree in every node of a normal segment tree? I am getting TLE using this idea.

Also how do you solve this problem by 2D segment tree or 2D BIT or by storing a BIT in each node of segment tree? Isn't that going to take too much memory?

N.B.: I have solved this problem using square root decomposition plus BIT. Theoretically the complexity of the query operation for the implicit segment tree idea should be better while that of the update operation of the sqrt idea should be better. But I am interested to know if this problem can be solved using implicit segment trees within time limit.

Thanks very much.

My O(N lg^2 N) code passes in 1.38s even though the time limit is 1sec lol. My solution: Coordinate Compression + BIT in Segment Tree.