Hello Codeforces!!

I have many times came across scanline algorithm in tutorials but don't know about that. I googled it and the only thing I came across was the 'Polygon filling algorithms'.

I would be grateful if someone could guide how this algorithm is used in competitive programming questions or provide with some useful links

TIA!

I said the same a few days ago in codechef.The blogs that have been written so far in codeforces or topcoder does not make the topic crystal clear.I would really like someone to write a beautiful blog on this.

https://www.youtube.com/watch?v=lFBpH_Mt_LI&t=412s

I guess its as i say :

We have an array $$$a$$$ of $$$n$$$ integers, we want to calculate $$$\sum\limits_{1 \le i < j \le n} a_i \cdot a_j$$$.

My approach is that lets calculate array $$$sl$$$ of length $$$n$$$ such that $$$sl_k = \sum\limits_{1 \le i < j \le k} a_i \cdot a_j$$$ and $$$sl_1 = 0$$$ by definition, then $$$sl_i$$$ can be calculated using $$$sl_{i-1}$$$, its a DP form of scanline, you can instead of storing array $$$sl$$$, just remember the previous one. For some cases its useful to not to store them, for example when we calculate LIS using monotonically increasing stack.

I'm not sure, correct me if i'm not.

In this case, using this identity would be easier I think

Nice one, i haven't seen this before(its really easy to see why it works), Thanks.

But in fact the point was something else.

You should contact the MAME team. It uses scanlines to emulate the Arcade screen.

https://www.youtube.com/watch?v=lFBpH_Mt_LI&t=412s