1.26单调队列

单调队列

单调队列，顾名思义，队内元素是单调的

增减性可以自行定义，但最后访问队首元素都是所求区间的最值

这里以单调递减队列为例

对于当前元素，先与队尾元素比较，如果队尾元素更小，那么直接删除队尾元素，一直删除直到队尾元素比当前元素大或者队列为空

这样就能保证他的单调性

对于他的维护，我们以例题来说明

传送门~

这样移动的区间，要想维护一个合法的单调队列，我们需要额外记录每个元素对应的下标，也就是他的id

在开始的时候进行一次预处理，处理前w个，接着再不断进行移动，弹出队首不合法的元素，在队尾加入元素，最后得到合法的队列，输出队首元素即可

#include
#include
#include
using namespace std;
const int N = 1e6+5;
int n,w,a[N],q[N],id[N];
void mi(){
    int st = 0,ed = 0;
    for(int i=1;i<=w;++i){//预处理
        while(st < ed && q[ed] > a[i])ed--;
        ed++;
        q[ed] = a[i];
        id[ed] = i;
    }
    for(int i=w+1;i<=n;++i){
        while(st < ed && id[st+1] < i - w)st++;//当前区间为[i-w,i];
        printf("%d ",q[st+1]);//O(1)访问
        while(st < ed && q[ed] > a[i])ed--;//不合法的弹出去
        ed++;
        q[ed] = a[i];//插入当前元素
        id[ed] = i;
    }
    while(st < ed && id[st+1] < n+1-w)st++;//处理最后一组
    printf("%d\n",q[st+1]);
}
void ma(){
    memset(q,0,sizeof(q));
    memset(id,0,sizeof(id));
    int st = 0, ed = 0;
    for(int i=1;i<=w;++i){
        while(st < ed && q[ed] < a[i])ed--;
        ed++;
        q[ed] = a[i];
        id[ed] = i;
    }
    for(int i=w+1;i<=n;++i){
        while(st < ed && id[st+1] ;
        printf("%d ",q[st+1]);
        while(st < ed && q[ed] < a[i])ed--;
        ed++;
        q[ed] = a[i];
        id[ed] = i;
    }
    while(st < ed && id[st+1] < n+1-w)st++;
    printf("%d",q[st+1]);
}
int main(){
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    mi();ma();
}

单调队列进阶应用

非负和

题目描述：对于给定的n个元素，a1，a2 ......an-1， an 有如下变换：

ai，ai+1 ...... ，an-1，an，a1，a2 .......ai-2，ai-1

显然，我们可以得到n个这样的数列。试求出，有多少个这样的变换后的数列可以满足从第一项到任意一项的和非负。

对于这样的多次求和问题，我们不难想到做一个前缀和，由于是环状的，我们可以直接将数组翻倍，存两边，前缀和一直维护到2*n，

可以看到，现在问题转化成了，对于长度为n的一个子集，求其中前缀和的最小值，而且需要一直往右推，这不是就和刚才的滑动窗口一样？！

接下来只需维护单调队列不断比较即可

#include
#include
#include
using namespace std;
const int N = 1e6+5;
int ans,q[N*2],id[N*2],s[N*2],x[N*2],n;
void mi(){
    int st = 0,ed = 0;
    for(int i=2;i<=n+1;++i){
        while(st < ed && q[ed] > s[i])ed--;
        ed++;
        q[ed] = s[i];
        id[ed] = i;
    }
    for(int i=n+2;i<=n*2;++i){
        while(st < ed && id[st+1] < i - n)st++;
        if(s[i-n-1] - q[st+1] >= 0)ans++;
        while(st < ed && q[ed] > s[i])ed--;
        ed++;
        q[ed] = s[i];
        id[ed] = i;
    }
    while(st < ed && id[st+1] <= n)st++;
    if(s[n] - q[st+1])ans++;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&x[i]);
        x[i+n] = x[i]
        ;s[i] = s[i-1] + x[i];
    }
    for(int i=n+1;i<=n*2;++i){
        s[i] = s[i-1] + x[i];
    }
    mi();
    printf("%d",ans);
}

相关

标签