1810 连续区间
基准时间限制：1.5 秒 空间限制：131072 KB 分值: 80
区间内所有元素排序后，任意相邻两个元素值差为1的区间称为“连续区间”
如：3,1,2是连续区间，但3,1,4不是连续区间
给出一个1~n的排列，求出有多少个连续区间
Input
一个数n(n<=1,000,000)
第二行n个数,表示一个1~n的排列
Output
一个数，表示有多少个连续区间
Input示例
5
2 1 5 3 4
Output示例
9
样例解释：
区间[1,1][2,2][3,3][4,4][5,5][1,2][4,5][3,4][1,5]为连续区间//[l,r]表示从第l个数到第r个数构成的区间
题解：
分治计数
先将序列划分为左右两边，只考虑左端点在左边部分，右端点在右边部分的答案
也就是左边部分对右边部分答案的贡献
可知
Max{max(i),max(j)} - Min{min(i),min(j)} = j - i;
共有4中互不影响的情况，其实这里分类讨论下就可以O(1)求出
#include <bits/stdc++.h>
inline long long read(){long long x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}return x*f;}
using namespace std;
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 1e6 + , M = , inf = 1e9; LL ans,mx[N],mx1[N],mn[N],mn1[N],vis[N * ];
int a[N],n; void solve(int ll,int rr) {
if(ll == rr) return ;
int last1 = -,last2 = inf;
for(int i = mid; i >= ll; --i)
mx[i] = max(last1,a[i]),last1 = mx[i],
mn[i] = min(last2,a[i]),last2 = mn[i];
last1 = -,last2 = inf;
for(int i = mid+; i <= rr; ++i)
mx1[i] = max(last1,a[i]),last1 = mx1[i],
mn1[i] = min(last2,a[i]),last2 = mn1[i]; for(int i = ll; i <= mid; ++i) {
int tmp = i + mx[i] - mn[i];
if(tmp > mid && tmp <= rr
&& mx[i] > mx1[tmp] && mn[i] < mn1[tmp]) ans+=;
} for(int i = mid+; i <= rr; ++i) {
int tmp = i - mx1[i] + mn1[i];
if(tmp >= ll && tmp <= mid
&& mx1[i] > mx[tmp] && mn1[i] < mn[tmp]) ans+=;
}
int l = mid+,r = mid;
for(int i = mid; i >= ll; --i) {
while(r < rr && mx[i] > mx1[r+]) ++r, vis[r+mn1[r]+n]++;
while(l <= r && mn[i] < mn1[l]) vis[l+mn1[l]+n]--,++l;
ans += vis[i+mx[i]+n];
}
while(l <= r) vis[l+mn1[l]+n]--,l++; l = mid, r = mid+;
for(int i = mid+; i <= rr; ++i) {
while(r > ll && mx1[i] > mx[r-]) r--,vis[r-mn[r]+n]++;
while(l >= r && mn[l] > mn1[i]) vis[l-mn[l]+n]--,l--;
ans += vis[i-mx1[i]+n];
}
while(l >= r) vis[l-mn[l]+n]--,l--;
solve(ll,mid),solve(mid+,rr);
}
int main() {
scanf("%d",&n);
for(int i = ; i <= n; ++i) a[i] = read();
solve(,n);
printf("%lld\n",ans+n);
return ;
}