传送门

题解：

这道题是用模拟，如果使用暴力的话，显然需要3重循环，然后再写一个判断条件。那么我们就要从这三重循环下手进行优化，根据数据范围可以知道总的时间复杂度大概是O(n)或者O(nlogn)，那三重循环我们只能保留一重循环，观察发现保留A数组的循环和保留C数组的循环本质是一样的，但是如果保留A数组的循环的话，B数组和C数组是有关联的，写程序就比较麻烦，可以发现当保留B数组的时候，只需要找到A数组中比它小的，C数组中比它大的就行，A和C本身并无关联。我们保留了B数组的循环，接下来可以用前缀和的方法来解决这道题，可以先定义一个cnt数组，cnt[i]记录的是数组A中小于等于i的数的数量（之所以能这样写，是因为数据范围比较小），那么cnt[B[i]-1],就是数组A中所有比B[i]小的数的数量了，同理可以求出C数组中所有比B[i]大的数的数量。最后每次将小于B[i]的数的数量和大于B[i]的数的数量相乘，然后累加，就得出答案了。

#include <iostream> #include <algorithm> #include <cmath> #include <cstring> using namespace std; const int maxn=1e5+7; typedef long long ll; int a[maxn],b[maxn],c[maxn],cnta[maxn],cntc[maxn]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { scanf("%d",&a[i]); cnta[a[i]]++; } for(int i=0;i<n;i++) scanf("%d",&b[i]); for(int i=0;i<n;i++) { scanf("%d",&c[i]); cntc[c[i]]++; } for(int i=1;i<maxn;i++) { cnta[i]+=cnta[i-1]; cntc[i]+=cntc[i-1]; } ll ans=0; for(int i=0;i<n;i++) { ans+=(ll)cnta[b[i]-1]*(cntc[100001]-cntc[b[i]]);//这儿一定要将后面的数强制转换- }//成ll,因为两个1e5的数有可能爆int cout<<ans; return 0; }