2020牛客NOIP赛前集训营-普及组（第一场）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;
}