『Norma 分治』

<更新提示>

<第一次更新>

<正文>

Norma

Description

Input Format

第1行，一个整数N；

第2~n+1行，每行一个整数表示序列a。

Output Format

输出答案对10^9取模后的结果。

Sample Input

4
2
4
1
4

Sample Output

109

解析

可以考虑分治计算贡献，对于一次分治\((l,r,mid)\)，我们只需要计算跨过中点\(mid\)的子区间带来的贡献即可。

我们可以枚举一个左端点\(L\in[l,mid]\)，然后尝试计算所有的\(R\in[mid+1,r]\)，区间\([L,R]\)的贡献之和，然后就是推公式了。

对于确定的\(L\)，我们先假设\(min=\min\{a_L,a_{L+1},...,a_{mid}\},max=\max\{a_L,a_{L+1},...,a_{mid}\}\)，然后，我们令\(p\)为满足\(a_p<min,p\in[mid+1,r]\)最小的位置，\(q\)为满足\(a_p>max,q\in[mid+1,r]\)最小的位置，然后计算贡献。

不妨设\(p\leq q\)，那么对于\(R\in[mid+1,p)\)，区间\([L,R]\)的最大最小值为\(min,max\)，贡献为：
\[min\times max\times\sum_{R=mid+1}^{p-1} (R-L+1)\]

直接计算即可。

对于\(R\in[p,q)\)，区间的最大值为\(max\)，最小值为\(\min\{a_{mid+1},...,a_R\}\)，贡献为

\[max\times \sum_{R=p}^{q-1}min_R\times (R-L+1)\\=max\times \sum_{R=p}^{q-1}min_R\times R-max\times (L-1)\sum_{R=p}^{q-1}min_R\]

维护\(min_R\times R\)和\(min_R\)两个前缀和即可。

对于\(R\in[q,r]\)，区间的最大值为\(\max\{a_{mid+1},...,a_R\}\)，最小值为\(\min\{a_{mid+1},...,a_R\}\)，贡献为
\[\sum_{R=q}^rmax_R\times min_R\times(R-L+1)\\=\sum_{R=q}^rmax_R\times min_R\times R-(L-1)\sum_{R=q}^rmax_R\times min_R\]

维护\(max_R\times min_R\times R\)和\(max_R\times min_R\)两个前缀和即可。

对于\(q<p\)，只有第二部分不一样，其贡献为
\[min\times \sum_{R=p}^{q-1}max_R\times R-min\times (L-1)\sum_{R=p}^{q-1}max_R\]

维护\(max_R\times R\)和\(max_R\)两个前缀和即可。

于是这道题就解决了。

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
const int N = 500020 , Mod = 1e9 , INF = 0x3f3f3f3f;
int n;
long long ans,a[N],Min[N],Max[N],sMin[N],sMax[N],MinMax[N],sMinMax[N];
inline long long add(long long a,long long b) { long long c = a + b; while ( c >= Mod ) c -= Mod; return c; }
inline void upd(long long &a,long long b) { a = add( a , b ); }
inline long long sigma(int l,int r) { return 1LL * ( l + r ) * ( r - l + 1 ) / 2 % Mod; }
inline void divide(int l,int r)
{
    if ( l == r ) return upd( ans , a[l] * a[l] % Mod );
    int mid = l + r >> 1; long long mn = INF, mx = 0;
    divide( l , mid ) , divide( mid + 1 , r );
    Min[mid] = Max[mid] = sMin[mid] = sMax[mid] = MinMax[mid] = sMinMax[mid] = 0;
    for (int i=mid+1;i<=r;i++)
    {
        mn = min( mn , a[i] ) , mx = max( mx , a[i] );
        Min[i] = add( Min[i-1] , mn ) , Max[i] = add( Max[i-1] , mx );
        sMin[i] = add( sMin[i-1] , mn * i % Mod );
        sMax[i] = add( sMax[i-1] , mx * i % Mod );
        MinMax[i] = add( MinMax[i-1] , mn * mx % Mod );
        sMinMax[i] = add( sMinMax[i-1] , mn * mx % Mod * i % Mod );
    }
    mn = INF , mx = 0;
    int p = mid + 1 , q = mid + 1;
    for (int i=mid;i>=l;i--)
    {
        mn = min( mn , a[i] ) , mx = max( mx , a[i] );
        while ( p <= r && a[p] >= mn ) p++;
        while ( q <= r && a[q] <= mx ) q++;
        if ( p <= q )
        {
            upd( ans , mn * mx % Mod * sigma( mid - i + 2 , p - i ) % Mod );
            upd( ans , mx * ( sMin[q-1] - sMin[p-1] ) % Mod - mx * (i-1) % Mod * ( Min[q-1] - Min[p-1] ) % Mod + Mod );
            upd( ans , ( sMinMax[r] - sMinMax[q-1] ) - (i-1) * ( MinMax[r] - MinMax[q-1] ) % Mod + Mod );
        }
        if ( p > q )
        {
            upd( ans , mn * mx % Mod * sigma( mid - i + 2 , q - i ) % Mod );
            upd( ans , mn * ( sMax[p-1] - sMax[q-1] ) % Mod - mn * (i-1) % Mod * ( Max[p-1] - Max[q-1] ) % Mod + Mod );
            upd( ans , ( sMinMax[r] - sMinMax[p-1] ) - (i-1) * ( MinMax[r] - MinMax[p-1] ) % Mod + Mod );
        }
    }
}
int main(void)
{
    freopen("norma.in","r",stdin);
    freopen("norma.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lld",&a[i]) , a[i] %= Mod;
    divide( 1 , n );
    printf("%lld\n",ans);
    return 0;
}