题目描述
给定三个整数数组A = [A1,A2,…AN] , B = [B1,B2,…BN] , C = [C1,C2,…CN] , 请你统计有多少个三元组 (i,j,k) 满足:
1 ≤ i , j , k ≤ N
Ai < Bj < Ck
输入格式
第一行包含一个整数 N 。
第二行包含 N 个整数 A1,A2,…AN 。
第三行包含 N 个整数 B1,B2,…BN 。
第四行包含 N 个整数 C1,C2,…CN 。
输出格式
一个整数表示答案。
数据范围
1 ≤ N ≤ 105 ,
0 ≤ Ai , Bi , Ci ≤ 105
输入样例:
3
1 1 1
2 2 2
3 3 3
输出样例:
27
二分 $O(nlog2n)$
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[N],b[N],c[N],n;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
for(int i=0;i<n;i++)
scanf("%d",&c[i]);
sort(a,a+n);sort(b,b+n);sort(c,c+n);
LL res=0;
for(int i=0;i<n;i++)
{
int pos1=lower_bound(a,a+n,b[i])-a-1;
int pos2=upper_bound(c,c+n,b[i])-c;
if(pos1>=0&&pos2<n)
res+=(LL)(pos1+1)*(n-pos2);
}
cout<<res<<endl;
return 0;
}
双指针 $O(nlog2n)$
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[N],b[N],c[N],n;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
for(int i=0;i<n;i++)
scanf("%d",&c[i]);
sort(a,a+n);sort(b,b+n);sort(c,c+n);
LL res=0;
int j=0,t=0;
for(int i=0;i<n;i++)
{
while(j<n&&a[j]<b[i])
j++;
while(t<n&&c[t]<=b[i])
t++;
res+=(LL)j*(n-t);
}
printf("%lld\n",res);
return 0;
}
前缀和 $O(n)$
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[N],cnt_a[N],sum_a[N],b[N],c[N],cnt_c[N],sum_c[N],n;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
cnt_a[++a[i]]++;
}
for(int i=1;i<N;i++)
sum_a[i]=sum_a[i-1]+cnt_a[i];
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
b[i]++;
}
for(int i=0;i<n;i++)
{
scanf("%d",&c[i]);
cnt_c[++c[i]]++;
}
for(int i=1;i<N;i++)
sum_c[i]=sum_c[i-1]+cnt_c[i];
LL res=0;
for(int i=0;i<n;i++)
{
res+=(LL)sum_a[b[i]-1]*(sum_c[N-1]-sum_c[b[i]]);
}
printf("%lld\n",res);
return 0;
}