前缀和

import java.util.Arrays;
import java.util.Scanner;
class Main{
    public static void main(String[] args){ 
        Scanner input = new Scanner(System.in);
        int n= input.nextInt();
        int N = 100010;
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for(int j = 0; j < n; j ++){
            a[j] = input.nextInt();
            a[j]++;
        }
        for(int j = 0; j < n; j ++){
            b[j] = input.nextInt();
            b[j]++;
        }
        for(int j = 0; j < n; j ++){
            c[j] = input.nextInt();
            c[j]++;
        }

        //a的前缀和
        int[] sa = new int[N];
        for(int i = 0; i < n; i ++)sa[a[i]]++;
        for(int i = 1; i < N; i ++)sa[i] = sa[i - 1] + sa[i];
        int[] aa = new int[n];
        for(int i = 0; i <  n; i ++)aa[i] = sa[b[i] - 1];//存小于b[i]的每个A


        int[] sb = new int[N];
        for(int i = 0; i < n; i ++)sb[c[i]]++;
        for(int i = 1; i < N; i ++)sb[i] = sb[i - 1] + sb[i];

        int[] bb = new int[n];
        for(int i = 0; i <  n; i ++)bb[i] = sb[N - 1] - sb[b[i]];//存小于b[i]的每个A

        long res = 0;
        for(int i = 0; i < n; i ++)res += (long)aa[i]*bb[i];
        System.out.println(res);
    }
}

双指针

import java.util.Arrays;
import java.util.Scanner;
class Main{
    public static void main(String[] args){ 
        Scanner input = new Scanner(System.in);
        int n= input.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for(int j = 0; j < n; j ++)a[j] = input.nextInt();
        for(int j = 0; j < n; j ++)b[j] = input.nextInt();
        for(int j = 0; j < n; j ++)c[j] = input.nextInt();
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        long res = 0;
        int l = 0, r = 0;
        for(int i = 0; i < n; i ++){
            //在a中找到最后一个小于B的数
            while(l < n && a[l] < b[i])l ++;
            //在c中找到第一个大于b的数
            while(r < n && c[r] <= b[i])r ++;
            res += (long)l*(n - r);
        }
        System.out.println(res);

    }
}

二分

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
class Main{
    public static void main(String[] args) { 
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for(int i = 0; i < n; i ++)a[i] = input.nextInt();
        for(int i = 0; i < n; i ++)b[i] = input.nextInt();
        for(int i = 0; i < n; i ++)c[i] = input.nextInt();
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        long res = 0;
        for(int i = 0; i < n; i ++){
            int B = b[i];
            //枚举B，找AC

            //找A
            int l = 0;
            int r = n - 1;
            int mid;
            while(l < r){
                mid = (l + r + 1)/2;
                if(a[mid] < B)l = mid;
                else r = mid - 1;
            }
            int A = a[l];
            //找C
            int l2 = 0;
            int r2 = n - 1;
            while(l2 < r2){
                mid = (l2 + r2)/2;
                if(c[mid] > B)r2 = mid;
                else l2 = mid + 1;
            }
            int C = c[l2];
            if(A < B && B < C){
                res += (long)(l + 1)*(long)(n - l2);
            }
        }
        System.out.println(res);
    }
}