I have wrote 2 solutions for this problem in java (actually the only difference is writing an iterative VS recursive segment tree). But both got me TLE.
I am asking here because I can see that there are 3 people managed to get this problem accepted with java. I am curious to know whether they are doing constant time optimisations or they have better approach than O((n + q)log(n + q)) ?
here is the link to the problem: http://www.spoj.com/problems/DQUERY/
Here is the link to my recursive segment tree code: http://ideone.com/itwocf
Here is the link to my iterative segment tree code: http://ideone.com/33m8yZ
If anyone has any way of accepting this problem with java please tell me about it.