P8600 连号区间数

P8600 [蓝桥杯 2013 省 B] 连号区间数

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 $1$ ~ $N$ 的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：

如果区间 $[L,R]$ 里的所有元素（即此排列的第 $L$个到第 $R$ 个元素）递增排序后能得到一个长度为 $R-L+1$ 的“连续”数列，则称这个区间连号区间。

其中对“连续”数列的定义：

记长度为 $m$ 的数列 $A$ 第 $i$ 个元素为 $A_i$，当 $\forall i\in [2,m]，a_i=a_{i-1}+1$ 时认为该数列为“连续”数列。

当 $N$ 很小的时候，小明可以很快地算出答案，但是当 $N$ 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 $N(1\le N\le 50000)$， 表示全排列的规模。

第二行是 $N$ 个不同的数字 $P_i(1\le P_i\le N)$， 表示这 $N$ 个数字的某一全排列。

输出格式

输出一个整数，表示不同连号区间的数目。

输入输出样例 #1

输入 #1

4
3 2 4 1

输出 #1

7

输入输出样例 #2

输入 #2

5
3 4 2 5 1

输出 #2

9

说明/提示

第一个用例中，有 $7$ 个连号区间分别是：$[1,1]$, $[1,2]$, $[1,3]$, $[1,4]$, $[2,2]$, $[3,3]$, $[4,4]$。

第二个用例中，有 $9$ 个连号区间分别是：$[1,1]$, $[1,2]$, $[1,3]$, $[1,4]$, $[1,5]$, $[2,2]$, $[3,3]$, $[4,4]$, $[5,5]$。

原题时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛

解析

本题的题意是：统计有多少个区间 $[l,r]$，计区间最大值为 $max$，区间最小值为 $min$，区间长度为 $len=r-l$，满足关系式 $max-min=len$。

进行对原关系式的移项，有 $max-min+l=r$。

具体而言，考虑套路地枚举区间右端点 r 进行扫描线，求出以 r 为结尾的符合要求的区间个数，然后再求和。

而为了满足这一要求，我们需要使用单调栈 + 线段树维护。

考虑到 $max-min\ge r-l$，可以使用单调栈维护每个后缀的 $max$ 和 $min$，再用线段树维护 $max-min-len$ 的最小值以及其出现次数

首先明确，一个区间 $[l,r]$ 是一个连号，当且仅当该区间 $max-min=r-l$。

考虑套路地枚举右端点 r。问题转化为求满足 $max-min+l=r$ 的区间数量。

对于一个右端点 r，我们可以使用单调栈维护每一个后缀的 $max$,$min$。

现在问题就是如何快速维护这个数量。注意到 $max-min\ge r-l$，因此，用线段树维护区间最值的数量即可。

代码

//
// Created by 23264 on 2026/1/26.
//
#include<bits/stdc++.h>
using namespace std;
 
int N;
vector<int> arr;
int res;
 
// 线段树结构体：维护区间最小值及其出现次数
struct Node
{
    int minn;
    int count;
    int lazy;
}tree[500005];
 
// 向上更新
void pushUp(int rt)
{
    tree[rt].minn = min(tree[rt << 1].minn,tree[rt << 1 | 1].minn);
    tree[rt].count = 0;
    if (tree[rt].minn == tree[rt << 1].minn)
    {
        tree[rt].count += tree[rt << 1].count;
    }
    if (tree[rt].minn == tree[rt << 1 | 1].minn)
    {
        tree[rt].count += tree[rt << 1 | 1].count;
    }
}
 
// 向下下传懒标记
void pushDown(int rt)
{
    if (tree[rt].lazy != 0)
    {
        int v = tree[rt].lazy;
        tree[rt << 1].minn += v;
        tree[rt << 1].lazy += v;
        tree[rt << 1 | 1].minn += v;
        tree[rt << 1 | 1].lazy += v;
        tree[rt].lazy = 0;
    }
}
 
// 初始化线段树：初始时 V[i] = i
void build(int rt,int l,int r)
{
    tree[rt].lazy = 0;
    if (l == r)
    {
        tree[rt].minn = l;
        tree[rt].count = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1,l,mid);
    build(rt << 1 | 1,mid + 1,r);
    pushUp(rt);
}
 
// 区间修改
void update(int rt,int l,int r,int ql,int qr,int val)
{
    if (ql <= l && r <= qr)
    {
        tree[rt].minn += val;
        tree[rt].lazy += val;
        return;
    }
    pushDown(rt);
    int mid = (l + r) >> 1;
    if (ql <= mid)
    {
        update(rt << 1,l,mid,ql,qr,val);
    }
    if (qr > mid)
    {
        update(rt << 1 | 1,mid + 1,r,ql,qr,val);
    }
    pushUp(rt);
}
 
void solve()
{
    // 线段树和单调栈配合
    build(1,0,N - 1);
    stack<int> stkMax; // 维护最大值的单调栈（存下标）
    stack<int> stkMin; // 维护最小值的单调栈（存下标）
 
    for (int j = 0;j < N;j++)
    {
        // 更新最大值对 V_i 的贡献
        while (!stkMax.empty() && arr[stkMax.top()] < arr[j])
        {
            int cur = stkMax.top();
            stkMax.pop();
            int prev = stkMax.empty() ? -1 : stkMax.top();
            // 原来的 max(prev+1...cur) 是 arr[cur]，现在变成了 arr[j]
            update(1,0,N - 1,prev + 1,cur,arr[j] - arr[cur]);
        }
        stkMax.push(j);
 
        // 更新最小值对 V_i 的贡献
        while (!stkMin.empty() && arr[stkMin.top()] > arr[j])
        {
            int cur = stkMin.top();
            stkMin.pop();
            int prev = stkMin.empty() ? -1 : stkMin.top();
            // 原来的 min(prev+1...cur) 是 arr[cur]，现在变成了 arr[j]
            update(1,0,N - 1,prev + 1,cur,arr[cur] - arr[j]);
        }
        stkMin.push(j);
 
        // 此时根节点的 min_val 记录的是整个区间 [0, j] 中 max - min + i 的最小值
        // 理论最小值就是 j，满足条件即为连号区间
        if (tree[1].minn == j) {
            res += tree[1].count;
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    if (!(cin >> N))
    {
        return 0;
    }
    arr.resize(N);
    res = 0;
    for (int i = 0;i < N;i++)
    {
        cin >> arr[i];
    }
    solve();
    cout << res << endl;
}
 
// 下面也是一种解法，但是提交会有两个点TLE，需要各种卡常，我就很无奈
// void solve()
// {
//     for (int i = 0;i < N;i++)
//     {
//         int maxx = arr[i];
//         int minn = arr[i];
//         for (int j = i;j < N;j++)
//         {
//             maxx = max(maxx,arr[j]);
//             minn = min(minn,arr[j]);
//             if (maxx - minn == j - i)
//             {
//                 res++;
//             }
//         }
//     }
// }
//
// int main()
// {
//     cin >> N;
//     arr.resize(N);
//     res = 0;
//     for (int i = 0;i < N;i++)
//     {
//         cin >> arr[i];
//     }
//     solve();
//     cout << res;
// }