题解 [email protected]洛谷 | [email protected]洛谷 | [email protected] 【[COCI2010-2011#3] DIFERENCIJA】

我绝不会告诉你们这题与 SP10622 是双倍经验的,好了,不扯了,下面开始正文。

这题要求 i=1nj=inmaxikjakminikjak\sum_{i=1}^n\sum_{j=i}^n\max_{i\le k\le j}a_k-\min_{i\le k\le j}a_k,看到最小值与最大值,想到单调栈。

单调栈具体可不可以呢?当然是可以的。我们这里同时维护两个单调栈,递增和递减,就可以了。

代码:

#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;
}