题目链接
一些话
int f[N];
memset(f,0,sizeof f)影响不到f[N]
所以尽量不要对f[N]赋值，不要用f[N]操作
流程
//由三重暴力i,j,k因为三重暴力底下是分别用i和j，j和k作比较，想到可以拆成i~j,j ~k 再乘起来,
// 但 n < 1e5，双循环复杂度也还是太高，不过还有更优的方法，
// 即枚举b中元素，求b的第k个元素大于a中元素的个数，和b的第k个元素小于c中元素的个数，然后相乘。可以通过前缀和+哈希或二分来实现
// 前缀和+哈希要先统计a和c的元素个数，然后通过前缀和来得到a和c中小于等于某值的元素个数的数组，
// 然后求b的第k个元素大于a中元素的个数就是这个a中小于等于b[k] -1 的元素个数，即s[b[k] - 1]
//b的第k个元素小于c中元素的个数就是c中元素的个数减去c中小于等于b的第k个元素的个数，即s[N-1] - s[b[i]];
套路
统计数组中小于等于多个某值的元素个数：
先哈希统计元素个数，然后前缀和
1. for(int i = 0;i < n;i++) cnt[a[i]]++; 2. for(int i = 1;i < N;i++) s[i] += s[i-1] + cnt[i];
ac代码
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 1e5 + 10; int a[N],b[N],c[N],cc[N],ca[N],cnt[N],s[N]; int main(){ int n; 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]++; 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++) ca[i] = s[b[i]-1]; memset(s,0,sizeof s); memset(cnt,0,sizeof cnt); 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++) cc[i] = s[N-1] - s[b[i]]; long long ans = 0; for(int i = 0;i < n;i++){ ans += ca[i] * (long long) cc[i]; } cout << ans << endl; return 0; }
