义乌中学暑假集训 2021.07.11 D

(Updated: )
oi

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#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;
}