暴力做法
三重for循环，判断三个数大小，若符合递增序列，则count++ 最后输出count
long count=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
if(a[i]<b[j]&&b[j]<c[k]) {
count++;
}
}
}
}`
时间复杂度为O(n^3) 通过数据7个
思路
本题要求递增三元组，也就是从三个数组中挑出元素，满足a<b<c,这样就算一种方案。
我们可以选b数组，枚举b数组中的元素，然后判断a数组中小于b[i]的元素的个数n，以及c数组中大于b[i]元素的个数m，然后相乘，即可得到方案。
至于为什么不枚举a数组或者c数组，因为枚举a数组后，b数组的值受到a数组限制，但是c数组的值又受到b数组限制，b和c相互之间不独立,因此不能直接使用乘法计算。 c同理。
寻找a数组中小于b[i]的元素的个数n，以及c数组中大于b[i]元素的个数m,有两种方案
一种是使用二分，一种是使用前缀和
二分
注意:
int类型的运算
当两个int类型的数据进行加减乘除的时候，结果仍然为int。
若运算的结果已经超过int能表示的范围，此时计算机会截断高位，保留低位的32位作为结果，因此此时结果会发生错误。
int a=10000000;
int b=10000000;
long c=a*b;
System.out.println(a*b); //276447232
System.out.println(c); // 276447232
如上，即使将相乘的结果赋值给long类型,由于执行顺序是先运算再赋值，因此int*int还是等于int 此时已经发生溢出，然后再将溢出的结果赋值给long类型，这样显然也是错误的。
因此我们需要将其中一个乘数的类型变成long类型，避免溢出。这样做之后long * int 会自动提升为 long * long 因此 b 也会隐式转换为 long ，最终结果 10000000L * 10000000L = 100000000000000L（正确值）
代码如下:
import java.util.*;
public class Main {
static int N=100010;
static int[] a=new int[N];
static int[] b=new int[N];
static int[] c=new int[N];
static int n;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for(int i=1;i<=n;i++) {
a[i]=sc.nextInt();
}
for(int i=1;i<=n;i++) {
b[i]=sc.nextInt();
}
for(int i=1;i<=n;i++) {
c[i]=sc.nextInt();
}
// 对三个数组进行排序
Arrays.sort(a,1,n+1);
Arrays.sort(b,1,n+1);
Arrays.sort(c,1,n+1);
long count=0;
for(int i=1;i<=n;i++) {
// 在b里面寻找 第一个比b[i]小的数的下标以及数值
int ar=findsmall(b[i],a);
// 在c里面寻找第一个比 b[i]大的数值以及下标
// System.out.println(ar);
int cr=findbig(b[i],c);
// System.out.println(cr);
// 统计大的所有数 进行组合
// 注意 这里一定要加long 也就是将两个乘法的结果变成long 类型 然后再相加
count+=(long)(ar)*(n-cr+1);
}
System.out.println(count);
// 暴力解法
/*
long count=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
if(a[i]<b[j]&&b[j]<c[k]) {
count++;
}
}
}
}
System.out.println(count);
*/
}
// 找第一个比该数大的数
public static int findbig(int x,int[] arr) {
int l=0;
int r=n+1;
while(l+1<r) {
int mid=(l+r)/2;
if(arr[mid]<=x) {
l=mid;
}else {
r=mid;
}
}
// 返回右边
return r;
}
// 找第一个比该数小的数
public static int findsmall(int x,int[] arr) {
int l=0;
int r=n+1;
while(l+1<r) {
int mid=(l+r)/2;
if(arr[mid]<x) {
l=mid;
}else {
r=mid;
}
}
// 返回左边
return l;
}
}
前缀和
由于我们需要计算a数组中小于b[i] 以及c数组中大于b[i] 的元素的个数，我们可以使用cnt数组分别记录下来 a数组中每个元素出现的次数 以及c数组中每个元素出现的次数，然后对于a数组和c数组中元素出现的次数分别求前缀和数组，也就是 sa[i]表示a[0]到a[i]范围中 所有元素出现的总次数。
这样的话我们求a中小于b[i]元素的个数，就只用写sa[b[i]-1]即可
求c中大于b[i]的元素的个数，就可以写为sc[N-1]-sc[b[i]] 这里写N-1是因为我们sc数组的下标实际是数值，题目中数据范围是0~100000,因此我们的数据要超过100000
注意:
前缀和数组下标是从1开始的，因为下标要进行-1操作，因此对于s数组而言，也就是统计某个数值范围出现的次数而言(也就是sa和sc),下标要从1开始，但是由于他们的下标表示的实数值，而数值范围是0~100000,因此我们需要对输入的数据进行偏移，也就是所有输入的数据都+1,这样就可以保证数值范围在 1~100001,让我们s数组的下标从1开始。
代码如下:
import java.util.*;
public class Main {
static int N=100010;
static int[] b=new int[N];
// 统计 a和c数组中每个元素出现的次数
static int[] acnt=new int[N];
static int[] ccnt=new int[N];
static int[] sac=new int[N]; // sac[i] 表示 a[0]~a[i]中所有元素出现的总次数
static int[] scc=new int[N]; // scc[i] 表示 c[0]~c[i]中所有元素出现的总次数
static int n;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
// 由于改题的数据范围是从0开始的 但是求前缀和的话我们要求下标从1开始 因为有-1操作
// sac和scc数组的下标实际就是数的范围 因此我们需要把每个数都+1 确保sac和scc的下标最小从1开始
// 将输入的 a b c 数组的数值全部偏移1 也就是+1
for(int i=1;i<=n;i++) {
int a=sc.nextInt();
a++;
acnt[a]++;
}
for(int i=1;i<=n;i++) {
b[i]=sc.nextInt()+1;
}
for(int i=1;i<=n;i++) {
int c=sc.nextInt();
c++;
ccnt[c]++;
}
// 计算前缀和数组
for(int i=1;i<=N-1;i++) {
sac[i]=sac[i-1]+acnt[i];
}
for(int i=1;i<=N-1;i++) {
scc[i]=scc[i-1]+ccnt[i];
}
long count=0;
// 枚举b中的元素
for(int i=1;i<=n;i++) {
// 统计a中比b小的元素个数
int ab=sac[b[i]-1];
// 统计c中比b大的元素个数 也就是 b[i]+1 ....
int bc=scc[N-1]-scc[b[i]];
// System.out.println(ab+"-->"+bc);
count+=(long)ab*bc;
}
System.out.println(count);
}
}
