保序回归问题在序列上的特殊做法

LG P4331 [BalticOI 2004]Sequence 数字序列
远古论文题。


所以就可以单调栈维护区间的$L_p$均值，如果前面的均值比后面大则合并区间。
最后单调栈中的区间的$L_p$均值就是一个可行方案。

注意$L_2$等均值是可以$O(1)$求的，比如上面的论文。
但是$L_1$的均值是中位数，还得写可并堆，这种情况真的罕见。

再来一道例题：
2020 Petrozavodsk Winter Camp, Jagiellonian U Contest C - Bookface
真的离谱，2020年还出2004年的板题。
可并堆并不是总能维护中位数，在这题中使用时因为这题如果前一个区间的中位数大于后一个则直接合并的性质，可以证明如果维护的是大根堆在前后合并的时候后一个区间中不存在已经被删了还小于前一个区间的中位数的数（如果存在那么早合并了。），所以单调不降需要用大根堆才能过，单调不升则需要用小根堆。