【题目描述】

AcWing 1236. 递增三元组

根据数据范围，推断时间复杂度应该控制在O(n * log n )以内

n≤1000 => O(n2)，O(n2logn)
n≤10000=> O(n∗n√)
n≤100000=> O(nlogn)*

若分别暴力枚举A[i] 、B [j] 、 C[k] ，则时间复杂度为O(n^3)

考虑优化：

解法一： 排序 +二分

【思路】
- 对A、C序列进行排序，排序之后便可使用二分查找最后一个小于B[j]的数的位置和第一个大于B[j]的数的位置
- 枚举B序列，二分查找，A序列中小于B[j]的个数为a = upper_bound(B[j]) + 1; C序列中大于B[j]的个数为：c = n - lower_bound(B[j]); 注意边界处理
- ans + = a *c;

二分查找O(log n)， 枚举b[j] O(n)，所以时间复杂度为O(n * log n)

import java.io.*;
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 n;
    public static long upper_bound(int target){
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            //寻找A序列中从左到右最后一个小于target的元素位置
            if( A[mid] < target) l = mid;
            else r = mid - 1;  //注意是 mid - 1
        }
        //如果未找到小于target的数
        if(A[l] >= target) l = -1;
        return l;
    }

    public static long lower_bound(int target){
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            //寻找C序列中第一个大于target的元素的位置
            if(C[mid] > target) r = mid;
            else l = mid + 1;
        }
        //如果未找到大于target的数 将l标记为n,后续计算时 n-y==0;
        if(C[l] <= target) l = n;
        return l;
    }
    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());


        String s[] = bf.readLine().split(" ");
        for(int i = 0; i < n; i ++) A[i] = Integer.parseInt(s[i]);
        String s1[] = bf.readLine().split(" ");
        for(int i = 0; i < n; i ++) B[i] = Integer.parseInt(s1[i]);
        String s2[] = bf.readLine().split(" ");
        for(int i = 0; i < n; i ++) C[i] = Integer.parseInt(s2[i]);

        //对A、C序列进行排序
        Arrays.sort(A, 0 , n);
        Arrays.sort(C, 0 , n);


        long ans = 0;
        //枚举中间的数B[j]
        for(int j = 0; j < n; j ++){
            //查找A序列中小于B[j]的数的个数
            long a = upper_bound(B[j]) + 1; 
            //查找C序列中大于B[j]的数的个数
            long c = n - lower_bound(B[j]);
            //System.out.println(a +" "+  c);
            ans +=  a * c;

        }
        System.out.println(ans);

    }
}

前缀和

【思路】
数据范围较小 10E5,空间换时间
前缀和数组prefixA[i]统计A序列中（0~i)数的个数

时空复杂度皆为O(N)

import java.io.*;
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 cntA[] = new int [N];  //统计i在A序列中出现的次数
    static int cntC[] = new int [N];  //统计i在C序列中出现的次数
    //不开成long 再进行乘法时会溢出
    static long prefixA[] = new long [N];  //prefixA[i] 表示 A序列中0 ~ i 的个数
    static long prefixC[] = new long[N];  //prefixC[i] 表示 C序列中0 ~ i 的个数

    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());


        String s[] = bf.readLine().split(" ");
        String s1[] = bf.readLine().split(" ");
        String s2[] = bf.readLine().split(" ");
        /*
        注意数据范围： 0≤Ai,Bi,Ci≤105 所以在读入对数据进行加1操作，使得数据最小从1开始
        符合前缀和  避免处理边界情况 另外数组是开多的 会有默认数据0被统计成输入的0的干扰
        */
        for(int i = 1; i <= n; i ++) {
            A[i] = Integer.parseInt(s[i - 1]) + 1;
            cntA[ A[i] ] ++;
        }
        for(int i = 1; i <= n; i ++) B[i] = Integer.parseInt(s1[i - 1]) + 1;
        for(int i = 1; i <= n; i ++) {
            C[i] = Integer.parseInt(s2[i - 1]) + 1;
            cntC[ C[i] ] ++;
        }

        //prefixA[i] 表示 A序列中0 ~ i 的个数
        for(int i = 1; i < N; i ++) prefixA[i] = prefixA[ i - 1] +cntA[i];
        for(int i = 1; i < N; i ++) prefixC[i] = prefixC[ i - 1] +cntC[i];

        long ans = 0;        


        //枚举中间的数B[j]
        for(int j = 1 ; j <= n; j ++){
            //A序列中小于B[j]的个数为   prefixA[ B[j] - 1 ]

            //C序列中大于B[j]的个数为  prefixC[N] - prefixC[ B[j]] 
            ans +=  prefixA[ B[j] - 1 ] * (prefixC[N - 1] - prefixC[ B[j]] );
        }

        System.out.println(ans);

    }
}