AcWing 1236. 递增三元组 (flag + 前缀和 | 二分 | 滑动窗口)

1236. 递增三元组

解题思路

• 最开始想到3重循环枚举三个数组，然后最内层用条件语句判断一下即可，但是数据范围为$10^5$，三重循环肯定会超时
• 那么这道题很可能需要的算法复杂度为$O(n)$或$O(nlogn)$，所以只能枚举一个数组，那么枚举哪一个呢？
• 根据题目来看，要求$A_i<B_j<C_k$，那么就来枚举B数组
• 此时我们只需要找到A数组中所有小于$B_j$的数和C数组中所有大于$B_j$的数，然后将这两个数乘起来就是ans
• 如何找到A数组中所有小于$B_j$的数和C数组中所有大于$B_j$的数且在遍历B数组的for循环内部的时间复杂度要低于O(n)
  • 方法一：flag + 前缀和
  • 方法二：排序 + 二分
  • 方法三：滑动窗口

方法一：flag + 前缀和 O(n)

思路：

• 计数排序思想：先初始化flag数组用来记录a数组每个数出现的次数
• 计算flag数组的前缀和数组 s[n]，那么 s[i] 就表示从a数组中所有取值在 [0, i] 区间内的元素个数
• 那么计数 a数组 中所有小于 b[j] 的数就相当于求a数组中取值在 [0, b[j] - 1] 区间内的元素个数，即求s[b[j] - 1]，b数组同理

import java.util.*;
import java.io.*;
import java.math.*;

class Main {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String sp[];
    
    int N = 100010;

    int[] a = new int[N], b = new int[N], c = new int[N];
    int n;
    
    int[] flag_a = new int[N];
    int[] s_flag_a = new int[N];
    
    int[] flag_c = new int[N];
    int[] s_flag_c = new int[N];

     void run() throws Exception {
        sp = reader.readLine().split(" ");
        n = Integer.parseInt(sp[0]);

        sp = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sp[i]);
        }

        sp = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sp[i]);
        }

        sp = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(sp[i]);
        }
        
        // 用a数组初始化flag_a数组
        for (int i = 0; i < n; i++) {
            flag_a[a[i]]++;
            flag_c[c[i]]++;
        }
        
        s_flag_a[0] = flag_a[0];
        s_flag_c[0] = flag_c[0];
        
        // 得到flag_a数组和flag_c数组的前缀和数组
        for (int i = 1; i < N; i++) {
            s_flag_a[i] = s_flag_a[i - 1] + flag_a[i];
            s_flag_c[i] = s_flag_c[i - 1] + flag_c[i];
        }
        
        BigInteger cnt = new BigInteger("0");
        // 遍历b数组
        for (int i = 0; i < n; i++) {
            BigInteger cnt_a = new BigInteger(String.valueOf(b[i] - 1 < 0 ? 0 : s_flag_a[b[i] - 1]));
            BigInteger cnt_c = new BigInteger(String.valueOf(n - s_flag_c[b[i]]));
            cnt = cnt.add(cnt_a.multiply(cnt_c));
        }
        
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
}

方法二：排序 + 二分 O(nlogn)

注意：

• 二分的条件必须为：a数组和b数组中有一部分大于b[i]和小于b[i]的数，需要特判一下全小于等于或者全大于等于b[i]的情况，否则二分会出错
• Arrays.sort(int[] arr, int startIndex, int endIndex)时需要注意的是[startIndex, endIndex)，和substring一样
• N的数据范围为$10^5$，那么最多可能出现的次数为$10^{10}$会爆long，所以要用大数类
• 大数类的运算方法不会直接修改大数的值，需要重新赋值
• 调试技巧：当二分出现错误的时候从两个方向考虑，排序和二分

import java.util.*;
import java.io.*;
import java.math.*;

class Main {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String sp[];

    int[] a = new int[100010], b = new int[100010], c = new int[100010];
    int n;

     void run() throws Exception {
        sp = reader.readLine().split(" ");
        n = Integer.parseInt(sp[0]);

        sp = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sp[i]);
        }

        sp = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sp[i]);
        }

        sp = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(sp[i]);
        }

        // 对a数组和c数组先排序
        Arrays.sort(a, 0, n);
        Arrays.sort(c, 0, n);

        BigInteger cnt = new BigInteger("0");

        // 遍历b数组
        for (int i = 0; i < n; i++) {
            
            BigInteger cnt_a = new BigInteger("0"); 
            BigInteger cnt_c = new BigInteger("0");;

            // 从a数组中找到所有小于b[i]的数
            // 其最大值比b[i]还小那么cnt_a = n
            // 其最小值不小于b[i]那么cnt_a = 0
            // 有一部分小于b[i]，一部分大于b[i]，则用二分找到第一个大于b[i]的数的下标
            
            
            if (a[n - 1] < b[i]) cnt_a = new BigInteger(String.valueOf(n));
            else if (a[0] >= b[i]) cnt_a = new BigInteger(String.valueOf(0));
            else cnt_a = new BigInteger(String.valueOf(searchFirstBigOrEqualNum(b[i])));

            // 从c数组中找到所有大于b[i]的数
            // 其最小值比b[i]还那么cnt_c = n
            // 其最大值不大于b[i]那么cnt_c = 0
            if (c[0] > b[i]) cnt_c = new BigInteger(String.valueOf(n));
            else if (c[n - 1] <= b[i]) cnt_c = new BigInteger(String.valueOf(0));
            else cnt_c = new BigInteger(String.valueOf(n - searchFirstBigNum(b[i]))); 

            cnt = cnt.add(cnt_a.multiply(cnt_c));
        }
        System.out.println(cnt);
    }

    int searchFirstBigOrEqualNum(int target) {
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (a[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    int searchFirstBigNum(int target) {
        
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (c[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
    
    public static void main(String[] args) throws Exception {
        new Main().run();
    }
}

本文地址：https://blog.csdn.net/k909397116/article/details/109189695