双指针

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[][] a = new int[3][N];
    static int[] left = new int[N], right = new int[N];
    static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = Integer.parseInt(sc.nextLine());

        for (int i = 0; i < 3; i++) fill(a[i], sc.nextLine().split(" "));

        for (int i = 0; i < 3; i++) Arrays.sort(a[i], 1, n + 1);

        int j = 1, k = 1;
        for (int i = 1; i <= n; i++) {
            int bi = a[1][i];

            while (j <= n && a[0][j] < bi) j++;
            left[i] = j - 1;

            while (k <= n && a[2][k] <= bi) k++;
            right[i] = n - k + 1;
        }

        long ans = 0;
        for (int i = 1; i <= n; i++) ans += (long)left[i] * right[i];

        System.out.println(ans);
    }

    static void fill(int[] arr, String[] s) {
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(s[i - 1]);
    }
}

二分

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[][] a = new int[3][N];
    static int[] left = new int[N], right = new int[N];
    static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = Integer.parseInt(sc.nextLine());

        for (int i = 0; i < 3; i++) fill(a[i], sc.nextLine().split(" "));

        for (int i = 0; i < 3; i++) Arrays.sort(a[i], 1, n + 1);

        for (int i = 1; i <= n; i++) {
            int bi = a[1][i];
            int j = 0;

            int l = 1, r = n;
            //找bi小的最大索引
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (a[0][mid] < bi) l = mid;
                else r = mid - 1;
            }
            if (a[0][l] < bi) //判断是否找到
                left[i] = l - 1 + 1;

            l = 1; r = n;
            //找比bi大的最大索引
            while (l < r) {
                int mid = l + r >> 1;
                if (a[2][mid] > bi) r = mid;
                else l = mid + 1;
            }
            if (a[2][l] > bi) //同上
                right[i] = n - l + 1;
        }

        long ans = 0;//最大值为(10^5)^3 = 10^15 < long > 10^18
        for (int i = 1; i <= n; i++) ans += (long) left[i] * right[i];

        System.out.println(ans);
    }

    static void fill(int[] arr, String[] s) {
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(s[i - 1]);
    }
}

前缀和没想到

直接抄代码了

借用y总图片

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[][] a = new int[3][N];
    static int[] sa = new int[N], sb = new int[N];
    static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = Integer.parseInt(sc.nextLine());

        //该fill会在内部实现上+1，用于去除掉0的情况
        for (int i = 0; i < 3; i++) fill(a[i], sc.nextLine().split(" "));

        //求解cnt数组
        for (int i = 1; i <= n; i++) {//前缀和可以和原数组使用同一个数组
            sa[a[0][i]]++;
            sb[a[2][i]]++;
        }

        //求cnt数组前缀和
        for (int i = 1; i < N; i++) {
            sa[i] += sa[i - 1];
            sb[i] += sb[i - 1];
        }
        //得到答案
        long ans = 0;      
        for (int i = 1; i <= n; i++) {
            int bi = a[1][i];
            ans += (long)sa[bi - 1] * (sb[N - 1] - sb[bi]);
        }

        System.out.println(ans);
    }

    static void fill(int[] arr, String[] s) {
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(s[i - 1]) + 1;
    }
}