51nod - 1215 数组的宽度
程序员文章站
2022-03-03 07:59:41
...
N个整数组成的数组,定义子数组a[i]..a[j]的宽度为:max(a[i]..a[j]) - min(a[i]..a[j]),求所有子数组的宽度和。
Input
第1行:1个数N,表示数组的长度。(1 <= N <= 50000)
第2 - N + 1行:每行1个数,表示数组中的元素(1 <= A[i] <= 50000)
Output
输出所有子数组的宽度和。
Input示例
5
1
2
3
4
5
Output示例
20
思路:
用单调递减栈计算每个数作为最大值影响的区间,区间数量乘以这个数的值就是这个数作为最大值的贡献。
同理,用单调递增栈计算每个数作为最小值影响的区间,区间数量乘以这个数的值就是这个数作为最小值的贡献。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
int a[MAXN], s[MAXN];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
a[++n] = 0;
ll sum1 = 0, sum2 = 0;
int top = 0;
for (int i = 1; i <= n; i++)
{
while (top && a[i] < a[s[top]])
{
sum1 += 1ll * (s[top] - s[top - 1]) * (i - s[top]) * a[s[top]];
top--;
}
s[++top] = i;
}
a[n] = MAXN;
top = 0;
for (int i = 1; i <= n; i++)
{
while (top && a[i] > a[s[top]])
{
sum2 += 1ll * (s[top] - s[top - 1]) * (i - s[top]) * a[s[top]];
top--;
}
s[++top] = i;
}
cout << sum2 - sum1 << endl;
return 0;
}