Segment tree beats | IOI preparation #6

Segment tree beats is a data structure that can handle queries "maximize interval with X" and "compute the sum in interval". There is a great blog on Codeforces about it: https://codeforces.com/blog/entry/57319 - Frequently Asked Questions: https://github.com/Errichto/youtube/wiki/FAQ - Github repository: https://github.com/Errichto/youtube - Facebook: https://www.facebook.com/errichto - Twitter: https://twitter.com/errichto - Competitive Programming Discord: https://discordapp.com/invite/UzaURu7 - Youtube channel 1: https://www.youtube.com/errichto (mainly short videos) - Youtube channel 2: https://www.youtube.com/errichto2 (streams) I’m Kamil Dębowski, better known as Errichto. I compete in and organize programming competitions. I make educational streams on Youtube and Twitch. I'm a finalist of ACM-ICPC, Topcoder Open, Facebook Hacker Cup and Google Code Jam. I got a second place in Google Code Jam 2018. I am/was nutella in Codeforces and target in Topcoder. Watch me if you want to practice for coding interviews, competitive programming or just algorithms in general. I share my thought process, explain everything, and mention similar problems and techniques/algorithms.