单调栈 单调队列 尺取法

单调栈：

1：包含长度覆盖问题：C. Paint - 上海市大学生程序设计竞赛 - 十二月赛 - ECNU Online Judge

2：区间求以该元素为最值的区间范围，求最大值就维护单调增栈，出栈时就代表该元素为最大值的右边界为此。

反向再求一遍即可得到左右边界。

求最小值时就维护单调减栈。

参考实现：

        stack<int>s;
        for(int i=1;i<=n;i++){
        	r[i]=n+1;
            while(!s.empty()&&a[s.top()]<a[i]){
            	r[s.top()]=i;
				s.pop();
            } 
            s.push(i);
        }

例题：

​​​​​​CodeCraft-22 and Codeforces Round #795 (Div. 2) D. Max GEQ Sum（单调栈+区间最值）_Jack_00_的博客-CSDN博客

单调队列： 

适合求滑动窗口型最值，也常见于dp最值转移时优化。

单调队列-原理详解(deque实现)_Gaoithe的博客-CSDN博客_单调队列

尺取法： 

像是满足区间某种信息的l->r里的高效枚举：

Wannafly模拟赛3 牛客练习赛3 E-绝对半径2051（尺取法 离散化 二分）_Jack_00_的博客-CSDN博客

树网的核加强版 (树的直径 尺取法 思维)_Jack_00_的博客-CSDN博客