要命的题目。
写法：分类讨论进行计算。
枚举过每一个(mid)的所有区间。对于左端点(i∈[l, mid - 1])，向左推并计算([l,mid])范围内的最大(/)最小值。
然后右端点(p)分三种类型考虑。
-
(p∈[mid + 1, p1 - 1])，其中(p1)是第一次出现比(maxw)大或者比(minw)小的数的位置。
-
(p∈[p1, p2 - 1])，其中(p2)是第二次出现比(maxw)大或者比(minw)小的数的位置。
-
(p∈[p2, r])，(r)是当前枚举区间的右端点。
其中情况一高斯求和，情况二和情况三可以化为前缀最大最小值之和(/)积带几个系数的形式(O(N))维护。
要命原因：取膜。
两年(OI)一场空，_______。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 500000 + 5;
const LL Mod = 1000000000;
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x > y ? x : y)
#define mul(x,y) ((1ll * (x % Mod) * (y % Mod)) % Mod)
#define add(x,y) ((0ll + (x % Mod) + (y % Mod)) % Mod)
int n, arr[N]; LL ans;
int _maxw[N], _minw[N];
LL mn1[N], mn2[N], mx1[N], mx2[N], mnmx1[N], mnmx2[N];
int get_maxp (int w, int l, int r) {
if (_maxw[r] <= w) return r + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (_maxw[mid] > w) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
int get_minp (int w, int l, int r) {
if (_minw[r] >= w) return r + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (_minw[mid] < w) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
void cdq (int l, int r) {
if (l == r) {
ans = add (ans, mul (arr[l], arr[r]));
return;
}
int mid = (l + r) >> 1;
cdq (l, mid + 0);
cdq (mid + 1, r);
int maxw = arr[mid], minw = arr[mid];
mx1[mid - 1] = mx2[mid - 1] = 0;
mn1[mid - 1] = mn2[mid - 1] = 0;
mnmx1[mid - 1] = mnmx2[mid - 1] = 0;
_maxw[mid] = _minw[mid] = arr[mid];
for (int i = mid + 1; i <= r; ++i) {
_maxw[i] = max (_maxw[i - 1], arr[i]);
_minw[i] = min (_minw[i - 1], arr[i]);
}
for (int p = mid; p <= r; ++p) {
mx1[p] = add (mx1[p - 1], mul (_maxw[p], (p + 1)));
mx2[p] = add (mx2[p - 1], _maxw[p]);
mn1[p] = add (mn1[p - 1], mul (_minw[p], (p + 1)));
mn2[p] = add (mn2[p - 1], _minw[p]);
mnmx1[p] = add (mnmx1[p - 1], mul (_maxw[p], mul (_minw[p], (p + 1))));
mnmx2[p] = add (mnmx2[p - 1], mul (_maxw[p], _minw[p]));
}
for (int i = mid; i >= l; --i) {
maxw = max (maxw, arr[i]);
minw = min (minw, arr[i]);
int p1 = get_maxp (maxw, mid + 1, r); // [mid + 1, r]内第一个比maxw大的地方
int p2 = get_minp (minw, mid + 1, r); // [mid + 1, r]内第一个比minw小的地方
if (p1 > p2) swap (p1, p2); // 不关注大小，主要看划分
// cout << p1 << " " << p2 << endl;
ans = add (ans, mul (1ll * (p1 - mid - 1) * (p1 + mid - i * 2 + 2) / 2, mul (minw, maxw))); // Part 1
if (arr[p1] > maxw) {
ans = add (ans, mul (minw, add (add (mx1[p2 - 1], -mx1[p1 - 1]), -mul (i, add (mx2[p2 - 1], -mx2[p1 - 1])))));
} else {
ans = add (ans, mul (maxw, add (add (mn1[p2 - 1], -mn1[p1 - 1]), -mul (i, add (mn2[p2 - 1], -mn2[p1 - 1])))));
}
if (p2 <= r) {
ans = add (ans, add (add (mnmx1[r], -mnmx1[p2 - 1]), -mul (i, add (mnmx2[r], -mnmx2[p2 - 1]))));
}
}
}
signed main () {
// freopen ("data.in", "r", stdin);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
}
cdq (1, n);
// cout << ans << endl;
cout << (((ans % Mod) + Mod) % Mod) << endl;;
}