暴力算法
枚举3个数组 时间复杂度O(n^3) 超时
根据数据范围N为1e5次方
所以大概的时间复杂度应该是O(N) 或者 O(NlogN)
所以最多只能枚举一个数组
如果枚举A数组的话，那么A是确定的
则可以确定B > A 也可以确定C > A
但是B和C的关系是不确定的
同样枚举C数组也是这个问题
如果枚举B数组 ， 则B是确定的
则可以确定B > A 也可以确定B < C
那么C也一定是大于A 就可以确定一个三元组
因为确定A < B 和 确定 C > B
这2个事件属于独立事件
所以三元组的数量应该等于 Bi > Ai的个数 * Bi < Ci 的数量（因为对于一个C > Bi , 他可以和前面所有满足B > Ai的数组成三元组）
所以问题就变成了对于任意一个Bi 求A数组中小于Bi的数，和C数组中大于Bi的数
首先第一个方法是排序 + 二分
因为A，B，C的数很小
所以第二个方法是前缀和
方法一、 排序 + 二分
时间复杂度O(NlongN)
对于每个Bi用二分在A数组找到一个临界点，这个临界点的左边都是小于Bi
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int b[N];
int c[N];
int n;
int main (){
cin >> 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(c , c + n);
//枚举B数组 确定每个Bi
long long res = 0;
for (int i = 0;i < n;i++){
int t = b[i];
//用二分在A数组中找到一个临界点，临界点左边的数都小于x
int l = 0;
int r = n - 1;
while(l < r){
int mid = l + r >> 1;
if (a[mid] >= t) r = mid;
else l = mid + 1;
}//while
long long x = l;
if (a[l] < t) x++;
//用二分在C数组中找到一个临界点，临界点右边的数都大于x
l = 0;
r = n - 1;
while(l < r){
int mid = (l + r + 1) >> 1;
if (c[mid] <= t) l = mid;
else r = mid - 1;
}
//独立事件
long long y = n - l - 1;
if (c[l] > t) y++;
res = res + x * y;
}
cout << res << endl;
return 0;
}
方法二、前缀和
时间复杂度O(N)
用前缀和求一个数组中小于（大于）x的数
前提是每个数不是很大
第一步定义一个cnt数组
遍历一遍数组，用cnt记录每个数出现的个数，即cnt[a[i]]++
第二步
对cnt数组求一遍前缀和
求比Bi小的数的个数 就是s[b[i] - 1]
s[b[i] - 1] == cnt[1] + cnt[2] + cnt[3] + ··· + cnt[b[i] - 1]
cnt[1]表示数组中1的个数，cnt[2]表示数组中2的个数
所以s[b[i] - 1]就是小于bi的所有的数的数量
因为要用到b[i] - 1 数组的下标不能为负
所以b[i]最小要是1 那就每个数都+1即可
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int a[N];
int b[N];
int c[N];
int sa[N]; //sa[i] 表示a数组小于b[i]的数量
int sc[N]; //sc[i] 表示c数组大于b[i]的数量
int n;
int cnt[N]; //cnt[i] 表示数组中i这个数的个数
int s[N]; //前缀和
int main (){
cin >> n;
for (int i = 1;i <= n;i++) scanf ("%d" , &a[i]) , a[i]++;
for (int i = 1;i <= n;i++) scanf ("%d" , &b[i]) , b[i]++;
for (int i = 1;i <= n;i++) scanf ("%d" , &c[i]) , c[i]++;
//统计a数组每个数的个数
for (auto i : a) cnt[i]++;
//对cnt求前缀和
for(int i = 1;i < N;i++) s[i] = s[i - 1] + cnt[i];
//求a数组都比bi小的数
for (int i = 1;i <= n;i++){
sa[i] = s[b[i] - 1];
//cout << sa[i] << endl;;
}
memset(cnt , 0 , sizeof cnt);
memset(s , 0 , sizeof s);
//统计c数组每个数的个数
for (auto i : c) cnt[i]++;
//对cnt求前缀和
for(int i = 1;i < N;i++) s[i] = s[i - 1] + cnt[i];
//求c数组都比bi大的数
for (int i = 1;i <= n;i++){
sc[i] = s[N - 1] - s[b[i]];
// cout << sc[i] << endl;;
}
LL res = 0;
for (int i = 1;i <= n;i++){
res = res + (LL)sa[i] * sc[i];
}
printf ("%lld\n" , res);
return 0;
}
