题解
一道不错的分治题
最近心情有点焦躁在机房根本冷静不下来，所以今天用历史课推了 30 分钟式子就推完了。
首先我们考虑分治区间，将 $[l,mid]$和 $[mid+1,r]$的贡献统计完之后，我们只需要讨论跨越中点的区间对答案的贡献。
因为看数据范围可以知道算法必须是 $O(nlogn)$的，所以这意味着我们只能花费 $O(r-l)$的时间来处理上述贡献。
我们先记 $min[x,y]=Min_{i=x}^y a[i]$，$max[x,y]$同理
枚举一个区间左端点 $t$，那么以它为左端点的区间的贡献和为
$$\sum_{i=mid+1}^r min[t,i]\times max[t,i]\times (i-t+1)$$
我们记 $mn=min[t,mid],mx=max[t,mid]$
我们会发现 $min[t,i]$分为两部分，一部分等于 $mn$，一部分小于 $mn$，$max[t,i]$同理。
于是我们记 $pmin$表示 $min[t,pmin]=mn$且 $a[pmin+1]<mn$的位置，$pmax$同理。
记 $sum(x,y)=(y-x+1)\times (y+x)/2$
我们下面假设 $pmin<pmax$
当区间右端点在 $[mid+1,pmin]$中时，贡献为
$$\sum_{i=mid+1}^{pmin} mn \times mx \times (i-t+1)$$
即
$$mn\times mx \times sum(mid-t+2,pmin-t+1)$$
当区间右端点在 $[pmin+1,pmax]$中时，贡献为
$$\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)] $$
发现两个求和没办法简化了，所以我们可以预处理 $smn[i]$为 $min[t,i]$的前缀和，$smx[i]$为 $max[t,i]$的前缀和，$ismn[i]$为 $i\times min[t,i]$的前缀和，$ismx[i]$为 $i\times max[t,i]$的前缀和
上式化为
$$mx\times [(1-t)(smn[pmax]-smn[pmin]) + (ismn[pmax]-ismn[pmin])]$$
当区间右端点在 $[pmax+1,r]$中时，贡献为
$$\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]$$
所以我们预处理 $two[i]$表示 $min[t,i]\times max[t,i]$的前缀和，$itwo[i]$表示 $i\times min[t,i]\times max[t,i]$的前缀和
化简得
$$(1-t)(two[r]-two[pmax])+itwo[r]-itwo[pmax]$$
$pmin>pmax$的情况同理
然后你就可以 $O(n)$算跨中间的区间的贡献了，有些边界需要注意一下。
#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;
}
因为一些细节的错误 $WA$了好几次 $QAQ$
缩成一团逐渐自闭
0 条评论