#2020寒假集训#单调队列与单调栈入门（Humdrum Queue and Monotonic stack）代码笔记
单调队列
洛谷-P1886 滑动窗口 /【模板】单调队列
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
int n,k,put[maxn],que[maxn],Min[maxn],Max[maxn],pos[maxn];
//此队列是象形意义，可用que[maxn]数组在队尾进行操作,或用deque双端队列写
void get_min()//维护单增队列,得最小值
{
int head=1,tail=0;//分别是头下标 and 尾下标
for(int i=1;i<=n;++i)//遍历 n 个数
{
while(head<=tail&&que[tail]>=put[i]) --tail;
/*
队列非空，且尾元素 >= 当前被遍历到的数
则那时的尾元素不再可能是最小值，--tail弹出尾元素
*/
que[++tail]=put[i];//只插入更大的，维护递增（相等的也弹出再插入，以防重复）
/*
直到队列为空，或者前面的元素已经小于现在遍历到的元素
将现在被遍历到的元素塞入队列
++tail先自加后赋值，保证tail值和下标一致
*/
pos[tail]=i;
/*
用 pos 数组记录队尾实际下标
其实，当 tail 为 1 的时候，相对于后续产生为 2 为 3 的tail
1 的时候就是队首，pos[1]记录的就是队首的实际下标
后续用于pos[head]比较判断，队首元素是否在滑动窗口内
*/
if(i<k) continue;
/*
如果刚开始遍历的元素个数还不足窗口长度
那维护的单增队列队首，还不一定是窗口内的最小值
可能到第 k 个就有更小的了，所以得先遍历完k个
之后窗口一格一格滑动，不受影响
*/
while(pos[head]<i-k+1) ++head;
/*
队列的大小超过了窗口值，即队首元素实际下标比窗口起始下标小
i-k+1即为窗口起始下标
例如，i 为 9；k 为 3；i>=k开始才有这步
访问到 i==3 的元素时，能找出第 1-3 个元素的最小值
此时，i-k+1==1，确为起始下标
之后每访问一次新的 i，无论其是否入队
队内至少有一个，第 1 到 i 内的最小元素（也印证了上述 i>=k 开始不受影响）
若队内有多个元素，可能队首元素实际下标小于 i-k+1 是之前的最小值，需弹出队首元素
要注意，新元素小于等于队尾元素，会弹出尾元素自己入队，满足窗口范围
新元素大于队尾元素，会直接插入在队尾
无论如何，最新的元素一定在队伍里，不会出现没有一个元素满足窗口范围的情况
*/
Min[i-k+1]=que[head];
}
}
void get_max()//维护单减队列，得最大值
{//（注释与get_min()函数同理）
int head=1,tail=0;
for(int i=1;i<=n;++i)//遍历 n 个数
{
while(head<=tail&&que[tail]<=put[i]) --tail;
/*
队列非空，且尾元素 <= 当前被遍历到的数
则那时的尾元素不再可能是最大值，--tail弹出尾元素
*/
que[++tail]=put[i];//只插入更小的，维护递减（相等的也弹出再插入，以防重复）
pos[tail]=i;
if(i<k) continue;
while(pos[head]<i-k+1) ++head;
Max[i-k+1]=que[head];
}
}
void print()
{
//一共 n 个数，窗口长度为 k，会有 n-k+1 种窗口位置，即每行会有 n-k+1 个答案
for(int i=1;i<=n-k+1;++i) printf("%d%c",Min[i],i==n-k+1?'\n':' ');
for(int i=1;i<=n-k+1;++i) printf("%d%c",Max[i],i==n-k+1?'\n':' ');
}
int main()
{
while(~scanf("%d %d",&n,&k))//输入元素个数和滑动窗口的长度
{
for(int i=1;i<=n;++i) scanf("%d",&put[i]);
get_min();
get_max();
print();
}
return 0;
}
单调栈
洛谷-P5788 【模板】单调栈
#include<stdio.h>
#include<string.h>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=3e6+10;
int n,Index[maxn];
struct num
{//如果不用记录其他相关信息，则定义一个整型put即可
int digit;
int id;
}put;
stack<num> st;
void get_bigger()
{
for(int i=1;i<=n;++i)
{
scanf("%d",&put.digit);
put.id=i;
while(!st.empty()&&st.top().digit<put.digit)
{//维护的是单调递增栈
Index[st.top().id]=i;
/*
记录对于栈顶元素来说，第一个比它大，让它出栈的put
这个put的id就是栈顶元素id对应的其后第一个大于它的数
因为记录必须是大于，所以栈顶元素digit之后小于当前put的才操作
即当前put的digit得更大才记录并操作pop，等于的时候入栈即可
不会出现同digit用st.top().id时乱套的情况
因为每一个被push进st栈的put都是独一无二的
*/
st.pop();
}
st.push(put);
}
}
int main()
{
while(~scanf("%d",&n))
{
memset(Index,0,sizeof(Index));
get_bigger();
for(int i=1;i<=n;++i) printf("%d%c",Index[i],i==n?'\n':' ');
}
}
例题（单调队列-维护更新次数）
HDU-6319-Problem A. Ascending Rating
Description
Before the start of contest, there are n ICPC contestants waiting in a long queue. They are labeled by 1 to n from left to right. It can be easily found that the i-th contestant’s QodeForces rating is ai.
Little Q, the coach of Quailty Normal University, is bored to just watch them waiting in the queue. He starts to compare the rating of the contestants. He will pick a continous interval with length m, say [l,l+m−1], and then inspect each contestant from left to right. Initially, he will write down two numbers maxrating=−1 and count=0. Everytime he meets a contestant k with strictly higher rating than maxrating, he will change maxrating to ak and count to count+1.
Little T is also a coach waiting for the contest. He knows Little Q is not good at counting, so he is wondering what are the correct final value of maxrating and count. Please write a program to figure out the answer.
Input
The first line of the input contains an integer T(1≤T≤2000), denoting the number of test cases.
In each test case, there are 7 integers n,m,k,p,q,r,MOD(1≤m,k≤n≤107,5≤p,q,r,MOD≤109) in the first line, denoting the number of contestants, the length of interval, and the parameters k,p,q,r,MOD.
In the next line, there are k integers a1,a2,…,ak(0≤ai≤109), denoting the rating of the first k contestants.
To reduce the large input, we will use the following generator. The numbers p,q,r and MOD are given initially. The values ai(k<i≤n) are then produced as follows :
It is guaranteed that ∑n≤7×107 and ∑k≤2×106.
Output
Since the output file may be very large, let’s denote maxratingi and counti as the result of interval [i,i+m−1].
For each test case, you need to print a single line containing two integers A and B, where :
Note that ``⊕’’ denotes binary XOR operation.
Sample Input
1
10 6 10 5 5 5 5
3 2 2 1 5 7 6 8 2 9
Sample Output
46 11
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=7e7+10;
long long T,n,m,k,p,q,r,mod,put[maxn],que[maxn],pos[maxn],ans1,ans2;
/*
求count要从后往前遍历维护的单调递减队列
倒回来就是区间内的递增
区间内的元素个数，便是该区间最大值的更新次数
从后往前遍历的意义在于
对于原序列而言，排在后面的元素如果较小，应当丢弃（出队）
排在前面的元素如果较小，在没到后面前，成为过最大值
但若从前往后遍历，若要找最大值，维护单减
所入队的较小值是后面较小的数，前面较小的会被丢弃（出队）
而实际一个个区间判断的时候是从前往后，前面较小的才有用
*/
void get_answer()
{
long long head=1,tail=0;
for(int i=n;i>=1;--i)
{
while(head<=tail&&que[tail]<=put[i]) --tail;
que[++tail]=put[i];
pos[tail]=i;
if(i>n-m+1) continue;
while(pos[head]>i+m-1) ++head;
//队首下标出界，即正序序列的尾元素超出了区间尾部
ans1+=que[head]^i;//最大值统计
ans2+=(tail-head+1)^i;//计数统计
}
}
int main()
{
scanf("%lld",&T);
while(T--)
{
ans1=0,ans2=0;
scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&m,&k,&p,&q,&r,&mod);
for(long long i=1;i<=k;++i) scanf("%lld",&put[i]);
for(long long i=k+1;i<=n;++i) put[i]=(p*put[i-1]%mod+q*i%mod+r%mod)%mod;
get_answer();
printf("%lld %lld\n",ans1,ans2);
}
return 0;
}
例题（单调栈-直方图中最大连续矩形面积）
POJ-2559Largest Rectangle in a Histogram
Description
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,…,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
Output
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000
Hint
Huge input, scanf is recommended.
#include<stdio.h>
#include<string.h>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
long long n,ans,left[maxn],right[maxn];
struct num
{
long long digit;
long long id;
}put[maxn];
stack<num> st;
void get_left()//左边不比自己矮的连续几个
{
for(long long i=1;i<=n;++i)
{
while(!st.empty()&&st.top().digit>=put[i].digit)
{
left[i]=max(left[i],left[st.top().id]+i-st.top().id);
st.pop();
}
st.push(put[i]);
}
}
void get_right()//右边不比自己矮的连续几个
{
for(long long i=n;i>=1;--i)
{
while(!st.empty()&&st.top().digit>=put[i].digit)
{
right[i]=max(right[i],right[st.top().id]+st.top().id-i);
st.pop();
}
st.push(put[i]);
}
}
int main()
{
while(~scanf("%lld",&n)&&n)
{
for(long long i=1;i<=n;++i)
{
scanf("%lld",&put[i].digit);
put[i].id=i;
}
memset(left,0,sizeof(left));
memset(right,0,sizeof(right));
while(!st.empty()) st.pop();
get_left();
while(!st.empty()) st.pop();
get_right();
ans=0;
for(int i=1;i<=n;++i)
{
long long sum=(left[i]+right[i]+1)*put[i].digit;
ans=max(ans,sum);
}
printf("%lld\n",ans);
}
}
例题（单调栈-01矩阵每行以上化直方图-上题升级）
POJ-3494-Largest Submatrix of All 1’s
Description
Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.
Input
The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 2000) on line. Then come the elements of a (0,1)-matrix in row-major order on m lines each with n numbers. The input ends once EOF is met.
Output
For each test case, output one line containing the number of elements of the largest submatrix of all 1’s. If the given matrix is of all 0’s, output 0.
Sample Input
2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
Sample Output
0
4
#include<stdio.h>
#include<string.h>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int n,m,cnt[maxn],ans,num,left[maxn],right[maxn];
struct number
{
int digit;
int id;
}put[maxn];
stack<number> st;
void get_left()//左边不比自己矮的连续几个
{
for(int i=1;i<=m;++i)
{
while(!st.empty()&&st.top().digit>=put[i].digit)
{
left[i]=max(left[i],left[st.top().id]+i-st.top().id);
st.pop();
}
st.push(put[i]);
}
}
void get_right()//右边不比自己矮的连续几个
{
for(int i=m;i>=1;--i)
{
while(!st.empty()&&st.top().digit>=put[i].digit)
{
right[i]=max(right[i],right[st.top().id]+st.top().id-i);
st.pop();
}
st.push(put[i]);
}
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&num);
put[j].id=j;
if(num) put[j].digit++;
else put[j].digit=0;
}
memset(left,0,sizeof(left));
memset(right,0,sizeof(right));
while(!st.empty()) st.pop();
get_left();
while(!st.empty()) st.pop();
get_right();
for(int j=1;j<=m;++j)
{
int sum=(left[j]+right[j]+1)*put[j].digit;
cnt[i]=max(cnt[i],sum);
}
}
ans=0;
for(int i=1;i<=n;++i) ans=max(ans,cnt[i]);
printf("%d\n",ans);
}
}
小贴士
入队入栈也可让下标入
put数组作输入数组的话，比较和赋值部分，可用put[que[tail]]单调队列/put[st.top()]单调栈等
例如（以单调队列为例-可参照上文例题的AC代码比较）
while(head<=tail&&put[que[tail]]<=put[i]) tail--;
que[++tail]=i;
while(que[head]>i+k-1) head++;