小苯的区间删除

[题目链接](https://www.nowcoder.com/practice/91495e71914a4bf7abacf80ac4309eeb)

思路

给定长度为 $n$ 的数组 $a$ ，需要选择一段区间 $[l, r]$ （ $1 \le l \le r \le n$ ）删除，使得剩余部分拼接后单调不降。求有多少种不同的区间选择方案。

关键观察

删除 $[l, r]$ 后，保留的是前缀 $a[0..l\!-\!2]$ 和后缀 $a[r..n\!-\!1]$ （0-indexed）。要使拼接后有序，需要同时满足三个条件：

前缀 $a[0..l\!-\!2]$ 本身单调不降；
后缀 $a[r..n\!-\!1]$ 本身单调不降；
前缀末尾 $\le$ 后缀开头（若两者都非空）。

预处理

令 $\mathit{pre}$ 为最长非降前缀的长度，即 $a[0..\mathit{pre}\!-\!1]$ 非降， $a[\mathit{pre}]$ 处第一次下降（若整个数组有序则 $\mathit{pre} = n$ ）。
令 $\mathit{suf}$ 为最长非降后缀的起始位置，即 $a[\mathit{suf}..n\!-\!1]$ 非降。

条件 1 等价于保留的左端点数量 $i \le \mathit{pre}$ ；条件 2 等价于保留的右部分从 $j \ge \mathit{suf}$ 开始。

枚举 + 二分搜索

枚举左边保留的元素个数 $i$ （ $0 \le i \le \mathit{pre}$ ），对于每个 $i$ ：

右部分的起始下标 $j$ 需满足 $j \ge \max(i + 1,\; \mathit{suf})$ ，其中 $j \ge i + 1$ 保证至少删除一个元素。
当 $i > 0$ 且 $j < n$ 时，还需 $a[i-1] \le a[j]$ 。由于后缀 $a[\mathit{suf}..n\!-\!1]$ 是非降的，可以二分搜索找到满足 $a[j] \ge a[i-1]$ 的最小 $j$ 。
$j$ 还可以等于 $n$ （即右部分为空），此时条件 3 自然满足。

对每个 $i$ ，有效的 $j$ 是一段连续区间 $[j_{\min},\, n]$ ，方案数为 $n - j_{\min} + 1$ 。

样例演示

以 $a = [1, 3, 2, 2, 5]$ 为例： $\mathit{pre} = 2$ （ $a[0..1] = [1,3]$ 非降）， $\mathit{suf} = 2$ （ $a[2..4] = [2,2,5]$ 非降）。

$i$ （保留左边 $i$ 个）	左边保留	$j_{\min}$	有效 $j$	方案数
0	空	$\max(1, 2) = 2$	$2, 3, 4, 5$	4
1	$[1]$	$\max(2, 2) = 2$ , $a[2]=2 \ge 1$	$2, 3, 4, 5$	4
2	$[1,3]$	$\max(3, 2) = 3$ , $a[3]=2 < 3$ , 二分得 $j=4$ , $a[4]=5 \ge 3$	$4, 5$	2

总方案数 $= 4 + 4 + 2 = 10$ 。

复杂度

时间复杂度： $O(n \log n)$ ，预处理 $O(n)$ ，枚举 $i$ 时每次二分 $O(\log n)$ 。
空间复杂度： $O(n)$ ，存储数组。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    // pre: 最长非降前缀长度
    int pre = 1;
    while(pre < n && a[pre] >= a[pre-1]) pre++;
    // suf: 最长非降后缀起始位置
    int suf = n - 1;
    while(suf > 0 && a[suf] >= a[suf-1]) suf--;
    long long ans = 0;
    for(int i = 0; i <= pre; i++){
        int lo = max(i + 1, suf); // j 的下界
        if(lo > n) continue;
        if(i == 0){
            ans += n - lo + 1;
            continue;
        }
        // 二分找第一个 j in [lo, n-1] 使得 a[j] >= a[i-1]
        int left = lo, right = n;
        while(left < right){
            int mid = (left + right) / 2;
            if(mid < n && a[mid] >= a[i-1]) right = mid;
            else left = mid + 1;
        }
        ans += n - left + 1; // j 可取 [left, n]
    }
    cout << ans << "\n";
    return 0;
}

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
        // pre: 最长非降前缀长度
        int pre = 1;
        while (pre < n && a[pre] >= a[pre - 1]) pre++;
        // suf: 最长非降后缀起始位置
        int suf = n - 1;
        while (suf > 0 && a[suf] >= a[suf - 1]) suf--;
        long ans = 0;
        for (int i = 0; i <= pre; i++) {
            int lo = Math.max(i + 1, suf);
            if (lo > n) continue;
            if (i == 0) {
                ans += n - lo + 1;
                continue;
            }
            // 二分找第一个 j in [lo, n-1] 使得 a[j] >= a[i-1]
            int left = lo, right = n;
            while (left < right) {
                int mid = (left + right) / 2;
                if (mid < n && a[mid] >= a[i - 1]) right = mid;
                else left = mid + 1;
            }
            ans += n - left + 1;
        }
        System.out.println(ans);
    }
}