Link

Sol

退役人闲得无聊切题,这散兵题目想了好一会儿,还调了好一会儿

这题还是比较套路,可能做法比较多。我有觉得这个名字很奇怪,但是它从来没有让我有这题就用单调栈的提示想法

因为这个栈是跟时序有关系的,可以做到在线的结构应该不多,一般都考虑离线了。

加入一个二元组的时候,满足两个条件中的一种:1. 空栈 2. $\exists p, s.t. a_p = a_i, b_p > b_i$ 让当前这个二元组不能出去。

现在就是要处理这个 $p$ ,可以发现从左到右加进去,对于每个二元组这个 $p$ 都是固定的。题目转换为求满足条件的 $p$ 的个数。直接求出所有的 $p$ ,在它可以弹栈的二元组记一个前缀和。需要一个支持查询区间修的结构,随便什么都行。

Code

不放了,老年人写的狗屎调了万把遍的bo luo 货

最后修改:2022 年 04 月 10 日
如果觉得我的文章对你有用,请随意赞赏