Недавно я встретил задачу 2046D - For the Emperor!, которая напомнила мне про существование L-R потоков. Я их узнал очень давно, да и в тот момент задачи помимо "просто напиши L-R поток" нам не дали, так что я не запомнил алгоритм и мне пришлось узнать его заново, уже более детально. К сожалению блога на кфе, который бы всё понятно объяснил, не было, так что пришлось лазить по всяким другим ресурсам. Я нашёл их тут, примерно понял идею, потом пришлось смотреть реализацию, у меня к ней остались вопросы, я воспринимал немного как чёрный ящик. Но сегодня в 3 часа ночи мне пришло озарение и я всё понял. Чтобы тем 5 людям, которые прочитают мой блог, не пришлось его ждать, я хочу тут разъяснить моё понимание этого алгоритма и как его удобно писать.

Что такое вообще L-R поток?