这些知识总算啃掉了...
重要的思路就是加入栈和队列时还要加入元素的坐标位置。
使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。
单调栈就简单点,只有栈顶可以操作，若要找到从左到右第一个比i大的数，就保证严格递减，这样如果到第一个比i大的数是i就会被弹出，总之就是找什么条件的数，第i个数被弹出栈的条件就是什么，建议手打栈，代码如下：
n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { while(top>=1&&a[i]>=q[top].s) ans=ans+i-q[top--].id-1; q[++top].id=i;q[top].s=a[i]; } for(int i=top;i>=1;i--) ans=ans+n-q[top--].id;
单调队列除了tail需要更新，还需要更新head，也就是及时把不符合信息的head出队，、
单调队列性质：
- 1、维护区间最值
- 2、去除冗杂状态 如上题，区间中的两个元素a[i],a[j]（假设现在再求最大值）
若 j>i且a[j]>=a[i] ，a[j]比a[i]还大而且还在后面（目前a[j]留在队列肯定比a[i]有用，因为你是往后推， 核心思想 ! - 其中第二条对动态规划仍使用...
与题目联系时，记得把要求的元素放在队头就行了.
例：
for(int i=1;i<=k;i++) { while(head<=tail&&q[tail].s>=a[i]) tail--; q[++tail].id=i,q[tail].s=a[i]; } mn[++o]=q[head].s; for(int i=k+1;i<=n;i++) { while(head<=tail&&q[tail].s>=a[i]) tail--; q[++tail].id=i,q[tail].s=a[i]; while(q[head].id<=i-k) head++; mn[++o]=q[head].s; }
好，让我们来看这个题：
题目很简单，求连续的长度范围在p到q的最大长度和...
暴力吗？O（n2）...
我们暴力一定会用到前缀和，那我们就要来考虑能不能用前缀和保持单调性做...
#include<bits/stdc++.h> #define ll long long #define max(a,b) (((a)>(b))?(a):(b)) #define min(a,b) (((a)<(b))?(a):(b)) using namespace std; const ll N=101000; ll ans=-1e18,sum[N],n,p,l,head,tail; struct gg { ll id,s; }q[N]; inline ll read() { ll x=0,ff=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } int main() { freopen("1.in","r",stdin); cin>>n>>p>>l; for(register int i=1;i<=n;++i) sum[i]=sum[i-1]+read(); for(register int i=p+1;i<=n;i++) { while(head<=tail&&sum[i-p]<=q[tail].s) --tail; q[++tail].id=i-p;q[tail].s=sum[i-p]; while(head<=tail&&q[head].id<i-l) ++head; ans=max(ans,sum[i]-q[head].s); } cout<<ans<<endl; return 0; }
这个题我们要记住的是范围，也就是说，你每次i向前推进时，你应该把哪些点放到队列里，这里就是把i-p放进去，因为有最小长度的限制，所以
每次枚举i时，我们队列里控制的点范围其实在（i-q，i-p）之间，这样才能保证子序列时合法的子序列...