连续区间

区间内所有元素排序后，任意相邻两个元素值差为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,5][1,5]为连续区间//[l,r]表示从第l个数到第r个数构成的区间      

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 5;

int n;
ll result = 0;
int a[MAXN];
int b[MAXN << 2];
int mx[MAXN];
int mn[MAXN];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

void solve(int left, int right)
{
    if (left == right)
    {
        result++;
        return;
    }
    
    int mid = left + (right - left) / 2;
    mx[mid] = mn[mid] = a[mid];
    for (int i = mid - 1; i >= left; i--)
    {
        mx[i] = max(a[i], mx[i + 1]);
        mn[i] = min(a[i], mn[i + 1]);
    }
    mx[mid + 1] = mn[mid + 1] = a[mid + 1];
    for (int i = mid + 2; i <= right; i++)
    {
        mx[i] = max(a[i], mx[i - 1]);
        mn[i] = min(a[i], mn[i - 1]);
    }

    for (int i = mid; i >= left; i--)
    {
        int j = i + mx[i] - mn[i];
        if (j > mid && j <= right && mx[i] > mx[j] && mn[i] < mn[j])
        {
            result++;
        }
    }
    for (int i = mid + 1; i <= right; i++)
    {
        int j = i - (mx[i] - mn[i]);
        if (j >= left && j <= mid && mx[j] < mx[i] && mn[j] > mn[i])
        {
            result++;
        }
    }

    int l = mid + 1, r = mid;
    for (int i = mid; i >= left; i--)
    {
        while (r < right && mx[r + 1] < mx[i])
        {
            r++;
            b[mn[r] + r + MAXN]++;
        }
        while (l <= r && mn[l] > mn[i])
        {
            b[mn[l] + l + MAXN]--;
            l++;
        }
        result += b[mx[i] + i + MAXN];
    }
    while (l <= r)
    {
        b[mn[l] + l + MAXN]--;
        l++;
    }

    l = mid + 1, r = mid;
    for (int j = mid + 1; j <= right; j++)
    {
        while (l > left && mx[l - 1] < mx[j])
        {
            l--;
            b[mn[l] - l + MAXN]++;
        }
        while (r >= l && mn[r] > mn[j])
        {
            b[mn[r] - r + MAXN]--;
            r--;
        }
        result += b[mx[j] - j + MAXN];
    }
    while (l <= r)
    {
        b[mn[r] - r + MAXN]--;
        r--;
    }

    solve(left, mid);
    solve(mid + 1, right);
}

int main()
{
    scan_d(n);
    for (int i = 1; i <= n; i++)
    {
        scan_d(a[i]);
    }
    solve(1, n);

    printf("%lld\n", result);

    return 0;
}