Hello everyone, meet again, I am your friend Quanzhanjun.
First, the concept of monotonic queue:
A monotonic queue, that is, a queue that is monotonically decreasing or monotonically increasing.
Second, the properties of monotonic queues:
1. The position of the elements in the queue in the original list is from front to back (with the circular order enqueued).
2. The size of the elements in the queue is monotonically increasing or decreasing.
Third, the characteristics of monotonic queue:
Enqueue from the end of the queue, dequeue from the head or tail of the queue.
Four, example analysis:
So what is the use of monotonic queue? Monotonic queues are generally used to find the maximum value in an interval. Read a few questions to understand the above:
1. Luogu P1886 sliding window: https://www.luogu.org/problemnew/show/P1886
It doesn't look very difficult, two for loops are done, but you must know that the time complexity of such an algorithm is o(n^2), and the data given by the title will definitely time out. What we want is an algorithm with a time complexity of o(n). Look at the code:
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int m[N]; //Used to store the maximum value sequence
struct node{ //The node of the queue, containing the original position and value of the element in the list
int order;
int value;
}tmp;
deque<node>maxn,minn; //Define the node type monotonic queue, record the maximum and minimum values in the area respectively
int main()
{
int n,k,t; //n,k as the meaning in the title, t is used to temporarily store the input
int m_lo=0; //Maximum sequence subscript
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&t);
if(!maxn.empty() && i-maxn.front().order>=k) maxn.pop_front(); //The principle part of monotonic queue
if(!minn.empty() && i-minn.front().order>=k) minn.pop_front(); //See below for details
while(!maxn.empty() && maxn.back().value<t) maxn.pop_back();
while(!minn.empty() && minn.back().value>t) minn.pop_back();
tmp.value=t; //Node enqueue
tmp.order=i;
maxn.push_back(tmp);
minn.push_back(tmp);
if(i>=k-1) //When the length of the interval required by the question is reached, the minimum value sequence is output and the maximum value sequence is stored.
{
if(i==n-1) printf("%d\n",minn.front().value);
else printf("%d ",minn.front().value);
m[m_lo++]=maxn.front().value;
}
}
for(int i=0;i<m_lo;i++) //output max sequence
{
if(i==m_lo-1) printf("%d\n",m[i]);
else printf("%d ",m[i]);
}
}Explanation: This question asks for the maximum and minimum values in an interval. For an element in the array, we only need to care about itself and its first k-1 numbers.
So how to use queue processing? Let’s briefly talk about the idea of solving the problem, taking the minimum value as an example: at the beginning, the index i of the array is 0, we keep putting elements into the queue, and keep the first element of the queue at the minimum value until the kth number, At this time, the first element of the queue is the minimum value of the first k numbers. Then we output the leader of the team. Continue to go down, in the process of walking, kick out the numbers whose subscripts in the queue exceed the range of (i-k+1)~i, continue to keep the first element of the team as the minimum value in the interval, and then output the first element of the team.
To sum up briefly, for each loop, what we have to do is: first kick off the elements that are beyond the range, put in the elements and ensure that the head of the team is the minimum value of the current range in the array, output the head of the team, and go back and forth. What is stored in the queue is the sequence of monotonically increasing minimum values in the interval before the element is placed.
So we have two problems to solve:
1. How to remove elements that are beyond the range: This is the role of the node node in the code. The node node stores the subscript of the original array. For the i-th number of each new input, because the element position in the monotonic queue is the same as before. After that, we only need to judge the node.order and i of the first element of the team to see if i-node.order>=k at this time, and then let the first element of the team dequeue.
2. How to ensure that the element at the head of the queue is the minimum value in the interval: For a certain interval, every time we enter a number, we will see if the value of the element at the end of the queue is greater than it, and dequeue this element until the queue is empty or The value of the element at the end of the queue is smaller than this number, and then we put this number in. At this time, the element at the head of the queue is the minimum value of the interval, and it can be output.
Rationality analysis: Starting from the queue being empty, we put in the 0th number until k-1. Every time the input value is smaller than the current input value, the queue tail value is dequeued. It is easy to know the head of the queue at this time. It is the minimum value of [0,k-1]. Then enter the kth number next, and it is certain that the minimum value of the interval [1,k] is related to the minimum value of [0,k-1]. There are two cases, one is that the minimum value of [1,k] comes from the number in front of k, in this case, we look at the case of [0,k-1], if the minimum value of [0,k-1] comes from The 0th bit means that there must be elements other than the 0th element in the queue, that is, there must be a minimum sequence of [1,k-1] in the queue, and they are monotonically increasing. At this time, since the 0th digit is out of the range of the interval, it is dequeued, which does not affect the search for the minimum value of the interval [1,k]. If the minimum value of [0,k-1] comes from [1,k-1], it will naturally not affect the search for the minimum value of [1,k]. The second is that the minimum value is k, then the operation can be performed to clear the queue, and then put it in. At this time, the head of the queue is k, which is the minimum value. The same is true for the general case.
Points to note:
1. When writing if and while, you must first write to determine whether the queue is empty, otherwise an overflow operation will be performed in if and while.
2. There is no definite relationship between judging whether the leader of the team is out of the queue and the length of the queue, because the queue does not necessarily contain the elements of the entire range.
3. It is possible to remove or not to remove duplicate elements. Removal can ensure that there is at least one in the queue. If it is not removed, it will not affect the head of the queue, and it will be dequeued when it encounters a smaller value.
4. This algorithm has only one for loop, and each element enters and exits only once, so the time complexity is o(n).
2. P1440 finds the minimum value in the m interval: https://www.luogu.org/problemnew/show/P1440
The title of this question may not be very clear, look at the example: the minimum value of the first two numbers of 4 is 1, and the minimum value of the first two numbers of 3 is also 1.
This question is basically the same as the previous question, the difference is that this time the window does not include the current element, that is, the current element does not participate in the comparison, and the previous result can be output every time the loop is performed.
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int a[N];
struct node{
int order;
int value;
}tmp;
deque<node>vis;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
tmp.order=i;
tmp.value=a[i];
if(i==0) printf("%d\n",0);
else printf("%d\n",vis.front().value);
if(i-vis.front().order>=m) vis.pop_front();
while(!vis.empty() && vis.back().value>a[i]) vis.pop_back();
vis.push_back(tmp);
}
}3. P2032 scan: https://www.luogu.org/problemnew/show/P2032
Template questions, write directly:
#include <bits/stdc++.h>
using namespace std;
struct node{
int order;
int value;
}tmp;
deque<node>vis;
int main()
{
int n,k,t;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&t);
if(!vis.empty() && i-vis.front().order>=k) vis.pop_front();
while(!vis.empty() && vis.back().value<t) vis.pop_back();
tmp.order=i;
tmp.value=t;
vis.push_back(tmp);
if(i>=k-1)
{
printf("%d\n",vis.front().value);
}
}
}4. P1714 Cut the cake: https://www.luogu.org/problemnew/show/P1714
At first glance, this question seems to be able to be done with a ruler, but it is not, because there is no way to go back after moving the left and right pointers.
So how do you use a monotonic queue for this problem? The first thing to do is to transform the problem into a problem of subtracting all elements at the current position and subtracting the first x elements and the maximum value. To get the max, just take the first x elements and the min. Then we replace each bit of the array with the sum from 0 to the current position, use the monotonic queue to find the minimum value of the element before the current element, and then subtract the minimum value from the current element value, and compare each time.
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],sum[N];
struct node{
int order;
int value;
}tmp;
deque<node>vis;
int main()
{
int n,m;
int ans;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(i==0) sum[0]=a[i];
else sum[i]=sum[i-1]+a[i];
if(!vis.empty() && i-vis.front().order>m) vis.pop_front(); //Note that > , understand by yourself
while(!vis.empty() && vis.back().value>sum[i]) vis.pop_back();
tmp.value=sum[i];
tmp.order=i;
vis.push_back(tmp);
if(i==0) ans=sum[i]-vis.front().value;
else if(i<m) ans=max(ans,sum[i]);
else ans=max(ans,sum[i]-vis.front().value);
}
printf("%d\n",ans);
}5. P1725 Cirno: https://www.luogu.org/problemnew/show/P1725
This question is estimated to have bugs when the question is asked, but don't worry about it, because the data is given according to the method with bugs.
First of all, this is a dp question. The state transition equation is dp[i]=max(dp[x])+a[i]; where (i-r)<=x<=(i-l);
Since the maximum value in the interval dp[i-r]~dp[i-l] is required, a monotonic queue is used.
The loop starts directly from l, because the position before l cannot be reached, and the dp value is all 0.
The monotonic queue needs to maintain the maximum value of dp (note that it is not a), and the lower limit of the interval to be maintained differs from i by l (this is the reason for defining j), and the fixed length of the interval is r-l+1.
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],dp[N];
struct node{
int order;
int value;
}tmp;
deque<node>vis;
int main()
{
int n,l,r;
scanf("%d%d%d",&n,&l,&r);
for(int i=0;i<=n;i++) scanf("%d",&a[i]);
for(int i=0;i<l;i++) a[i]=0; //It is impossible to go from 0 to l-1, so change the value to 0
for(int i=n+1;i<=n+r;i++) a[i]=0;
int j=0; //j is the subscript of the element to be maintained
for(int i=l;i<=n+r;i++)
{
if(!vis.empty() && j-vis.front().order>=r-l+1) vis.pop_front();
while(!vis.empty() && vis.back().value<dp[j]) vis.pop_back();
tmp.order=j;
tmp.value=dp[j];
vis.push_back(tmp);
dp[i]=vis.front().value+a[i];
j++;
}
int ans=-9999999;
for(int i=n+1;i<=n+r;i++)
{
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}6. P2629 Good news, bad news: https://www.luogu.org/problemnew/show/P2629
This question also uses the sum of elements. The idea is to copy a and put it at the end of the array, then slide a window of size n, find the minimum value in the window, and subtract the sum of the values in front of the window to see if it is greater than or equal to 0.
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int a[N],sum[N];
struct node{
int order;
int value;
}tmp;
deque<node>vis;
int main()
{
int n,k,ans;
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
if(i==0) sum[i]=a[i];
else sum[i]=sum[i-1]+a[i];
}
for(int i=n;i<2*n;i++) sum[i]=sum[i-1]+a[i];
k=0; //k is used to record the position index before the window
ans=0;
for(int i=0;i<2*n-1;i++)
{
if(!vis.empty() && i-vis.front().order>=n) vis.pop_front();
while(!vis.empty() && vis.back().value>sum[i]) vis.pop_back();
tmp.order=i;
tmp.value=sum[i];
vis.push_back(tmp);
if(i==n-1 && vis.front().value>=0) ans++;
else if(i>n-1 && vis.front().value-sum[k]>=0) ans++;
if(i>n-1) k++;
}
cout<<ans<<endl;
}7. P2422 Good feeling: https://www.luogu.org/problemnew/show/P2422
The idea of this question is to find the maximum range that can be contained in the array a with each a[i] as the minimum value (because all values are greater than 0, so in the case of the minimum value of a[i] , it is necessary to make the range of the interval [i,j] as large as possible, so that the sum of a[i] times the elements in the interval is the largest), and then compare the product of each a[i] and the sum of the elements in the corresponding interval. It lies in the search of the interval range.
In this problem, the role of the monotonic queue is to construct a monotonically increasing sequence of a. For each element in the queue, if it is smaller than the tail element of the queue, it means that the lower limit of the range of the tail element has been determined, that is, the tail element itself, and the upper limit of the range of the tail element is the previous number of the tail element in the queue, the sum value of the lower limit and The sum value of the upper limit is subtracted to obtain the sum of the elements of the largest interval that can be included when a[i] is the minimum value. Refer to the code for other special cases.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e6+5;
LL a[N],sum[N],multi[N];
struct node{
LL order;
LL value;
}tmp;
deque<node>vis;
int main()
{
LL n,lo,bef,aft,ans;
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
if(i==0) sum[i]=a[i];
else sum[i]=sum[i-1]+a[i];
}
a[n]=0; //This is very important, otherwise the queue cannot be emptied when the last number is reached
for(int i=0;i<=n;i++) //Note that <=, the reason is the same as above
{
while(!vis.empty() && vis.back().value>a[i])
{
lo=vis.back().order;
aft=i-1;
vis.pop_back();
if(!vis.empty()) bef=vis.back().order;
else bef=-1;
if(bef==-1) multi[lo]=sum[aft];
else multi[lo]=sum[aft]-sum[bef];
}
tmp.order=i;
tmp.value=a[i];
vis.push_back(tmp);
}
ans=-1;
for(int i=0;i<n;i++)
{
ans=max(ans,multi[i]*a[i]);
}
cout<<ans<<endl;
}Publisher: Full stack programmer, please indicate the source: https://javaforall.cn/152990.html Original link: https://javaforall.cn