义乌中学暑假集训 2021.07.11 D

2022-09-19 13:31:10 浏览数 (1)

义乌中学暑假集训 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)。

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

1leq nleq 10^5,1leq A_i,B_i,C_ileq10^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)& = MxAtimes MxBtimes MxC-MxAtimes MxBtimes MnC-MxAtimes MnBtimes MxC-MnAtimes MxBtimes MxC MxAtimes MnBtimes MnC MnAtimes MxBtimes MnC MnAtimes MnBtimes MxC-MnAtimes MnBtimes MnCend{align}

码量稍大。

Code

代码语言：javascript复制
#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("%un",ans),0;
}
max min ode

0 人点赞