《从入门到精通：蓝桥杯编程大赛知识点全攻略》（九）-连号区间数、递增三元组

前言

在本篇博客中，我们将通过模拟方法解决两道经典的算法题：连号区间数和递增三元组。通过这两道题，我们将展示如何通过模拟操作和细致的算法设计来解决实际问题，帮助提升算法思维和编码能力。

连号区间数

小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。
当 N很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式
第一行是一个正整数 N，表示排列的规模。
第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。
输出格式
输出一个整数，表示不同连号区间的数目。
数据范围
1≤N≤10000,1≤Pi≤N
输入样例1：

java">4
3 2 4 1

输出样例1：

java">7

输入样例2：

java">5
3 4 2 5 1

输出样例2：

java">9

样例解释
第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]

第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

算法思路

暴力做法，只需要枚举每一个区间的左端点和区间的右端点，然后分别对每一个区间进行排序，之后再对区间的元素进行遍历，当区间的后一个元素比前一个元素多一时，说明是一种方案。
这样的时间复杂度为O(n^3logn)，会超时，我们可以对区间内的元素是否是等差数列进行优化。
将区间的最大值和最小值记录一下，当区间的最大值-区间的最小值=右区间-左区间（即max- min == j-i）时就说明该方案是合格的。
此时时间复杂度是O(n^2)，能够通过。

代码如下

暴力做法

java">import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr = new int[n+1]; // 区间下标从1开始，所以n+1for (int i=1; i<=n; i++) {arr[i] = sc.nextInt();}int res = 0;for (int i=1; i<=n; i++) {for (int j=i; j<=n; j++) {int[] temp = arr.clone(); // 开一个新数组，便于每次新数组排序Arrays.sort(temp, i, j+1); // 把新数组中[i,j]排序boolean flag = true;for (int k=i; k<j; k++) {if (temp[k+1] - temp[k] != 1) {flag = false; break;}}if (flag == true) {res ++;}}}System.out.println(res);}
}

优化版本

java">import java.io.*;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int mod = 100000007;static int N = 10010;static int[] arr = new int[N];public static void main(String[] args) throws Exception {int n = nextInt();for(int i = 1; i <= n; i++){arr[i] = nextInt();}int res = 0;for(int i = 1; i <= n; i++){//枚举区间左端点int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for(int j = i; j <= n; j++){//枚举区间右端点max = Math.max(max, arr[j]);//区间最大值min = Math.min(min, arr[j]);//区间最小值if(max - min == j - i){res++;}}}pw.println(res);pw.flush();}public static int nextInt()throws Exception{st.nextToken();return (int)st.nval;}
}

递增三元组

给定三个整数数组

A=[A1,A2,…AN],B=[B1,B2,…BN],C=[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k) 满足：

1≤i,j,k≤N
Ai<Bj<Ck

输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…AN。
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。
输出格式
一个整数表示答案。
数据范围
1≤N≤10⁵,0≤Ai,Bi,Ci≤10⁵
输入样例：

java">3
1 1 1
2 2 2
3 3 3

输出样例：

java">27

算法思路

在这里插入图片描述
暴力做法直接枚举3层循环i、j、j，然后做判断满足 Ai < Bj && Bj < Ck的情况方案数加1即可，但会超时。
根据题意需要求有多少个i、j、k满足Ai<Bj<Ck，故就是求对于B数组中的每一个数Bj，在A数组中有多少个数小于Bj，在C数组中有多少个数大于Bj。
我们可以用前缀和的思路来处理这道题。对于在A中有多少个数小于Bj，用数组cnt来存储A数组中每个数出现在的次数即cnt[i]表示i这个值在A数组中出现的次数，然后求cnt数组的前缀和数组s，s[i] = cnt[0] + cnt[1]+…+cnt[i]表示在A数组中0~i出现的次数，最后求在A数组中有多少个数小于Bj即s[Bj - 1]。
求在C数组中有多少个数大于Bj，同样用前缀和的方法开处理，先将原本的cnt和s两个数组都清0，然后遍历C数组，用cnt数组统计C数组中每个值出现的次数即cnt[i]表示i这个值在C数组中出现的次数，然后求cnt数组的前缀和数组s，s[i]表示在C数组中0~i出现的次数，要求在C数组中有多少个数大于Bj即s[N -1] - s[Bj]。
最后将每一个Bj对应在A数组中有多少个数小于Bj，在C数组中有多少个数大于Bj两个结果相乘即可。

N = 100010，因为数组中数组的最大值是10⁵，需要求大于Bj的值出现的次数，需要用0 ~ 10000所有数出现的次数即s[N-1]减去0~Bj的数出现的次数即s[Bj]就是大于Bj的数出现的次数。

因为数组中每个值的范围是0~10⁵，同时我们需要统计cnt数组的前缀和数组，但此时cnt[0]表示数组中0出现的次数，而s[0]其实是无意义的，故做题时数组输入值时都加1，这样可以让cnt[0]变为无意义，s[0]也无意义，减少做题的复杂度。

在这里插入图片描述

代码如下

暴力枚举（会超时）：

java">import java.util.*;
import java.io.*;
public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int n;static int[] a = new int[N];static int[] b = new int[N];static int[] c = new int[N];public static void main(String[] args)throws Exception {int n = nextInt();for(int i = 1; i <= n; i++){a[i] = nextInt();}for(int i = 1; i <= n; i++){b[i] = nextInt();}for(int i = 1; i <= n; i++){c[i] = nextInt();}long res = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){for(int k = 1; k <= n; k++){if(a[i] < b[j] && b[j] < c[k]){res++;}}}}pw.println(res);pw.flush();}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}}

前缀和方法代码如下：

java">
import java.io.*;
import java.util.Arrays;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int n;static int[] a = new int[N];static int[] b = new int[N];static int[] c = new int[N];//as[i]在A数组中有多少个数小于b[i]static int[] as = new int[N];//cs[i]在A数组中有多少个数大于b[i]static int[] cs = new int[N];static int[] cnt = new int[N];//前缀和数组static int[] s = new int[N];public static void main(String[] args) throws Exception {n = nextInt();for (int i = 1; i <= n; i++) {a[i] = nextInt()+1;}for (int i = 1; i <= n; i++) {b[i] = nextInt()+1;}for (int i = 1; i <= n; i++) {c[i] = nextInt()+1;}//求as[]for(int i = 1; i <= n; i++){cnt[a[i]]++;}//输入的时候3个数组中的值保证了最小值是1，这样求cnt数组的前缀和的时候可以保证s[0]还是0for(int i = 1; i < N; i++){s[i] = s[i-1] + cnt[i];}for(int i = 1; i <= n; i++){as[i] = s[b[i] - 1];}//求cs[]Arrays.fill(cnt, 0);Arrays.fill(s, 0);for(int i = 1; i <= n; i++){cnt[c[i]]++;}for(int i = 1; i < N; i++){s[i] = s[i-1] + cnt[i];}for(int i = 1; i <= n; i++){cs[i] = s[N - 1] - s[b[i]];}//枚举每个b[i]long res = 0;for(int i = 1; i <= n; i++){res += (long)cs[i] * as[i];}pw.println(res);pw.flush();}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}
}