分析

从 0~N-1 如果区间上排序后数字连续（每次加一），那么，最大-最小=R-L

正解

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl

//data
typedef long long LL;
const int N=100010;

//module
int n;
int a[N];



void AcWing(){

    cin>>n;
    ffor(i,0,n) scanf("%d",&a[i]);

    int ans=n;//区间长为一

    ffor(l,0,n-1){
        int minx=a[l],maxx=a[l];
        ffor(r,l+1,n){//从左端点下一个开始
            minx=min(a[r],minx);
            maxx=max(a[r],maxx);
            if((maxx-minx)==(r-l)) ans++;
        }
    }

    out(ans);nl;
}

int main(){


    AcWing();
    return 0;
}

只通过了8/10

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl

//data
typedef long long LL;
const int N=100010;

//module
int n;
int a[N];

//
bool check(int l,int r){

    if(l+1==r){
        return abs(a[r]-a[l])==1;
    }

    int minx=n,maxx=-1;

    ffor(i,l,r+1){
        minx=min(a[i],minx);
        maxx=max(a[i],maxx);

        if((maxx-minx)>(r-l)) return false;
    }

    return true;
}


void AcWing(){

    cin>>n;
    ffor(i,0,n) scanf("%d",&a[i]);

    int ans=n+1;//区间长为一，或n的符合

    ffor(len,2,n){//按长度扫描
        int e=n-len+1;
        ffor(left,0,e){
            int right=left+len-1;
            if(check(left,right)) ans++;//这里check也有O(n),最后变成O(n^3)
            //如果能在O(1)复杂度得到区间的某种性质，如求和，才能这样写
        }
    }

    out(ans);nl;
}

int main(){


    AcWing();
    return 0;
}