题目描述

一维前缀和，三个数组可以想象成一个数组，中间的就是b数组的值

样例

import java.util.*;

public class Main {
    /*
       其实就是  a中所有小于b[i]的数出现的次数 < b[i] < c中所有大于b[i]的数出现的次数
       对于b的一个位置来说，一次结果= a中所有小于b[i]的数出现的次数 * c中所有大于b[i]的数出现的次数

       整个结果就是，对上面语句循环b.length次，把每一次的结果进行相加
    */

    static final int N = 100010;
    static int[] cntSum1 = new int[N], b = new int[N], cntSum2 = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //统计a当中每个数出现的次数
        for (int i = 1; i <= n; i ++) cntSum1[sc.nextInt() + 1] ++;
        //对b[i] + 1是为了出现求解cntSum1[- 1]的情况，也就是b有取0，所以数组a, c跟着+1才不影响大小关系   对于b数组直接读入
        for (int i = 1; i <= n; i ++) b[i] = sc.nextInt() + 1;
        //统计c当中每个数出现的次数
        for (int i = 1; i <= n; i ++) cntSum2[sc.nextInt() + 1] ++;

        //计算a、c当中每个数出现的次数的前缀和 注意i <= N-1  整个数组都要遍历
        for (int i = 1; i <= N - 1; i ++) {
            cntSum1[i] += cntSum1[i - 1];
            cntSum2[i] += cntSum2[i - 1];
        }
        //结果可能爆int 数的最大为10的5次方 因为下面有乘法
        long res = 0;
        /*
         由于a < b < c 所以对于b[i] 左边出现的所有可能就是cntSum[b[i] - 1],也就是a前缀和的b[i]-1个位置，即小于b的所有数

         对于b[i] 右边出现的所有可能就是cntSum2[N - 1] - cntSum2[b[i]], 
         也就是b前缀和的N-1（最右）位置 - b前缀和的b[i]位置，即大于b的所有数
         注意不是cntSum2[b[i] - 1]，b[i]位置不需要保留的,也就是[l,r)，a到c严格增
        */

        for (int i = 1; i <= n; i ++)
            res += (long) cntSum1[b[i] - 1] * (cntSum2[N - 1] - cntSum2[b[i]]);
        System.out.println(res);
    }
}