看到滑动窗口，很容易想到单调队列，但该做法在本题中时间复杂度达到了 $O(n^2)$，不可取，于是考虑计算每个元素在不同窗口的贡献。

首先，元素在哪些窗口会作为最大值？对于每一个 $i∈[1,n]$ 我们可以用单调栈预计算出左右两边第一个大于他的值，并得到其能向左/右扩展多少步。同时为了避免重复计算贡献，我们使用左闭右开，即：

向左找到最近的一个位置 $j$ 使得 $a_j\geq a_i$ （若不存在则为 $0$），则 $l_i=i-j$
向右找到最近的一个位置 $j$ 使得 $a_j>a_i$ （若不存在则为 $n+1$），则 $r_i=j-i$

接下来分类讨论，计算贡献，记 $k$ 为滑动窗口的长度，$x=min(l_i,r_i),y=max(l_i,r_i)$，有：

当 $k∈[1,x]$，对长度为 $k$ 的窗口有贡献的共有 $x$ 个，$ans_k=ans_k+a_i k$
当 $k∈(x,y]$，对长度为 $k$ 的窗口有贡献的共有 $x$ 个，$ans_k=ans_k+a_i x$
当$k∈(y,x+y)$，对长度为 $k$ 的窗口有贡献的共有 $(x+y-k)$ 个，$ans_k=ans_k+(x+y-k) a_i$

区间修改，单点查询，可以使用树状数组或者线段树，但最简单的还是差分。

维护 $p$，$q$ 差分数组，将上述操作含有 $k$ 的项归为 $p$，其余归为 $q$，答案 $ans_k=\sum_{i=1}^k p_i k+\sum_{i=1}^k q_i$

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,a[N],l[N],r[N];
int p[N],q[N];
void add(int *b,int l,int r,int x){b[l]+=x,b[r+1]-=x;}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    stack<int> s;
    for(int i=1;i<=n;i++){
        while(!s.empty()&&a[i]>a[s.top()]) s.pop();
        l[i]=i-(s.empty()?0:s.top());
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i=n;i>=1;i--){
        while(!s.empty()&&a[i]>=a[s.top()]) s.pop();
        r[i]=(s.empty()?n+1:s.top())-i; 
        s.push(i);
    }
    for(int i=1;i<=n;i++){
        int x=l[i],y=r[i];
        if(x>y) swap(x,y); 
        add(p,1,x,a[i]);
        add(q,x+1,y,a[i]*x);
        add(p,y+1,x+y,-a[i]);
        add(q,y+1,x+y,a[i]*(x+y));
    }
    for(int i=1;i<=n;i++){
        p[i]+=p[i-1],q[i]+=q[i-1];
        printf("%lld\n",p[i]*i+q[i]);
    }
    return 0;
}