AcWing 1236. 开空间小一点的前缀和解法
原题链接
中等
作者:
MongoRolls
,
2022-02-15 23:02:26
,
所有人可见
,
阅读 146
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N],b[N],c[N];
int as[N],cs[N];//as[i]cs[i]都表示a[]数组c[]数组里小于i这个值的个数
int main()
{
int n,amax=0,cmax=0;
LL ans=0;
cin>>n;
for(int i = 1; i <= n; i ++ ){scanf("%d",&a[i]);as[a[i]]++;amax=max(a[i],amax);}
for(int i = 1; i <= n; i ++ )scanf("%d",&b[i]);
for(int i = 1; i <= n; i ++ ){scanf("%d",&c[i]);cs[c[i]]++;cmax=max(c[i],cmax);}
for(int i = 1; i <= N; i ++ )as[i]+=as[i-1];
for(int i = 1; i <= N; i ++ )cs[i]+=cs[i-1];
for(int i = 1; i <= n; i ++)ans+=(LL)as[b[i]-1]*(n-cs[b[i]]);//大于b[i]的c数量用(n-cs[b[i]])表示
cout<<ans<<endl;
return 0;
}