you can solve this problem with sqrt-decomposition on queries + persistent segment tree 
My solution: https://www.codechef.com/viewsolution/17543787
Anyone whose solution is failing for first test case of third subtask: Use unsigned long long instead of long long int whenever computing sum.