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

题目链接

小苯的区间删除

题目描述

小苯有一个长度为 $n$ 的数组 $a$ ，他想要使得数组有序（单调不降）。为此，他必须选择一段区间 $[l,r]$ ，将数组的这一段删除，其他的部分（如果存在的话）就按顺序拼在一起。

现在他想知道有多少种不同的选择区间的方案。注：小苯认为，空数组也满足有序，即你可以选择 $[1,n]$ 这个区间。

输入:

第一行一个正整数 $n$ ，表示数组的长度
第二行 $n$ 个正整数 $a_i$ ，表示数组 $a$

输出:

一个正整数表示答案

解题思路

这是一个区间问题，可以通过以下步骤优化解决：

关键发现：
- 对于每个位置 i，我们可以预处理：
  - p[i] 表示从位置 i 向左最多有多少个连续递增的数
  - s[i] 表示从位置 i 向右最多有多少个连续递增的数
- 如果要删除区间 [l,r]，那么 l-1 和 r+1 位置的数必须能够连接
优化策略：
- 枚举左端点 i，如果 p[i-1] < i-1，说明左边部分不是递增的，可以直接退出
- 对于每个左端点，二分查找右端点：
  - 找到最小的位置 j，使得 s[j] = n-j+1（右边部分递增）且 a[i-1] <= a[j]
  - 从 j 到 n 的所有位置都可以作为右端点
具体步骤：
- 预处理 p 和 s 数组
- 枚举左端点，二分查找右端点
- 统计合法方案数

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 2);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[n + 1] = inf;  // 添加哨兵，简化边界处理
    
    // 预处理连续递增长度
    vector<int> p(n + 1), s(n + 2);
    for(int i = 1; i <= n; i++) {
        if(a[i] >= a[i - 1]) {
            p[i] = p[i - 1] + 1;
        } else {
            p[i] = 1;
        }
    }
    for(int i = n; i; i--) {
        if(a[i] <= a[i + 1]) {
            s[i] = s[i + 1] + 1;
        } else {
            s[i] = 1;
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int x = a[i - 1];
        if(p[i - 1] < i - 1) break;  // 左边部分不递增，后面都不用看了
        
        // 二分查找右端点
        int l = i, r = n + 1;
        while(l < r) {
            int mid = l + r >> 1;
            if(s[mid] == (n - mid + 1) && x <= a[mid]) r = mid;
            else l = mid + 1;
        }
        ans += n - l + 1;  // l到n的所有位置都可以作为右端点
        ans += l > i;  // 如果l>i，说明可以不删除i位置
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static final int INF = (int)2e9;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int[] a = new int[n + 2];
        for(int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        a[n + 1] = INF;
        
        // 预处理连续递增长度
        int[] p = new int[n + 1];
        int[] s = new int[n + 2];
        for(int i = 1; i <= n; i++) {
            if(a[i] >= a[i - 1]) {
                p[i] = p[i - 1] + 1;
            } else {
                p[i] = 1;
            }
        }
        for(int i = n; i > 0; i--) {
            if(a[i] <= a[i + 1]) {
                s[i] = s[i + 1] + 1;
            } else {
                s[i] = 1;
            }
        }
        
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            int x = a[i - 1];
            if(p[i - 1] < i - 1) break;
            
            // 二分查找右端点
            int l = i, r = n + 1;
            while(l < r) {
                int mid = (l + r) >> 1;
                if(s[mid] == (n - mid + 1) && x <= a[mid]) r = mid;
                else l = mid + 1;
            }
            ans += n - l + 1;
            ans += l > i ? 1 : 0;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
INF = int(2e9)
a = [0] + list(map(int, input().split())) + [INF]

# 预处理连续递增长度
p = [0] * (n + 1)
s = [0] * (n + 2)
for i in range(1, n + 1):
    if a[i] >= a[i - 1]:
        p[i] = p[i - 1] + 1
    else:
        p[i] = 1

for i in range(n, 0, -1):
    if a[i] <= a[i + 1]:
        s[i] = s[i + 1] + 1
    else:
        s[i] = 1

ans = 0
for i in range(1, n + 1):
    x = a[i - 1]
    if p[i - 1] < i - 1:
        break
    
    # 二分查找右端点
    l, r = i, n + 1
    while l < r:
        mid = (l + r) >> 1
        if s[mid] == (n - mid + 1) and x <= a[mid]:
            r = mid
        else:
            l = mid + 1
    ans += n - l + 1
    ans += l > i

print(ans)

算法及复杂度

算法：前缀预处理 + 二分查找
时间复杂度： $\mathcal{O}(n \log n)$ - 预处理 O(n)，每个左端点二分查找 O(log n)
空间复杂度： $\mathcal{O}(n)$ - 需要存储预处理数组