单调栈
题目
定义：一个下标 $i$ 是序列 $a$ 的后缀最大值下标当且仅当对于所有的 $i < j \le |a| $ ，都有 $a_i>a_j$。其中 $|a|$ 表示序列 $a$ 的长度。给出整数 $n$ 和一个长为 $n$ 的序列 $a$，对于每个 $1 \le i \le n$ ，输出 $a_1 \sim a_i$ 所有后缀最大值下标的异或和。
思路
考虑用一个栈来维护当前 $a_1 \sim a_i$ 所有的后缀最大值下标，容易发现栈中的数单调递增（指栈顶到栈底的下标对应的值单调递增）。当遍历到 $i$ 时，如果栈顶存放的下标 $j$ 满足 $a_j>a_i$，则因为栈是单调递增的，栈中的其他下标对应的值均大于 $a_i$，可以正确维护。如果不满足条件则需要不断弹出栈顶直到满足条件。并将 $i$ 入栈，栈中的下标即为后缀最大值下标
Code:
vector<int> stk;
int ans=0;
for(int i=1;i<=n;i++){while(!stk.empty()&&a[stk.back()]<=a[i]){ans^=stk.back();stk.pop_back();}stk.push_back(i);cout<<ans<<" ";
}
复杂度
共有 $n$ 次循环且共执行了 $n$ 次入栈操作，时间复杂度 $O(n)$。
单调栈需要额外空间，空间复杂度 $O(n)$ 。
单调队列
题目
将单调栈的问题稍加变化：给出整数 $n, k$ 和一个长为 $n$ 的序列 $a$，对于每个长度为 $k$ 的区间，输出该区间内所有后缀最大值下标的数量。
思路
这个问题对比上个问题来说多了一个删除过期元素的功能。可以用 STL 中的 deque 双端队列来维护。每次循环开始时先从队首（front）取出过期元素。再按照单调栈的方法维护
单调队列还可以求区间最小/最大值，将新的下标加入队列中后队首的下标就是最值所在的下标
Code
deque<int> q;
int ans=0;
for(int i=1;i<=n;i++){while(!q.empty()&&q.front()<=i-k){ans--;q.pop_front();}while(!q.empty()&&a[q.back()]<=a[i]){ans--;q.pop_back();}q.push_back(i);ans++;if(i>=k)cout<<ans<<" ";
}
复杂度
时间复杂度 $O(n)$
空间复杂度 $O(n)$
例题
P6510 奶牛排队
题意
给定一个长度为 $n$ 的序列 $a$，求出满足区间内 $a_l$ 最小且 $a_r$ 最大的区间 $[l,r]$ 的最大长度。（ $2 \le N \le 10^5$ ）
思路
考虑暴力，枚举右端点 $r$ ，对每个 $r$ 求出符合条件的 $l$ 。时间复杂度 $O(n^2)$ ，对 $10^5$ 的数据显然会超时。
因为 $a_l < a_i$ （ $l < i \le r$ ），所以 $l$ 一定是 $1 \sim r$ 的后缀最小值。又因为 $l \sim r$ 中 $a_r$ 最大，即这段区间不能有任何一个数比 $a_r$ 大。可以二分求出 $l$ 的值。
用单调栈 $s1$ 和 $s2$ 分别维护后缀最大值和最小值，每次循环时在 $s2$ 上二分找出第一个大于 $s1.back()$ （即栈顶）的下标，更新答案。时间复杂度 $O(n \log n)$ 。
Code
#include<bits/stdc++.h>
using namespace std;
int main(){int n; cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++)cin>>a[i];vector<int> s1,s2;int ans=0;for(int r=1;r<=n;r++){while(s1.size()&&a[s1.back()]<=a[r])s1.pop_back();while(s2.size()&&a[s2.back()]>=a[r])s2.pop_back();auto l=upper_bound(s2.begin(),s2.end(),s1.back());if(l!=s2.end())ans=max(ans,r-*l+1);s1.push_back(r);s2.push_back(r);}cout<<ans;return 0;
}
P13889 子矩阵
题意
有一个 $n \times m$ 个整数组成的矩阵，求所有大小为 $a \times b$ 的子矩阵中最大值与最小值的乘积的和。
思路
考虑暴力做法，先找出每个子矩形，再计算最小值和最大值，统计答案，时间复杂度 $O(nmab)$ ，显然不能通过本题。
我们可以使用单调队列进一步优化，对于输入的 $n \times m$ 的矩阵，我们可以把每一行看作一个单独的数列，对其求出它的每个长度为 $b$ 的子段的区间最大值，易得出这样的最大值有 $n \times (m-b+1)$ 个，将每行的最大值构成新矩阵 $mx1$ 的一行，则 $mx1$ 的大小是 $n \times (m-b+1)$ 。
对新矩阵，再将它的每一列看作一个单独的数列，求出这一列上每个长度为 $a$ 的子段的区间最大值，存到另一个矩阵 $mx2$ 中， $mx2$ 的大小就是 $(n-a+1) \times (m-b+1)$ 。最小值同理。
经过这一步，我们可以得出两个存储原矩阵的子矩阵最值的矩阵，最后统计答案即可。
Code
#include<bits/stdc++.h>
using namespace std;int main(){int n,m,a,b; cin>>n>>m>>a>>b;vector<vector<int>> c(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];}}vector<vector<int>> mx1(n+1,vector<int>(m-b+2)),mn1(n+1,vector<int>(m-b+2));vector<vector<int>> mx2(n-a+2,vector<int>(m-b+2)),mn2(n-a+2,vector<int>(m-b+2));for(int i=1;i<=n;i++){deque<int> q;for(int j=1;j<=m;j++){while(q.size()&&q.front()<j-b+1)q.pop_front();while(q.size()&&c[i][q.back()]<=c[i][j])q.pop_back();q.push_back(j);if(j>=b)mx1[i][j-b+1]=c[i][q.front()];}}for(int j=1;j<=m-b+1;j++){deque<int> q;for(int i=1;i<=n;i++){while(q.size()&&q.front()<i-a+1)q.pop_front();while(q.size()&&mx1[q.back()][j]<=mx1[i][j])q.pop_back();q.push_back(i);if(i>=a)mx2[i-a+1][j]=mx1[q.front()][j];}}for(int i=1;i<=n;i++){deque<int> q;for(int j=1;j<=m;j++){while(q.size()&&q.front()<j-b+1)q.pop_front();while(q.size()&&c[i][q.back()]>=c[i][j])q.pop_back();q.push_back(j);if(j>=b)mn1[i][j-b+1]=c[i][q.front()];}}for(int j=1;j<=m-b+1;j++){deque<int> q;for(int i=1;i<=n;i++){while(q.size()&&q.front()<i-a+1)q.pop_front();while(q.size()&&mn1[q.back()][j]>=mn1[i][j])q.pop_back();q.push_back(i);if(i>=a)mn2[i-a+1][j]=mn1[q.front()][j];}}long long ans=0;long long mod=998244353;for(int i=1;i<=n-a+1;i++){for(int j=1;j<=m-b+1;j++){ans=(ans+(mx2[i][j]*1LL*mn2[i][j]%mod))%mod;}}cout<<ans;return 0;
}