My solution is O(N*logN), that it works 0.062 sec!!!
But use 680 Kb.

I used data structure with the title "Tree in massive".

My algo is also O(N*logN)0.062 but I used a structre calles
Dinamic Ordered Statistics(Index tree). can you tell me what kind of data structure is "Tree in massive" and from where I can learn more ?

This structure is like Index tree.

and what is index tree.
where can I find about it?

I got ac in 0.062 sec,too.
I use treap.

Is tree in massiv the same thing as Red-Black trees?
I think it's also possible to use RB-trees, becaues it's also O(N*logN).

Tree in massiv is much easier than RB-trees.
In two words tree in massiv is following structure:

Node T contains F([a,b]) and if b-a > 0 its children
contain F([a,(a+b)/2]) first and F([(a+b)/2,b]) second
(else T is a leave).
Using this structure we can update F[x] in O(logN) and
get F[l,r] also in O(logN) where N is length of the
interval in the root.
In this problem F = number of stars on the inrterval.

My 450 byte O(N*sqrt(N)) Pascal solution
works 0.031 sec and uses 240Kb

Hurrra! My solution worked 0.015 seconds!

"tree in massive", "tree in massiv"
"massiv" is russian word and it mean array.
"tree in array"