New Queries On Segment Deluxe#13021

New Queries On Segment Deluxe (Editorial)

Author:

Alex Danilyuk

The problem quite clearly asks to implement a persistent segment tree with lazy propagation, except that the operations are a bit weird. For a segment tree to work, you need to merge answers from sons (no problem, just take minimum) and quickly change the answer for a vertex when applying the operation on the whole segment. And while it is not an issue for +=, for := the answer can change quite unpredictably: you need to kinda forget about this row in a matrix and take minimum if we sum all the rows except this one...

After some considerations, it should be clear that we need to expand what is "the answer": we want to store the minimum not only for the sum of all rows but also for all subsets of rows. The details of the implementation are left as an exercise :)

Time and memory complexities are .