题解 P6503 【[COCI2010-2011#3] DIFERENCIJA】
rui_er
2020-05-01 10:47:09
~~我绝不会告诉你们这题与 SP10622 是双倍经验的~~，好了，不扯了，下面开始正文。
这题要求 $\sum_{i=1}^n\sum_{j=i}^n\max_{i\le k\le j}a_k-\min_{i\le k\le j}a_k$，看到最小值与最大值，想到单调栈。
单调栈具体可不可以呢？当然是可以的。我们这里同时维护两个单调栈，递增和递减，就可以了。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5+5;
ll n, a[N], x[N], y[N], S, ans;
stack<ll> mi, ma;
int main()
{
scanf("%lld", &n);
for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
mi.push(a[1]);
ma.push(a[1]);
x[1] = y[1] = 1;
ans = S = 0;
for(ll i=2;i<=n;i++)
{
ll tmp = 1;
while(!mi.empty() && mi.top() <= a[i])
{
S -= mi.top() * x[mi.size()];
tmp += x[mi.size()];
mi.pop();
}
mi.push(a[i]);
x[mi.size()] = tmp;
S += a[i] * tmp;
tmp = 1;
while(!ma.empty() && ma.top() >= a[i])
{
S += ma.top() * y[ma.size()];
tmp += y[ma.size()];
ma.pop();
}
ma.push(a[i]);
y[ma.size()] = tmp;
S -= a[i] * tmp;
ans += S;
}
printf("%lld\n", ans);
return 0;
}
```