There are a lot of problems where the same idea can be used.

Try to think of such a problem first:
You have a string of n zeroes.
Then there will be a series of either requests or data changings
(they may follow in any order).
On a request you have to output the first non-zero element of the
string (or say that all the elements are zeroes).
On a data changing you have to increase or decrease the value of one
element.

The obvious algorythm will take you O(1) at each data changing and
O(n) at each request. Try to think of an algorythm that will take
O(Sqrt(n)) at each request and at each data changing.

I'm sure that if you solve this problem, you'll be able to solve the
stars problem as well.

Good luck!

That's great!

> There are a lot of problems where the same idea can be used.
>
> Try to think of such a problem first:
> You have a string of n zeroes.
> Then there will be a series of either requests or data changings
> (they may follow in any order).
> On a request you have to output the first non-zero element of the
> string (or say that all the elements are zeroes).
> On a data changing you have to increase or decrease the value of
one
> element.
>
> The obvious algorythm will take you O(1) at each data changing and
> O(n) at each request. Try to think of an algorythm that will take
> O(Sqrt(n)) at each request and at each data changing.
>

Hi,

are you suggesting an O(n sqrt(n)) solution for stars?  Well, I think
that O(n log n) suffices, but O(n sqrt(n)) should be able to beat the
time limit.

As for that question, I think I can get O((log n)^2) request and O
(log n) update.  I am sure other better algorists can beat this
complexity however.

Thanks.

But how i solve stars with it?

Can you tell me how to do it?
mailto: pserega@r66.ru
Thanks.