AcWing 1210.连号区间数（暴力枚举优化）

[题目概述]

小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1～N 的某个排列中有多少个连号区间呢？
这里所说的连号区间的定义是：
如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R?L+1 的“连续”数列，则称这个区间连号区间。
当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 N，表示排列的规模。
第二行是 N 个不同的数字 $P_i$，表示这 N 个数字的某一排列。

输出格式

输出一个整数，表示不同连号区间的数目。

数据范围

1 ≤ N ≤ 10000,
1 ≤ $P_i$ ≤ N

输入样例1：

4
3 2 4 1

输出样例1：

7

输入样例2：

5
3 4 2 5 1

输出样例2：

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]

• 分析问题
  • 题目要找一个序列有多少子序列在排序后是连续区间，最先想到的方法就是暴力枚举，两重for循环枚举左右端点，然后对此区间排序，再算一下是不是连续区间，此方法不优化会超时。
  • 但貌似没有更好的方法，只能想办法去优化，枚举左右端点是通法，不能优化了，只能从第二重循环中的内容来着手，那么再找到区间后如何判断是连续区间呢？
  • 本题的关键就是这个地方。我们可以算出此区间的最大值和最小值，如果是连续区间的话，二者差值应该和区间左右端点的差值是相同的，这样就完成了对暴力解法的优化。
• 代码解析
  我们在枚举的同时就可以算出最大值和最小值来减少时间

 for (int i = 0; i < n; i ++) {
		int maxs = 0, mins = 100000;
		for (int j = i; j < n; j ++) {
			maxs = max(maxs, a[j]);
			mins = min(mins, a[j]);
			if (maxs - mins == j - i)
				cnt ++;
		}
	}

• 完整代码

for (int i = 0; i < n; i ++) {
	int maxs = 0, mins = 100000;
	for (int j = i; j < n; j ++) {
		maxs = max(maxs, a[j]);
		mins = min(mins, a[j]);
		if (maxs - mins == j - i)
			cnt ++;
	}
}

• 本题较简单，主要就是怎样判断是连续区间的优化条件
  本题到这里就结束了，有疑问的小伙伴可以发在评论区或私信，记得点赞收藏！