对单调栈的理解

最常规的无外乎 $O(n)$O(n) 求对于位置 $i$i 求 $a_j<a_i(j<i)$aj​<ai​(j<i) 的最大 $j$j

我们可以这样想：

如果是这样一个单调递增栈我们发现无论 $a_i$ai​ 的变化我们决策始终是栈顶元素，于是栈顶以下的元素全部被包含，是不合理的，不会成为决策点

对于位置 $i$i 求 $a_j<a_i(j<i)$aj​<ai​(j<i) 的最大 $j$j 此时红箭头以上部分不会 $i$i 后面决策点，于是将他们 $pop$pop 掉后 $i$i 会成为新的决策点
但是如果有系数呢，即求 $a_j<ka_i(j<i,k>1)$aj​<kai​(j<i,k>1) 的最大 $j$j

我们依旧可以 $O(n)$O(n) 出解，因为这里我们可以先查询在修改，而对于后面此时 $[j_2,tp]$[j2​,tp] 是没有 $i$i 优的，于是可以先查询 $j_1$j1​ 再到 $j_2$j2​

换一个问题，求 $ka_j<a_i(j<i,k>1)$kaj​<ai​(j<i,k>1) 的最大 $j$j

我们发现此时似乎无法单调，因为你并不能把 $[j_1,tp]$[j1​,tp] 删除完，考虑后面又来了一个查询 $[j_1,j_2]$[j1​,j2​] 是可能作为答案的
但是 $[j_2,tp]$[j2​,tp] 是肯定要删除的，因为此时肯定选 $i$i
此时对于查询我们依旧可以维护单调栈，但是可以变为二分
针对上面2种问题，为什么前一种是 $O(n)$O(n) 而后一种是 $O(nlogn)$O(nlogn) ，发现前一种的查询点总会被此次弹出每次选择栈顶作为决策点，而后一种的查询点不一定在删除点中，要保留，于是决策点不一定是栈顶需要二分。
其实可以 $O(nlogn)$O(nlogn) 处理询问的