高度由习惯堆积

分类 数据结构:单调栈 下的文章

February 17, 2019

51nod1482 部落信号

这是个单调栈的题目题目n个数 ai围成一个环,两个数能看到当且仅当两条路径中一条满足所有数都小于等于这两个数 问有多少对数能互相看见思路一开始想的很简单,是一个n^2的算法,即日常跑一波单调栈,求一求L,R,在枚举每个元素的区间,将这个区间内能与之配对的元素列出来,再统计。然而这样做有一大坨的细节要处理(题目的正解细节往往不多),所以看抄了题解。题解讲的是将此区间内的最大值取出来,再在此处 ...