题目描述:
给定三个整数数组
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≤10^5,
0≤Ai,Bi,Ci≤10^5
输入样例:
3
1 1 1
2 2 2
3 3 3
输出样例:
27
解题思路:
求每个满足 ai < bj < ck的组合。
可以转换为:将b固定,遍历bj,求a中小于bj的数 * c中大于bj的数,是两数相乘便是bj贡献的次数。
需要提前预处理a,c,使得as[i] = 0-i中ai小于i的个数。cs同理大于ci
由于前缀和中0为默认首相,所以将输入的a,b,c都++,与0区分开,有利于求前缀和。
参考代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int n;
int a[N],b[N],c[N];
int as[N],cs[N],cnt[N];
int s[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i],a[i]++;
for(int i=0;i<n;i++) cin>>b[i],b[i]++;
for(int i=0;i<n;i++) cin>>c[i],c[i]++;
//预处理as
for(int i=0;i<n;i++) cnt[a[i]]++;
for(int i=1;i<N;i++) s[i] = s[i-1] + cnt[i];
for(int i=0;i<n;i++) as[i] = s[b[i]-1];
memset(cnt,0,sizeof cnt);
memset(s,0,sizeof s);
//预处理cs
for(int i=0;i<n;i++) cnt[c[i]]++;
for(int i=1;i<N;i++) s[i] = s[i-1] + cnt[i];
for(int i=0;i<n;i++) cs[i] = s[N-1] - s[b[i]];
LL res = 0;
for(int i=0;i<n;i++) res += (LL)as[i] * cs[i];
cout<<res<<endl;
return 0;
}