Could you please give me some hints? All my submissions get the same answer "time limit exceeded".

Cumulative Frequency Tables

Can you explain it more concretly?With me,  "Cumulative Frequency Tables" looks strange.

In my words:
It is 2^n type structure of data
with O(log) insert and O(log) interval-[left,right]
query in additive on subsets in [0,MAX] data,
easy to programming.
Best explanatuion in
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html

Thanks

I think it is more usual to use Fenwick trees

Now I confirmed  Cumulative Frequency Tables and ideas of
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html
practically having AC 1.37 not very bad because used iostream. Tables better than Fenwick trees because they used
only arrays. For adopting the method I used
formulas a[k]=f(t0,t1,t2,...,tk) where tk=sum of A[i]^k
and is additive contrary to a[k].
During a long time had WA7 because forgotten
that abs does't work in __int64 and
we must build our own abs for __int64.

After cosmetic modifications have 0,843 Ac ant 3-th.
Edited by author 27.09.2007 14:24

Edited by author 27.09.2007 14:31

Edited by author 27.09.2007 14:51

Edited by author 27.09.2007 14:52

For using Fenwick trees you also need only array, and, moreover, only one array!

I used 4 interval trees. One having Ai, another having Ai^2, another Ai^3 and the last one Ai^4. This way you can compute Al^k + ... + Ar^k in log(N) for k=1..4. This info is enough to calculate S(L..R, K).

It can be easily done using Segment tree. Try to store this s[0...4] for each node in segment tree. Now you can find a nice formula using convolution to merge two nodes.