Loading... [Link](https://www.luogu.com.cn/problem/P8251) ## 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 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用,请随意赞赏
3 条评论
tony/se/se/se
托老师爆切我不会的神仙题
托老师爆切我不会神仙题