[题解]51nod_1810_连续区间（排列分治乱搞

https://www.cnblogs.com/LukeStepByStep/p/7420829.html

首先要发现一个区间如果是连续区间，因为是一个排列没有重复数字，那么一定有$r-l+1==max(a[i])-min(a[i]) (l<=i<=r)$

然后考虑分治，每次计算$l,r$在$mid$左右两边的答案（应该是统计区间个数常用技巧，分类讨论

设$mx,mn$为从$mid$开始一直到$i$这段区间的最大/最小值

两种情况，一种是$mx,mn$不在$mid$同一边取到，一种是在同一边

如果在同一边，例如左边，会有 $mx[i]-mn[i]=j-i$，这样枚举$i$可以直接算出$j$，直接判断是否合法（在区间内并且能使$i$取到最值

如果不在同一边，例如$i$在左边，$mx[i]-mn[j]=j-i$，$mx[i]+i=mn[j]+j$，这样该怎么统计呢

这样取的条件是$mx[i]>mx[j] mn[i]>mn[j]$，可以看到合法的$j$一定在一个区间内（重要（因为是从mid到j的区间，所以如果前面mx不满足，越往后mx递增更不可能满足，确定了一个右边界，如果前面mn不满足，越往后mn递减可能就满足，这样确定了一个左边界）

那我们不如维护这个区间的左右端点，从上面的分析基本让人联想到尺取，随着$i$的不断枚举，也是$mx$递增$mn$递减，这样$mx$限制变松右边界可以后移，$mn$限制变紧左边界可以后移，所以维护这个区间，每加入一个数就$cnt[mn[j]+j]++$

出去就--，最后$ans+=cnt[mx[i]+i]$，注意有负下标需要加偏移量

再处理一些细节即可

#pragma GCC optimize(19260817)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1000009;
int n,a[maxn];ll ans;
int mn[maxn],mx[maxn];
ll cnt[3*maxn];
void work(int l,int r){
    int mid=l+r>>1;
    mn[mid]=mx[mid]=a[mid];
    mn[mid+1]=mx[mid+1]=a[mid+1];
    for(int i=mid+2;i<=r;i++)mn[i]=min(mn[i-1],a[i]),mx[i]=max(mx[i-1],a[i]);
    for(int i=mid-1;i>=l;i--)mn[i]=min(mn[i+1],a[i]),mx[i]=max(mx[i+1],a[i]);
    for(int i=l;i<=mid;i++){
        int j=mx[i]-mn[i]+i;
        if(j>mid && j<=r && mx[i]>mx[j] && mn[i]<mn[j])ans++;//在范围内并且可以取到最值 
    }
    for(int i=mid+1;i<=r;i++){
        int j=i-mx[i]+mn[i];
        if(j<=mid && j>=l && mx[i]>mx[j] && mn[i]<mn[j])ans++;
    }
    int pl=mid+1,pr=mid+1;
    for(int i=mid;i>=l;i--){
        while(pr<=r && mx[pr]<mx[i])cnt[mn[pr]+pr+maxn]++,pr++;
        while(pl<pr && mn[pl]>mn[i])cnt[mn[pl]+pl+maxn]--,pl++;
        ans+=cnt[mx[i]+i+maxn];
    }
    while(pl<pr)cnt[mn[pl]+pl+maxn]=0,pl++;
    pl=mid,pr=mid;
    for(int i=mid+1;i<=r;i++){
        while(pr>=l && mx[pr]<mx[i])cnt[mn[pr]-pr+maxn]++,pr--;
        while(pl>pr && mn[pl]>mn[i])cnt[mn[pl]-pl+maxn]--,pl--;
        ans+=cnt[mx[i]-i+maxn];
    }
    while(pl>pr)cnt[mn[pl]-pl+maxn]=0,pl--;
    if(l==r)return;
    work(l,mid);work(mid+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    work(1,n);
    printf("%lld",ans+n);
}