Luogu P8500. [NOI2022] 冒泡排序

本文讨论了区间相交问题，并提出了三个引理解决该问题。引理一：利用离散化可以方便使用各种数据结构。引理二：对于性质B，未确定的数单调递增。引理三：从左到右扫描时，尽量填更小的值。综上所述，使用线段树记录填数代价，进行区间修改和求最小值。处理区间交得到已填数和未填数的下界数组。对于性质A，1直接填入已填数数组，0从右向左扫描区间，尽可能晚地填数。按权值从大到小挖去每个阶段处理过的位置。