BZOJ | P3745 | 分治 | cdq 分治


Description

你有一个长度为n的序列,定义这个序列中每个区间的价值是 $Cost(i,j)=\mathrm{Min}(A_{i}…A_{j}) \times \mathrm{Max}(A_{i}…A_{j}) \times (j-i+1)$ 。其中,$i,j$ 是区间的两个端点。请你求出给定序列所有区间的价值之和。


Input Format

第 $1$ 行一个整数 $N$ ,表示这个序列有 $N$ 个数。
第 $2 \sim N+1$ 行每行一个整数,第 $i+1$ 行的整数代表这个序列的第 $i$ 个数。


Output Format

一行,一个整数。给定序列所有区间的价值之和。输出其 mod $10^9$ 的值。


Input Sample

Sample 01

4
2 4 1 4

Sample 02

2
1 3


Output Sample

Sample 01

109

Sample 02

16


Data Range

$1 \le N \le 5 \times 10^5$,$1 \le a_i \le 10^8$。


Solution

考虑分治。设立指针 $i$ 从 $mid$ 向左移动,记录当前左区间 $[i,mid]$ 中的 $min$ 和 $max$,同时记录右区间中第一个小于 $min$ 的 $minpos$ 和第一个大于 $max$ 的 $maxpos$。(假设 $minpos < maxpos$ )这样就将 $[mid+1,R]$ 划分为了三个部分:$[mid+1,minpos-1],[minpos,maxpos-1],[maxpos,R]$ ,最值分别为 $<min,max> , <min_R,max> , <min_R,max_R>$ 。依次预处理出几个前缀和,讨论一下计算答案即可。一定要多取模。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define mid ((L+R)>>1)
#define mod 1000000000
#define ToAns(x) ans=(ans+x)%mod

typedef long long ll;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int N;
int minn_ext;
int maxx_ext;

ll ans;
ll minn;
ll maxx;

int src[500005];

ll minn_arr[500005];
ll maxx_arr[500005];
ll minn_sv[500005];
ll maxx_sv[500005];
ll mmax_sv[500005];
ll minn_msv[500005];
ll maxx_msv[500005];
ll mmax_msv[500005];

void Merge(int L,int R){
    if(L==R)
        return ToAns((ll)src[L]*src[R]%mod),void();
    Merge(L,mid);
    Merge(mid+1,R);
    int i=mid;
    int j=mid+1;
    minn_ext=j;
    maxx_ext=j;
    minn=src[i];
    maxx=src[i];
    minn_sv[mid]=0;
    maxx_sv[mid]=0;
    mmax_sv[mid]=0;
    minn_msv[mid]=0;
    maxx_msv[mid]=0;
    mmax_msv[mid]=0;
    maxx_arr[mid]=src[mid+1];
    minn_arr[mid]=src[mid+1];
    rep(k,mid+1,R){
        minn_arr[k]=min(minn_arr[k-1],src[k]);
        maxx_arr[k]=max(maxx_arr[k-1],src[k]);
        minn_sv[k]=(minn_sv[k-1]+minn_arr[k])%mod;
        maxx_sv[k]=(maxx_sv[k-1]+maxx_arr[k])%mod;
        mmax_sv[k]=(mmax_sv[k-1]+((ll)minn_arr[k]*maxx_arr[k])%mod)%mod;
        minn_msv[k]=(minn_msv[k-1]+(ll)minn_arr[k]*(k)%mod)%mod;
        maxx_msv[k]=(maxx_msv[k-1]+(ll)maxx_arr[k]*(k)%mod)%mod;
        mmax_msv[k]=(mmax_msv[k-1]+((ll)minn_arr[k]*maxx_arr[k]%mod*(k)%mod)%mod)%mod;
    }
    for(;i>=L;i--){
        minn=min(minn,src[i]);
        maxx=max(maxx,src[i]);
        while(minn_ext<=R){
            if(src[minn_ext]<minn)
                break;
            minn_ext++;
        }
        while(maxx_ext<=R){
            if(src[maxx_ext]>maxx)
                break;
            maxx_ext++;
        }
        //type 1
        //公因子:minn*maxx 
        //首项:mid+2-i
        //末项:min(minn_ext,maxx_ext)-i
        //项数:min(minn_ext,maxx_ext)-(mid+1)
        ToAns(((ll)minn*maxx)%mod*((ll)(mid+2-i+min(minn_ext,maxx_ext)-i)*(min(minn_ext,maxx_ext)-(mid+1))/2%mod)%mod);
        if(minn_ext<maxx_ext){
            //type 2
            ToAns((ll)maxx*((minn_msv[maxx_ext-1]-minn_msv[minn_ext-1]%mod+mod)%mod)%mod);
            ToAns((ll)((-1)*maxx%mod+mod)%mod*(i-1)%mod*((minn_sv[maxx_ext-1]-minn_sv[minn_ext-1])%mod+mod)%mod);
            //type 3
            ToAns((ll)((mmax_msv[R]-mmax_msv[maxx_ext-1])%mod+mod)%mod);
            ToAns((ll)((-1)+mod)%mod*(i-1)%mod*(((mmax_sv[R]-mmax_sv[maxx_ext-1])%mod+mod)%mod)%mod);
        }
        else{
            //type 2
            ToAns((ll)minn*((maxx_msv[minn_ext-1]-maxx_msv[maxx_ext-1]%mod+mod)%mod)%mod);
            ToAns((ll)((-1)*minn%mod+mod)%mod*(i-1)%mod*((maxx_sv[minn_ext-1]-maxx_sv[maxx_ext-1])%mod+mod)%mod);
            //type 3
            ToAns((ll)((mmax_msv[R]-mmax_msv[minn_ext-1])%mod+mod)%mod);
            ToAns((ll)((-1)+mod)%mod*(i-1)%mod*(((mmax_sv[R]-mmax_sv[minn_ext-1])%mod+mod)%mod)%mod);           
        }
    }

    return;
}

int main(){
    Read(N);
    rep(i,1,N)
        Read(src[i]);
    Merge(1,N);
    printf("%lld\n",ans);
    return 0;
}