义乌中学暑假集训 2021.07.11 D

yzxoi

发布于 2022-09-19 13:31:10

2830

发布于 2022-09-19 13:31:10

文章被收录于专栏：OI

义乌中学暑假集训 2021.07.11 D

Description

给定三个长度为 n 的正整数序列 A,B,C。

定义 f(X,l,r) 表示在序列 X 中，\max X_i-\min X_i。

定义一个区间 [l,r] 的权值为 f(A,l,r)\times f(B,l,r)\times f(C,l,r)。

求对于所有 1\leq l\leq r\leq n，区间 [l,r] 的权值之和对 2^{32} 取模的结果。

1\leq n\leq 10^5,1\leq A_i,B_i,C_i\leq10^9。

Solution

考虑分治。

首先答案的式子可以展开。

。

\begin{align}f(A,l,r)\times f(B,l,r)\times f(C,l,r) & = (\max_{i=l}^rA_i-\min_{i=l}^rA_i)\times(\max_{i=l}^rB_i-\min_{i=l}^rB_i)\times(\max_{i=l}^rC_i-\min_{i=l}^rC_i)\& = MxA\times MxB\times MxC-MxA\times MxB\times MnC-MxA\times MnB\times MxC-MnA\times MxB\times MxC+MxA\times MnB\times MnC+MnA\times MxB\times MnC+MnA\times MnB\times MxC-MnA\times MnB\times MnC\end{align}

码量稍大。

Code

#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
#define ui unsigned int
using namespace std;
Cn int N=1e5+10;
ui n,a[N],b[N],c[N],A[N],B[N],C[N],Ans,ans,SA[N],SB[N],SC[N],AB[N],AC[N],BC[N],ABC[N];
I void Solve1(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve1(l,mid),Solve1(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=max(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=max(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=max(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=max(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=max(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=max(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]<=A[i]) ja++;W(jb<=r&&B[jb]<=B[i]) jb++;W(jc<=r&&C[jc]<=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
I void Solve2(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve2(l,mid),Solve2(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=max(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=max(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=min(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=min(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=min(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=min(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]<=A[i]) ja++;W(jb<=r&&B[jb]>=B[i]) jb++;W(jc<=r&&C[jc]>=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
I void Solve3(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve3(l,mid),Solve3(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=min(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=min(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=max(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=max(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=min(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=min(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]>=A[i]) ja++;W(jb<=r&&B[jb]<=B[i]) jb++;W(jc<=r&&C[jc]>=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
I void Solve4(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve4(l,mid),Solve4(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=min(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=min(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=min(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=min(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=max(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=max(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]>=A[i]) ja++;W(jb<=r&&B[jb]>=B[i]) jb++;W(jc<=r&&C[jc]<=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
I void Solve5(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve5(l,mid),Solve5(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=min(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=min(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=max(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=max(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=max(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=max(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]>=A[i]) ja++;W(jb<=r&&B[jb]<=B[i]) jb++;W(jc<=r&&C[jc]<=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
I void Solve6(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve6(l,mid),Solve6(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=max(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=max(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=min(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=min(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=max(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=max(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]<=A[i]) ja++;W(jb<=r&&B[jb]>=B[i]) jb++;W(jc<=r&&C[jc]<=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
I void Solve7(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve7(l,mid),Solve7(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=max(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=max(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=max(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=max(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=min(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=min(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]<=A[i]) ja++;W(jb<=r&&B[jb]<=B[i]) jb++;W(jc<=r&&C[jc]>=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
I void Solve8(CI l,CI r){
    if(l==r) return void(Ans+=a[l]*b[l]*c[l]);
    RI i,ja,jb,jc,mid=l+r>>1;Solve8(l,mid),Solve8(mid+1,r);
    for(A[mid]=a[mid],i=mid-1;i>=l;i--) A[i]=min(A[i+1],a[i]);for(A[mid+1]=a[mid+1],i=mid+2;i<=r;i++) A[i]=min(A[i-1],a[i]);
    for(B[mid]=b[mid],i=mid-1;i>=l;i--) B[i]=min(B[i+1],b[i]);for(B[mid+1]=b[mid+1],i=mid+2;i<=r;i++) B[i]=min(B[i-1],b[i]); 
    for(C[mid]=c[mid],i=mid-1;i>=l;i--) C[i]=min(C[i+1],c[i]);for(C[mid+1]=c[mid+1],i=mid+2;i<=r;i++) C[i]=min(C[i-1],c[i]);
    SA[mid]=SB[mid]=SC[mid]=AB[mid]=AC[mid]=BC[mid]=ABC[mid]=0;
    for(i=mid+1;i<=r;i++) SA[i]=SA[i-1]+A[i],SB[i]=SB[i-1]+B[i],SC[i]=SC[i-1]+C[i],AB[i]=AB[i-1]+A[i]*B[i],AC[i]=AC[i-1]+A[i]*C[i],BC[i]=BC[i-1]+B[i]*C[i],ABC[i]=ABC[i-1]+A[i]*B[i]*C[i];
    for(ja=jb=jc=mid+1,i=mid;i>=l;i--){
        W(ja<=r&&A[ja]>=A[i]) ja++;W(jb<=r&&B[jb]>=B[i]) jb++;W(jc<=r&&C[jc]>=C[i]) jc++;
             if(ja<=jb&&jb<=jc) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jb-1]-SA[ja-1])+C[i]*(AB[jc-1]-AB[jb-1])+ABC[r]-ABC[jc-1];
        else if(ja<=jc&&jc<=jb) Ans+=A[i]*B[i]*C[i]*(ja-mid-1)+B[i]*C[i]*(SA[jc-1]-SA[ja-1])+B[i]*(AC[jb-1]-AC[jc-1])+ABC[r]-ABC[jb-1];
        else if(jb<=ja&&ja<=jc) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[ja-1]-SB[jb-1])+C[i]*(AB[jc-1]-AB[ja-1])+ABC[r]-ABC[jc-1];
        else if(jb<=jc&&jc<=ja) Ans+=A[i]*B[i]*C[i]*(jb-mid-1)+A[i]*C[i]*(SB[jc-1]-SB[jb-1])+A[i]*(BC[ja-1]-BC[jc-1])+ABC[r]-ABC[ja-1];
        else if(jc<=ja&&ja<=jb) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[ja-1]-SC[jc-1])+B[i]*(AC[jb-1]-AC[ja-1])+ABC[r]-ABC[jb-1];
        else if(jc<=jb&&jb<=ja) Ans+=A[i]*B[i]*C[i]*(jc-mid-1)+A[i]*B[i]*(SC[jb-1]-SC[jc-1])+A[i]*(BC[ja-1]-BC[jb-1])+ABC[r]-ABC[ja-1];
    }
}
int main(){
    RI i;for(scanf("%u",&n),i=1;i<=n;i++) scanf("%u",&a[i]);for(i=1;i<=n;i++) scanf("%u",&b[i]);for(i=1;i<=n;i++) scanf("%u",&c[i]);
    Solve1(1,n),Solve2(1,n),Solve3(1,n),Solve4(1,n),ans=Ans,Ans=0,
    Solve5(1,n),Solve6(1,n),Solve7(1,n),Solve8(1,n),ans+=-Ans;
    return printf("%u\n",ans),0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-07-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

max