3606: 牛牛的滑动窗口(第一轮04)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
【题目描述】
牛牛最近学习了滑动窗口类的算法，滑动窗口算法可以解决一些线性数组的离线静态区间查询类问题。具体来说，假设对于一个数组进行 m 次静态区间查询问题。如果这些查询满足条件：∀𝑖,𝑗当𝑙𝑖 ≤ 𝑙𝑗时，总有𝑟𝑖 ≤ 𝑟𝑗。（i,j 表示查询的编号，l,r 表示查询的左右端点）
接下来只要查询的问题满足可以快速插入和删除单点，就可以使用滑动窗口优化，将这 m 次查询的复杂度降低到 O(n)。显然，如果对于一个数组的区间查询问题，查询的区间长度给定为 k 时，总是满足∀𝑖,𝑗当𝑙𝑖 ≤ 𝑙𝑗 时，总有𝑟𝑖 ≤ 𝑟𝑗这一条件的。牛牛接下来想要问你的问题也和定长滑动窗口有关。众所周知，长度为 k 的滑动窗口从左到右去截取一个长度大小为 n 的数组时，一共可以截取到 n-k+1 个子数组。牛牛将这 n-k+1 个子数组的极大值与极小值的乘积求和称为该数组的"第 k 窗口值
举个例子，假设长度为5的数组为[1,5,2,4,3]，长度为3的滑动窗口可以截取三个子数组，它们分别为[1,5,2],[5,2,4],[2,4,3]。所以该数组的“第3窗口值”为1*5+2*5+2*4=23。对于一个给定大小的数组n，牛牛现在想要知道它的第1,2,3,4,5...n窗口值各是多少，请你编写程序解决他的问题。
输入
第一行输入一个正整数n，表示数组的大小。
接下来一行输入n个正整数ai，表示数组的内容
输出
输出一行n个正整数，表示滑动窗口的长度分别为1,2,3,4,5...n 时，问题的答案。
输出的整数之间用空格隔开，行末不允许有多余空格。
样例输入 复制
5
1 5 2 4 3样例输出 复制
55 35 23 15 5提示
【样例1说明】
第1窗口值=1*1+5*5+2*2+4*4+3*3=55
第2窗口值=5*1+5*2+4*2+4*3=35
第3窗口值=5*1+5*2+4*2=23
第4窗口值=5*1+5*2=15
第5窗口值=5*1=5
【数据范围】
对于10%的测试数据，保证1≤n≤10
对于20%的测试数据，保证1≤n≤100
对于30%的测试数据，保证1≤n≤1000
对于50%的测试数据，保证1≤n≤6000
对于另外10%的测试数据，保证1≤ai≤10
对于100%的测试数据，保证1≤n≤100000,1≤ai≤100