1. 数据结构-单调栈

单调栈是一种特殊的栈结构，它只允许栈内的元素保持单调性（单调递增或单调递减）。在实际应用中，单调栈常用于解决与单调性相关的算法问题，如找到下一个比当前元素大（或小）的元素、最小区间覆盖问题等。

1.1 单调栈的原理

单调栈的核心思想是维护一个单调递增或递减的栈序列。当新元素入栈时，如果它违反了栈的单调性，就从栈顶开始弹出元素，直到栈顶元素满足单调性条件，然后将新元素压入栈中。

1.2 代码

输出为

注意这里实际上并不是遍历，而是根据单调栈的处理来找的，某个元素出栈表示该元素找到了符合条件的位置

2.实战

2.1 题目

用栈数据结构对给定数组进行处理，找出每个元素右边第一个比它小的元素，并进行多项式计算

2.2 多项式修改问题

MOD = 99887765
N = int(5e6 + 7)

import sys

def main():
    
    input = sys.stdin.read

    data = input().split()
    
    n = int(data[0])
    x = int(data[1])
    
    a = [0] * (n + 2)
    b = [0] * (n + 2)
    
    for i in range(1, n + 2):
        a[i] = int(data[i + 1])
    
    st = []
    ans = 0
    
    for i in range(1, n + 2):
        while st and a[i] < a[st[-1]]:
            b[st[-1]] = a[i]
            st.pop()
        st.append(i)
    
    for i in range(1, n + 2):
        ans = ans * x + b[i]
        ans = (ans % MOD + MOD) % MOD
    
    print(ans)

if __name__ == "__main__":
    main()

END