题目描述

关系

内容

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 $1\sim N$ 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 $[L,R]$ 里的所有元素（即此排列的第 $L$ 个到第 $R$ 个元素）递增排序后能得到一个长度为 $R-L+1$ 的“连续”数列，则称这个区间连号区间。

当 $N$ 很小的时候，小明可以很快地算出答案，但是当 $N$ 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 $N$，表示排列的规模。

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

输出格式

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

数据范围

$1\le N\le 10000$,
$1\le P_i\le 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]$

问题分析

最初思路

用区间 dp 的思路，第一维度用长度进行枚举，第二维再枚举左端点。

现在的问题就是如何判断连续？我们需要再 ${\displaystyle O(1)}$ 的时间复杂度下判断是否连续。我能想到的直接方法就是先找最小的，然后再找最大的。但是复杂度并不符合要求。如果不依赖于前面的数据，那么时间复杂度很难是常数。

思路分析

由于是排列，所以对于区间 ${\displaystyle [a,b]}$，若区间最大值 max，最小值 min，满足 ${\displaystyle b-a=max-min}$. 则必定是连续区间。

如何寻找最大值和最小值呢？只需要依赖前面即可，注意到我们每次都是从左边界开始扩充的，所以，最值一开始一定都位于左边界。

所以，我们可以随着右边界的扩大，逐步的更新最值。

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
int n, res;
int a[N], b[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    for (int i = 0; i < n; i++) {
        int ma = a[i], mi = a[i];
        for (int j = i; j < n; j++) {
            ma = max(ma, a[j]);
            mi = min(mi, a[j]);
            
            if (ma - mi == j - i) res++;
        }
    }
    
    cout << res;
    return 0;    
}