题目链接：https://ac.nowcoder.com/acm/problem/212959

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109151074

题目

牛牛最近学习了滑动窗口类的算法，滑动窗口算法可以解决一些线性数组的离线静态区间查询类问题。

具体来说，假设对于一个数组进行 次静态区间查询问题。如果这些查询满足条件： 当 时，总有 。（ 表示查询的编号， 表示查询的左右端点）

接下来只要查询的问题满足可以快速插入和删除单点，就可以使用滑动窗口优化，将这 次查询的复杂度降低到 O(n)。

显然，如果对于一个数组的区间查询问题，查询的区间长度给定为 时，总是满足 当 时，总有 这一条件的。

牛牛接下来想要问你的问题也和定长滑动窗口有关。

众所周知，长度为 的滑动窗口从左到右去截取一个长度大小为 的数组时，一共可以截取到 个子数组。

牛牛将这 个子数组的极大值与极小值的乘积求和称为该数组的"第 窗口值"。
图片说明
举个例子，假设长度为 的数组为 [1,5,2,4,3]，长度为 的滑动窗口可以截取三个子数组，它们分别为 [1,5,2] , [5,2,4] , [2,4,3]。
所以该数组的“第 窗口值”为 。

对于一个给定大小的数组 ，牛牛现在想要知道它的第 窗口值各是多少，请你编写程序解决他的问题。

输入

第一行输入一个正整数 ，表示数组的大小。

接下来一行输入 个正整数 ，表示数组的内容

输出

输出一行 个正整数，表示滑动窗口的长度分别为 时，问题的答案。

输出的整数之间用空格隔开，行末不允许有多余空格。

样例输入

5
1 5 2 4 3

样例输出

55 35 23 15 5

样例解释

第 窗口值

第 窗口值

第 窗口值

第 窗口值

第 窗口值

数据范围

对于 的测试数据，保证
对于 的测试数据，保证
对于 的测试数据，保证
对于 的测试数据，保证
对于另外 的测试数据，保证
对于 的测试数据，保证

思路

这道题是一道用两个单调栈和差分来做的题目。

我们可以知道，一个区间对答案的贡献，就是最大的乘最小的，那我们其实可以先确定右端点，然后不断向左找，找可以让他的最大值或者最小值更新的点，这个时候对答案的贡献就会改变。

那我们就可以对于枚举的每一个右端点，维护两个单调栈，一个是严格单调上升，一个是严格单调下降，然后每次从这两个栈的栈顶的元素挑后面的值。这样，我们就把数列分成了若干个区间，以同一区间的任意一个点到右端点的新区间的最大值和最小值都是一样的。

但是问题来了，我们总不能对于每一个区间，一个一个的枚举长度然后加吧，那样肯定会超时。
那我们看，我们会发现，区间的每一个点从右边开始看构成新区间的长度，我们会发现它是一个等差数列，而且差值是 。
那我们就可以用差分来做，那这样每次加一整个区间就不用一个一个枚举了。

（当然，听说找一个点左边值递减的点和左边值递增的点好像还可以用很多其他方法，具体有什么忘了，但是我觉得用单调栈会相对简单很多吧。。。）
（上面括号最后一句仅表个人观点，勿喷谢谢）

比赛时

在第三题用了太多的时间，就只能唯唯诺诺的拿了个 分 n 方代码，然后又去搞第三题了。
（结果到最后还是没想到第三题处理完的数是一一对应的QAQ）
图片说明

代码

#include<cstdio>
#include<iostream>

using namespace std;

struct node {
    int x, num;
}bigstack[101], smallstack[101];
int n, a[100001], ans[100001], bigtop, smalltop, maxn, minn;
int lft, bignow, smallnow;

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

    for (int i = 1; i <= n; i++) {
        while (bigtop && bigstack[bigtop].x <= a[i]) bigtop--;
        while (smalltop && smallstack[smalltop].x >= a[i]) smalltop--;//栈的弹出

        bigstack[++bigtop] = (node){a[i], i};//插入
        smallstack[++smalltop] = (node){a[i], i};
        maxn = minn = a[i];
        lft = i;
        bignow = bigtop - 1;
        smallnow = smalltop - 1;

        while (bignow || smallnow) {//一点一点往后移，算贡献
            if (bignow && smallnow) {
                if (bigstack[bignow].num >= smallstack[smallnow].num) {
                    ans[i - lft + 1] += maxn * minn;
                    ans[i - bigstack[bignow].num + 1] -= maxn * minn;
                    lft = bigstack[bignow].num;
                    maxn = bigstack[bignow].x;
                    bignow--;
                }
                else {
                    ans[i - lft + 1] += maxn * minn;
                    ans[i - smallstack[smallnow].num + 1] -= maxn * minn;
                    lft = smallstack[smallnow].num;
                    minn = smallstack[smallnow].x;
                    smallnow--;
                }

                continue;
            }

            if (bignow) {
                ans[i - lft + 1] += maxn * minn;
                ans[i - bigstack[bignow].num + 1] -= maxn * minn;
                lft = bigstack[bignow].num;
                maxn = bigstack[bignow].x;
                bignow--;
            }

            else {
                ans[i - lft + 1] += maxn * minn;
                ans[i - smallstack[smallnow].num + 1] -= maxn * minn;
                lft = smallstack[smallnow].num;
                minn = smallstack[smallnow].x;
                smallnow--;
            }
        }

        ans[i - lft + 1] += maxn * minn;
        ans[i + 1] -= maxn * minn;
    }

    for (int i = 1; i <= n; i++) {
        ans[i] += ans[i - 1];//因为是差分，所以要加上前面的
        printf("%d ", ans[i]);
    }

    return 0;
}