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(); } }