题解 | #小苯的区间删除#

题目链接

小苯的区间删除

题目描述

给定一个长度为 $n$ 的数组 $a$ ，他必须选择一个连续的区间 $[l, r]$ 并将其删除。

剩下的前缀部分和后缀部分（如果存在）将按原顺序拼接在一起，形成一个新数组。

我们需要计算，有多少种不同的区间 $[l, r]$ （ $1 \le l \le r \le n$ ）的选择方案，可以使得最终拼接成的数组是单调不降的。

注意：空数组和只包含一个元素的数组也算作有序。删除整个数组也是一种合法的方案。

解题思路

这个问题要求我们统计满足特定条件的区间数量。暴力枚举所有 $\mathcal{O}(n^2)$ 个区间并进行 $\mathcal{O}(n)$ 的检查，总复杂度为 $\mathcal{O}(n^3)$ ，会超时。我们需要更高效的方法。

1. 结构分析

删除区间 $[l, r]$ 后，留下的数组由前缀 $a[0 \dots l-2]$ 和后缀 $a[r \dots n-1]$ 拼接而成。要使新数组有序，必须满足三个条件：

前缀 $a[0 \dots l-2]$ 本身是有序的。
后缀 $a[r \dots n-1]$ 本身是有序的。
前缀的最后一个元素不大于后缀的第一个元素，即 $a[l-2] \le a[r]$ (需处理边界情况)。

2. 预处理与双指针

预处理:
- 首先，我们可以从左到右扫描，找到最长的、本身就有序的前缀。设这个前缀的结尾索引为 prefix_end。任何合法的保留前缀都必须是这个最长前缀的一部分。
- 同理，从右到左扫描，找到最长的、本身就有序的后缀。设这个后缀的起始索引为 suffix_start。
特殊情况:

如果 prefix_end >= suffix_start，说明整个数组本身就是有序的。在这种情况下，删除任何一个区间，剩下的部分自然也是有序的。总方案数就是所有可能的区间数量，即 $n(n+1)/2$ 。
双指针算法:

当数组不是完全有序时（prefix_end < suffix_start），我们可以通过双指针来高效地计数。

我们固定一个合法的前缀（由指针 i 指示），然后寻找所有能与之匹配的合法后缀（由指针 j 指示）。
1. 初始化指针 i = 0 (指向合法前缀的末尾)，j = suffix_start (指向合法后缀的开头)，答案 ans = 0。
2. 计算不保留任何前缀的情况:
  - 如果我们删除的区间从 1 开始，即 l=1，那么我们不保留任何前缀。
  - 此时，任何合法的后缀（从 suffix_start 到 n-1 的后缀，以及空后缀）都是合法的方案。
  - 方案数是 (n - suffix_start) + 1。我们将这个计入 ans。
3. 遍历所有合法的前缀:
  - 我们让指针 i 从 0 遍历到 prefix_end。i 代表我们保留的前缀是 a[0...i]。
  - 对于每一个 i，我们需要找到第一个合法的后缀起始位置 j，使得 a[i] <= a[j]。
  - 我们移动指针 j (j 从 suffix_start 开始，且不回退)，直到 a[i] <= a[j]。
  - 一旦找到这样的 j，那么从 j 到 n-1 的所有后缀，以及空后缀，都可以和当前前缀 a[0...i] 匹配。
  - 方案数是 (n - j) + 1。我们将这个计入 ans。
  - 因为随着 i 的增加, a[i] 是不降的，所以 j 只需要单向移动，这保证了算法的线性时间复杂度。
最终的 ans 就是总方案数。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin::tie(NULL);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int prefix_end = 0;
    while (prefix_end + 1 < n && a[prefix_end] <= a[prefix_end + 1]) {
        prefix_end++;
    }

    if (prefix_end == n - 1) {
        cout << (long long)n * (n + 1) / 2 << endl;
        return 0;
    }

    int suffix_start = n - 1;
    while (suffix_start - 1 >= 0 && a[suffix_start - 1] <= a[suffix_start]) {
        suffix_start--;
    }

    long long ans = 0;
    
    // Case 1: 不保留任何前缀 (删除的区间从1开始)
    ans += (n - suffix_start) + 1;

    // Case 2: 保留 a[0...i] 的前缀
    int j = suffix_start;
    for (int i = 0; i <= prefix_end; ++i) {
        while (j < n && a[i] > a[j]) {
            j++;
        }
        ans += (n - j) + 1;
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        int prefixEnd = 0;
        while (prefixEnd + 1 < n && a[prefixEnd] <= a[prefixEnd + 1]) {
            prefixEnd++;
        }

        if (prefixEnd == n - 1) {
            System.out.println((long)n * (n + 1) / 2);
            return;
        }

        int suffixStart = n - 1;
        while (suffixStart - 1 >= 0 && a[suffixStart - 1] <= a[suffixStart]) {
            suffixStart--;
        }

        long ans = 0;
        
        // Case 1: 不保留任何前缀
        ans += (n - suffixStart) + 1;

        // Case 2: 保留 a[0...i] 的前缀
        int j = suffixStart;
        for (int i = 0; i <= prefixEnd; i++) {
            while (j < n && a[i] > a[j]) {
                j++;
            }
            ans += (n - j) + 1;
        }

        System.out.println(ans);
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)
    a = list(map(int, sys.stdin.readline().split()))

    prefix_end = 0
    while prefix_end + 1 < n and a[prefix_end] <= a[prefix_end + 1]:
        prefix_end += 1

    if prefix_end == n - 1:
        print(n * (n + 1) // 2)
        return

    suffix_start = n - 1
    while suffix_start - 1 >= 0 and a[suffix_start - 1] <= a[suffix_start]:
        suffix_start -= 1
        
    ans = 0
    
    # Case 1: 不保留任何前缀
    ans += (n - suffix_start) + 1
    
    # Case 2: 保留 a[0...i] 的前缀
    j = suffix_start
    for i in range(prefix_end + 1):
        while j < n and a[i] > a[j]:
            j += 1
        ans += (n - j) + 1

    print(ans)

solve()

算法及复杂度

算法：双指针
时间复杂度: $\mathcal{O}(n)$ 。预处理最长有序前缀和后缀需要线性扫描。双指针部分，两个指针 i 和 j 都只单向遍历数组一次。
空间复杂度: $\mathcal{O}(n)$ ，用于存储输入的数组。