AcWing
1210. 连号区间数
枚举右端点，n种，对于每个右端点i，有左端点j∈[1, i]，总共枚举n(n+1)/2次。对于确定的右端点，每次枚举左端点，记录下区间的最大值和最小值，其差值如果恰好等于区间右端点索引和左端点索引的差值，那么就是一个连号区间。时间复杂度为$O(n^2)$，但是实际只需要枚举$\frac{n(n+1)}{2}\approx 5\times 10^7$次，正好可以过。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 10010;
int p[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
int res = 0;
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= n; i++){
int maxe = p[i], mine = p[i];
for(int j = i; j >= 1; j--){
if(p[j] < mine) mine = p[j];
if(p[j] > maxe) maxe = p[j];
if(maxe - mine == i - j) res++;
}
}
cout << res;
return 0;
}