摘要
Title: 1210. 连号区间数
Tag: 模拟、st表
Memory Limit: 64 MB
Time Limit: 1000 ms

1210. 连号区间数

题意

小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1∼N 的某个排列中有多少个连号区间呢？
这里所说的连号区间的定义是：
如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。
当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
思路

核心思路：当一个区间内的区间长度和极差相同，那么就是符合的区间
- 可以用st表进行 $O(1)$ 查询
- 随着j的增加，动态更新最大值和最小值

代码

st表

/*
* @Author: NEFU AB-IN
* @Date: 2022-03-24 15:38:38
* @FilePath: \ACM\Acwing\1210.cpp
* @LastEditTime: 2022-03-24 15:38:52
*/
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
const int N = 1e5 + 10;
typedef long long LL;

int n;
int maxsum[N][30];
int minsum[N][30];
int Log[N]; // 用来求log的
int a[N];

void log_init() // 求log的函数
{
    Log[1] = 0;
    for (int i = 2; i <= n; i++)
        Log[i] = Log[i / 2] + 1;
}

void rmq_init()
{
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);
            minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);
        }
}
int query(int l, int r)
{
    int k = Log[r - l + 1];
    int Max = max(maxsum[l][k], maxsum[r - (1 << k) + 1][k]);
    int Min = min(minsum[l][k], minsum[r - (1 << k) + 1][k]);
    return Max - Min;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxsum[i][0] = minsum[i][0] = a[i];
    }
    log_init();
    rmq_init();
    LL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            if (query(i, j) == j - i)
                ans += (1LL);
        }
    }
    cout << ans << '\n';
    return 0;
}

'''
Author: NEFU AB-IN
Date: 2022-03-24 15:56:38
FilePath: \ACM\Acwing\1210.py
LastEditTime: 2022-03-24 15:56:38
'''
INF = int(4e9)

n = int(input())
a = list(map(int, input().split()))
a = [0, *a]
# mn, mx = [0] * (n + 1), [0] * (n + 1)

ans = 0
for i in range(1, n + 1):
    mx, mn = -INF, INF
    for j in range(i, n + 1):
        mx = max(mx, a[j])
        mn = min(mn, a[j])
        if mx - mn == j - i:
            ans += 1

print(ans)

1210. 连号区间数

题意

思路

代码