摘要
Title: 2972. 统计移除递增子数组的数目 II
Categories: 双指针

2972. 统计移除递增子数组的数目 II

题意

给你一个下标从 0 开始的正整数数组 nums 。

如果 nums 的一个子数组满足：移除这个子数组后剩余元素严格递增，那么我们称这个子数组为移除递增子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。

请你返回 nums 中移除递增子数组的总数目。

注意，剩余元素为空的数组也视为是递增的。

子数组指的是一个数组中一段连续的元素序列。

思路

只删除一个数组，然后要保证递增，首先找到前缀最长递增数组，和后缀最长递增数组，确认到中间的无序数组的左右边界
枚举左边的递增数组的下标，同时右指针往右移，保证右边边界的值大于左边边界的值，统计个数即可

https://leetcode.cn/problems/count-the-number-of-incremovable-subarrays-ii/solutions/2578499/cpptu-jie-by-lu-ming-b-wjtb/

代码

# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from re import L
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])
    @staticmethod
    def to_1_indexed(data: Union[List, str, List[List]]):
        """Adds a zero prefix to the data and returns the modified data and its length."""
        if isinstance(data, list):
            if all(isinstance(item, list) for item in data):  # Check if it's a 2D array
                new_data = [[0] * (len(data[0]) + 1)] + [[0] + row for row in data]
                return new_data, len(new_data) - 1, len(new_data[0]) - 1
            else:
                new_data = [0] + data
                return new_data, len(new_data) - 1
        elif isinstance(data, str):
            new_data = '0' + data
            return new_data, len(new_data) - 1
        else:
            raise TypeError("Input must be a list, a 2D list, or a string")

class Str:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
    removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)

class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)

class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))

class Std:
    pass

# ————————————————————— Division line ——————————————————————

class Solution:
    def incremovableSubarrayCount(self, arr: List[int]) -> int:
        arr, n = Arr.to_1_indexed(arr)
        
        l = 1
        while l <= n and arr[l] > arr[l - 1]:
            l += 1
        # l = arr[4] = 5
        if l == n + 1:
            return n * (n + 1) // 2

        r = n
        while r >= 1 and arr[r] > arr[r - 1]:
            r -= 1
        # r = arr[8] = 5
        ans = n - r + 2

        for i in range(1, l):
            while r <= n and arr[r] <= arr[i]:
                r += 1
            ans += n - r + 2
        
        return ans

# print(Solution().incremovableSubarrayCount([1, 2, 6, 5, 9, 3, 10, 5, 11, 12]))
# print(Solution().incremovableSubarrayCount([8,7,6,6]))
# print(Solution().incremovableSubarrayCount([6,5,7,8]))