单调栈二分CF 92D

题目链接解析

https://codeforces.com/problemset/problem/92/D

题意

对于给定的n个数值，需要确定每个数值之后最远的那个比它小的数值与它的位置间距减去1，若不存在则标记为-1。

思路

针对该问题，若从后向前进行分析，对于ai与aj这两个元素，当i小于j但ai大于aj时，显然ai无法带来更优的解。因为其无法超越aj所具备的优势。因此，在从后往前处理时，应维护一个递减的单调栈结构。若当前数值小于栈顶元素，则将其压入栈中，并将对应答案设为-1；反之，依据上述分析可知，该数值不会对最终结果产生更优的影响，此时可直接采用二分查找的方式获取其对应答案，无需将其压入栈中。

经验总结与反思

单调栈与单调队列这两种数据结构的关键特征在于其单调性。在进行入栈或入队操作时，通常遵循从前向后或从后向前的顺序，通过借鉴类似的分析思路，可以判断是否存在单调特性，从而考虑应用这两种数据结构。

代码

    #include<cstdio>
    #include<iostream>
    #include<iomanip>
    #include<map>
    #include<unordered_map>
    #include<string>
    #include<queue