贝壳极差题目O（n）解法
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给定一个长度为N的序列A1到AN，求所有区间[L，R]（1≤L≤R≤N）的极差之和，其中区间[L，R]的极差定义为AL到AR中的最大值与最小值之差。
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给定一个长度为N的序列A1到AN，求所有区间[L，R]（1≤L≤R≤N）的极差之和，其中区间[L，R]的极差定义为AL到AR中的最大值与最小值之差。
贝壳极差题目O（n）解法，花了很长时间才做出来，不要跟我说暴力就过了。。。。。。
思路：先算减去所有区间最小值，再算加上所有区间最大值。用单调栈可以算出，比某一个数大的最近的数，比如i位置的数，分别对应比他大的最近的数的位置是ci和di，那么所有的区间总数就是（i-ci）*（di-i），然后用ai乘上它，再从res里面减去。最大值得思路一样。
using namespace std;
int main() {
int n;
cin >> n;
if (n <= 1) {
cout << 0;
return 0;
}
vector<long long>a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
stack<pair<int, int>> s;
vector<int> c(n), d(n);
for (int i = 0; i < n; i++) {
while (!s.empty() && s.top().first > a[i])
s.pop();
if (s.empty())
c[i] = -1;
else
c[i] = s.top().second;
s.push({ a[i], i });
}
s = stack<pair<int, int>>();
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top().first >= a[i])
s.pop();
if (s.empty())
d[i] = n;
else
d[i] = s.top().second;
s.push({ a[i], i });
}
long long res = 0;
for (int i = 0; i < n; i++) {
res -= a[i] * (i - c[i]) * (d[i] - i);
}
s = stack<pair<int, int>>();
for (int i = 0; i < n; i++) {
while (!s.empty() && s.top().first <= a[i])
s.pop();
if (s.empty())
c[i] = -1;
else
c[i] = s.top().second;
s.push({ a[i], i });
}
s = stack<pair<int, int>>();
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top().first < a[i])
s.pop();
if (s.empty())
d[i] = n;
else
d[i] = s.top().second;
s.push({ a[i], i });
}
for (int i = 0; i < n; i++) {
res += a[i] * (i - c[i]) * (d[i] - i);
}
cout << res;
return 0;
}
int main() {
int n;
cin >> n;
if (n <= 1) {
cout << 0;
return 0;
}
vector<long long>a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
stack<pair<int, int>> s;
vector<int> c(n), d(n);
for (int i = 0; i < n; i++) {
while (!s.empty() && s.top().first > a[i])
s.pop();
if (s.empty())
c[i] = -1;
else
c[i] = s.top().second;
s.push({ a[i], i });
}
s = stack<pair<int, int>>();
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top().first >= a[i])
s.pop();
if (s.empty())
d[i] = n;
else
d[i] = s.top().second;
s.push({ a[i], i });
}
long long res = 0;
for (int i = 0; i < n; i++) {
res -= a[i] * (i - c[i]) * (d[i] - i);
}
s = stack<pair<int, int>>();
for (int i = 0; i < n; i++) {
while (!s.empty() && s.top().first <= a[i])
s.pop();
if (s.empty())
c[i] = -1;
else
c[i] = s.top().second;
s.push({ a[i], i });
}
s = stack<pair<int, int>>();
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top().first < a[i])
s.pop();
if (s.empty())
d[i] = n;
else
d[i] = s.top().second;
s.push({ a[i], i });
}
for (int i = 0; i < n; i++) {
res += a[i] * (i - c[i]) * (d[i] - i);
}
cout << res;
return 0;
}
#笔试题目##贝壳找房#
