2020牛客NOIP赛前集训营-普及组(第一场)D-牛牛的滑动窗口

牛牛的滑动窗口

https://ac.nowcoder.com/acm/contest/7604/D

牛牛的滑动窗口

  • 前言

    我严重怀疑这道题来错地方了QwQ,看题解和代码看了半天

  • 分析

    首先是暴力的n^2滑动窗口做法,枚举区间长度,然后做两次单调队列求极值,求出答案

    int n,m;
    int q1[N],q2[N],a[N],b[N];
    inline void min_deque()
    {
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q1[h]+m<=i) h++;
        while(h<=t&&a[i]<a[q1[t]]) t--;
        q1[++t]=i;
        b[i]=a[q1[h]];
    }
    }
    inline int max_deque()
    {
    int h=1,t=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q2[h]+m<=i) h++;
        while(h<=t&&a[i]>a[q2[t]]) t--;
        q2[++t]=i;
        if(i>=m) ans+=a[q2[h]]*b[i];
    }
    
    return ans;
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    
    for (int i=1;i<=n;i++)
    {
        m=i;
        min_deque();
        printf("%d ",max_deque());
    }
    return 0;
    }

    既然正解是从普通的滑动窗口得来的,那就让我们脑胡一下这个过程。因为对于每一个点,都能把他作为某个K滑动窗口的起点。
    1滑动窗口:[1,1][2,2][3,3][...][n,n]
    2滑动窗口:[1,2][2,3][3,4][...][n-1,n]
    3滑动窗口:[1,3][2,4][3,5][...][n-2,n]
    ...
    竖着看。那么这就是我们将每一个点作为起点求出他对相关K滑动窗口的贡献的理由(注意断句)。对于某一些区间,其实他们的最大值和最小值是相等的。那么只要从起点开始,找到这些区间,将他们的贡献加入差分数组,最后统一计算即可。
    图片说明
    就像这样,我们不去考虑某一个区间应该加上哪些值,而是考虑一个值可以对多少区间产生影响。

  • 代码

/*
    可以确定的是,第i个数的ma与mi

其中一个一定等于i+1

    以每一个点为起点,计算之后

的贡献
*/
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+10;

int n;
ll a[N],stk[N],ki[N],ka[N],ans[N];
//值数组, 栈数组,最大扩展区间,最小扩展区间

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

    //求最大值
    for (int i=n,tp=0;i>=1;i--)
    {
        while(tp&&a[stk[tp]]<=a[i]) tp--;
        if(tp) ka[i]=stk[tp];else ka[i]=n+1;
        stk[++tp]=i;
    }

    //求最小值
    for (int i=n,tp=0;i>=1;i--)
    {
        while(tp&&a[stk[tp]]>=a[i]) tp--;
        if(tp) ki[i]=stk[tp];else ki[i]=n+1;
        stk[++tp]=i;
    }

    for (int i=1;i<=n;i++)
    {
        ll ma=i,mi=i,lmin=i,rmin=ki[i]-1,lmax=i,rmax=ka[i]-1;
        while(1)
        {
            int l=lmin-i+1,r=min(rmin,rmax)-i+1;
            ans[l]+=a[ma]*a[mi];ans[r+1]-=a[ma]*a[mi];

            lmin=lmax=min(rmin,rmax)+1;
            if(lmin==n+1) break;

            if(rmin<lmin) mi=rmin+1,rmin=ki[mi]-1;
            if(rmax<lmax) ma=rmax+1,rmax=ka[ma]-1;
        }
    }

    for (int i=1;i<=n;i++) ans[i]+=ans[i-1];
    for (int i=1;i<=n;i++) printf("%lld ",ans[i]);

    return 0;
}
比赛题解 文章被收录于专栏

牛客IOI周赛,团队赛,练习赛,挑战赛,各种模拟赛的部分题解

全部评论
请问复杂度怎么保证
点赞 回复 分享
发布于 2021-05-30 16:40

相关推荐

点赞 评论 收藏
分享
评论
10
1
分享
牛客网
牛客企业服务