luogu

bzoj

## 题解

$$\sum_{i=mid+1}^r min[t,i]\times max[t,i]\times (i-t+1)$$

$$\sum_{i=mid+1}^{pmin} mn \times mx \times (i-t+1)$$

$$mn\times mx \times sum(mid-t+2,pmin-t+1)$$

$$\sum_{i=pmin+1}^{pmax}mx \times min[t,i] \times (i-t+1)$$

$$mx\times[(1-t)(\sum_{i=pmin+1}^{pmax}min[t,i]) + (\sum_{i=pmin+1}^{pmax}min[t,i]\times i)]$$

$$mx\times [(1-t)(smn[pmax]-smn[pmin]) + (ismn[pmax]-ismn[pmin])]$$

$$\sum_{i=pmax+1}^r min[t,i]\times max[t,i]\times(i-t+1)$$

$$(1-t)\sum_{pmax+1}^rmin[t,i]\times max[t,i]+\sum_{pmax+1}^r i\times min[t,i]\times max[t,i]$$

$$(1-t)(two[r]-two[pmax])+itwo[r]-itwo[pmax]$$

$pmin>pmax$的情况同理

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define Re register
#define N 500005
#define mod 1000000000
#define ll long long
int a[N], mn, mx, min[N], max[N], n;
ll ans, smn[N], smx[N], ismn[N], ismx[N], two[N], itwo[N];
int add (int x, int y) {Re int ret = x + y; return (mod < ret) ? ret - mod : ret;}
int sum (int x, int y) {return (1ll * (y - x + 1) * (x + y) >> 1) % mod;}
void solve (int l, int r)
{
if (l == r) {ans = (ans + 1ll * a[l] * a[l]) % mod; return;}
int mid = l + r >> 1, pmin = mid + 1, pmax = mid + 1, mn = a[mid], mx = a[mid];
solve(l, mid); solve(mid + 1, r);
smn[mid] = smx[mid] = ismn[mid] = ismx[mid] = two[mid] = itwo[mid] = 0;//我这个写法这里要赋值 0，否则差分前缀和的时候会出错
smn[mid + 1] = smx[mid + 1] = min[mid + 1] = max[mid + 1] = a[mid + 1];
ismn[mid + 1] = ismx[mid + 1] = 1ll * (mid + 1) * a[mid + 1] % mod;
two[mid + 1] = 1ll * a[mid + 1] * a[mid + 1] % mod;
itwo[mid + 1] = 1ll * (mid + 1) * two[mid + 1] % mod;
fo (i, mid + 2, r)
{
min[i] = std::min(min[i - 1], a[i]);
max[i] = std::max(max[i - 1], a[i]);
}
fo (i, mid + 2, r)
{
smn[i] = add(smn[i - 1], min[i]);
smx[i] = add(smx[i - 1], max[i]);
ismn[i] = (ismn[i - 1] + 1ll * i * min[i]) % mod;
ismx[i] = (ismx[i - 1] + 1ll * i * max[i]) % mod;
two[i] = (two[i - 1] + 1ll * min[i] * max[i]) % mod;
itwo[i] = (itwo[i - 1] + 1ll * i * min[i] % mod * max[i]) % mod;
}
fd (t, mid, l)
{
mn = std::min(mn, a[t]); mx = std::max(mx, a[t]);
while (pmin <= r&& mn <= a[pmin]) ++pmin; --pmin;
while (pmax <= r&& mx >= a[pmax]) ++pmax; --pmax;
if (pmin < pmax)
{
if (mid < pmin)
(ans += 1ll * mn * mx % mod * sum(mid + 2 - t, pmin - t + 1)) %= mod;
if (mid < pmax)
(ans += 1ll * mx * ((1 - t) * (smn[pmax] - smn[pmin]) % mod + ismn[pmax] - ismn[pmin])) %= mod;
(ans += 1ll * (1 - t) * (two[r] - two[pmax]) + itwo[r] - itwo[pmax]) %= mod;
}
else
{
if (mid < pmax)
(ans += 1ll * mn * mx % mod * sum(mid + 2 - t, pmax - t + 1)) %= mod;
if (mid < pmin)
(ans += 1ll * mn * ((1 - t) * (smx[pmin] - smx[pmax]) % mod + ismx[pmin] - ismx[pmax])) %= mod;
(ans += 1ll * (1 - t) * (two[r] - two[pmin]) + itwo[r] - itwo[pmin]) %= mod;
}
}
}
main ()
{
scanf("%d", &n);
fo (i, 1, n) scanf("%d", &a[i]);
solve(1, n);
printf("%lld", (ans + mod) % mod);
return 0;
}