Segment Tree and Scanline, a match made in hell

Revision en1, by Mindeveloped, 2024-09-23 15:32:48

I can use segment trees well, and I've done some basic scanline problems. But whenever these two algorithms appear in the same problem I will 100% fail to solve that one. I've been solving 930D - Game with Tokens and I was able to reduce it to "count the amount of integer points with at least one black point in each quadrant in terms of $$$(x+y, x-y)$$$". Then I stuck on the next move for 40 minutes. It turned out to be a stupid "scanline on $$$(x+y)$$$ build segment tree on $$$(x-y)$$$" thingy. Now I'm mad.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Mindeveloped 2024-09-23 15:32:48 540 Initial revision (published)