算法1 (前缀和)

• 1、acnt[i]表示在A中i这个值出现多少次,ccnt[i]表示在C中i这个值出现多少次

• 2、关键的一步，通过s[]记录当前数组从1到i中,所有数出现的次数的前缀和

• 3、as[]记录在A中由多少个数小于B[i]，as[i] = s[b[i] - 1]

• 4、cs[]记录在C中由多少个数大于B[i], cs[i] = s[N - 1] - s[b[i]]

• 5、由于a[]和c[]互斥，通过乘法原理可得res += as[i] * cs[i]

时间复杂度 $O(n)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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[] acnt = new int[N];//acnt[i]表示在A中i这个值出现多少次
    static int[] ccnt = new int[N];//ccnt[i]表示在C中i这个值出现多少次
    static int[] as = new int[N];//记录在A中由多少个数小于B[i]
    static int[] cs = new int[N];//记录在C中由多少个数大于B[i]
    static int[] s = new int[N];//求从1到i中,所有数出现的次数的前缀和
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        String[] s1 = reader.readLine().split(" ");
        String[] s2 = reader.readLine().split(" ");
        String[] s3 = reader.readLine().split(" ");
        for(int i = 1;i <= n;i++) a[i] = Integer.parseInt(s1[i - 1]) + 1;
        for(int i = 1;i <= n;i++) b[i] = Integer.parseInt(s2[i - 1]) + 1;
        for(int i = 1;i <= n;i++) c[i] = Integer.parseInt(s3[i - 1]) + 1;

        //求as[]
        for(int i = 1;i <= n;i++) acnt[a[i]] ++;
        for(int i = 1;i <= N - 1;i++) s[i] = s[i - 1] + acnt[i];
        for(int i = 1;i <= n;i++) as[i] = s[b[i] - 1];

        //求cs[]
        for(int i = 1;i <= n;i++) ccnt[c[i]] ++;
        for(int i = 1;i <= N - 1;i++) s[i] = s[i - 1] + ccnt[i];
        for(int i = 1;i <= n;i++) cs[i] = s[N - 1] - s[b[i]];

        //枚举每个b[i]
        long res = 0;
        for(int i = 1;i <= n;i++) res += (long)as[i] * cs[i];
        System.out.println(res);
    }
}

算法2（二分法）

• 1、对3个数组分别进行从小到大排序

• 2、找到a[]数组中最小的大于等于bi的元素位置la，便可知小于bi的个数为num1

• 3、找到c[]数组中最大的小于等于bi的元素位置lb，便可知大于bi的个数为num2

• 4、由于a[]和c[]互斥，通过乘法原理可知符合条件的个数为num1 * num2
  注意：当la == 0 或者 lb == n + 1时，则表示不符合条件

时间复杂度 $O(nlogn)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        String[] s1 = reader.readLine().split(" ");
        String[] s2 = reader.readLine().split(" ");
        String[] s3 = reader.readLine().split(" ");
        for(int i = 1;i <= n;i++) a[i] = Integer.parseInt(s1[i - 1]);
        for(int i = 1;i <= n;i++) b[i] = Integer.parseInt(s2[i - 1]);
        for(int i = 1;i <= n;i++) c[i] = Integer.parseInt(s3[i - 1]);
        Arrays.sort(a,1,n + 1);
        Arrays.sort(b,1,n + 1);
        Arrays.sort(c,1,n + 1);
        long res = 0;
        //枚举b[]数组
        for(int i = 1;i <= n;i++)
        {
            //找到a[]数组中最小的大于等于bi的元素位置
            int la = 0,ra = n + 1;
            while(la < ra)
            {
                int mid = (la + ra) >> 1;
                if(a[mid] >= b[i]) ra = mid;
                else la = mid + 1;
            }
            //找到c[]数组中最大的小于等于bi的元素位置
            int lb = 0,rb = n + 1; 
            while(lb < rb)
            {
                int mid = (lb + rb + 1) >> 1;
                if(c[mid] <= b[i]) lb = mid;
                else rb = mid - 1;
            }
            if(la == 0 || lb == n + 1) continue;
            res += ((long)(la - 1) *(n - lb)); 
        }
        System.out.println(res);
    }
}