luogu

bzoj

题解

一道不错的分治题

最近心情有点焦躁在机房根本冷静不下来,所以今天用历史课推了 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$

缩成一团逐渐自闭

分类: 文章

quhengyi11

AFO 有缘再见

发表评论

电子邮件地址不会被公开。 必填项已用*标注