N个整数组成的数组，定义子数组a[i]…a[j]的宽度为：max(a[i]…a[j]) - min(a[i]…a[j])，求所有子数组的宽度和。
输入
第1行：1个数N，表示数组的长度。(1 <= N <= 50000)
第2 - N + 1行：每行1个数，表示数组中的元素(1 <= A[i] <= 50000)
输出
输出所有子数组的宽度和。
输入样例
5
1
2
3
4
5
输出样例
20
使用单调栈处理出以a[i]为最小值和最大值的左右边界
答案为：sum : (i - Lmax[i]) * (Rmax[i] - i) * a[i] - (i - Lmin[i]) * (Rmin[i] - i) * a[i]
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int a[maxn]; int Lmin[maxn], Rmin[maxn]; int Lmax[maxn], Rmax[maxn]; stack<int> s; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } a[0] = 0; a[n + 1] = 0; for (int i = 1; i <= n + 1; i++) { while (!s.empty() && a[s.top()] >= a[i]) { Rmin[s.top()] = i; s.pop(); } s.push(i); } while (!s.empty()) s.pop(); for (int i = n; i >= 0; i--) { while (!s.empty() && a[s.top()] > a[i]) { Lmin[s.top()] = i; s.pop(); } s.push(i); } a[0] = 1e9; a[n + 1] = 1e9; while (!s.empty()) s.pop(); for (int i = 1; i <= n + 1; i++) { while (!s.empty() && a[s.top()] <= a[i]) { Rmax[s.top()] = i; s.pop(); } s.push(i); } while (!s.empty()) s.pop(); for (int i = n; i >= 0; i--) { while (!s.empty() && a[s.top()] < a[i]) { Lmax[s.top()] = i; s.pop(); } s.push(i); } long long ans = 0; for (int i = 1; i <= n; i++) { ans += 1LL * (i - Lmax[i]) * (Rmax[i] - i) * a[i]; ans -= 1LL * (i - Lmin[i]) * (Rmin[i] - i) * a[i]; } cout << ans << endl; return 0; }
