递增三元组
给定三个整数数组
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN]，
请你统计有多少个三元组(i, j, k) 满足：
1. 1 <= i, j, k <= N
2. Ai < Bj < Ck
【输入格式】
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
第三行包含N个整数B1, B2, ... BN。
第四行包含N个整数C1, C2, ... CN。
对于30%的数据，1 <= N <= 100
对于60%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
【输出格式】
一个整数表示答案
【输入样例】
3
1 1 1
2 2 2
3 3 3
【输出样例】
27
思路： 因为 A[i]，B[i], C[i] 的数据范围为 0~100000
所以可以开两个数组，num1[100010], num2[100010]。
num1[i] 代表数组A 中 小于等于 i 的数字数目
num2[i] 代表数组B 中 大于等于 i 的数字数目
遍历B组中的数字，含有 B[i] 组成的序列组合数为 num1[ B[i]-1 ] * num2[ B[i]+1 ]
因为这道题没测过数据，如果有问题请大家指教。QAQ
代码如下：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100000;
int b[N+10], num1[N+10], num2[N+10];
//num1[i] 代表数组A 中 小于等于 i 的数字数目
//num2[i] 代表数组B 中 大于等于 i 的数字数目
int main(){
int n;
cin >> n;
memset(num1, 0, sizeof(num1)); // 初始化
memset(num2, 0, sizeof(num2));
int temp;
for(int i=1; i<=n; i++) {
cin >> temp;
num1[temp] ++;
}
for(int i=1 ;i<=n; i++) {
cin >> b[i];
}
for(int i=1; i<=n; i++) {
cin >> temp;
num2[temp] ++;
}
for(int i=1; i<=N; i++) {
num1[i] += num1[i-1];
}
for(int i=N; i>=1; i--) {
num2[i] += num2[i+1];
}
long long ans = 0;
for(int i=1; i<=n; i++) {
if(b[i] == 0)
continue;
ans += num1[b[i]-1]*num2[b[i]+1];
// 遍历B组中的数字，
// 含有 B[i] 组成的序列组合数为 A[ B[i]-1 ] * C [ B[i]+1 ]
}
cout << ans << endl;
return 0;
}