连号区间数
题目描述
小明这些天一直在思考这样一个奇怪而有趣的问题：
在1 11~N NN的某个全排列中有多少个连号区间呢？
这里所说的连号区间的定义是：
如果区间[ L , R ] [L, R][L,R]里的所有元素（即此排列的第L LL个到第R RR个元素）递增排序后能得到一个长度为R − L + 1 R - L + 1R−L+1的"连续"数列，则称这个区间连号区间。
当N NN很小的时候，小明可以很快地算出答案，但是当N NN变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入描述
第一行是一个正整数N ( 1 ≤ N ≤ 50 × 10 4 ) N (1 \leq N \leq 50 \times 10^4)N(1≤N≤50×104), 表示全排列的规模。
第二行是N NN个不同的数字P i ( 1 ≤ P i ≤ N ) P_i (1 \leq P_i \leq N)Pi(1≤Pi≤N)，表示这N NN个数字的某一全排列。
输出描述
输出一个整数，表示不同连号区间的数目。
输入输出样例
示例
输入：
4 3 2 4 1输出：
7运行限制
- 最大运行时间：5s
- 最大运行内存: 64M
题目分析
题目为给你一个数组（是 1~N 的一个排列，没有重复），找出有多少个子区间 [L, R] 是“连续数”
举例：
3241区间[1,3]→324排序后234, 是一个连续数通过观察我们可以知道
m a x − m i n = = R − L max - min == R - Lmax−min==R−L
所以我们可以枚举所有区间，检验m a x − m i n = = R − L max - min == R - Lmax−min==R−L
如果相等，则该区间满足要求
代码如下：
#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;vector<int>p(n);for(inti=0;i<n;i++){cin>>p[i];}longlongans=0;for(intl=0;l<n;l++){intmn=p[l],mx=p[l];for(intr=l;r<n;r++){mn=min(mn,p[r]);mx=max(mx,p[r]);if(mx-mn==r-l){ans++;}}}cout<<ans<<endl;return0;}
