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

考虑分治。

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

令 $\max_{i=l}^rA_i=MxA,\min_{i=l}^r=MnA,\max_{i=l}^rB_i=MxB,\min_{i=l}^rB_i=MnB,\max_{i=l}^rC_i=MxC,\min_{i=l}^rC_i=MnC$。​
$$
\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}
$$
然后对于每个式子,直接分治处理,倒序枚举 $[l,mid]$​​​​​​​,然后三个指针扫 $[mid+1,r]$​​​​​ 分类讨论(取左边为最大值/取右边为最大值)。

码量稍大。

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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇