2205 D. Simons and Beating Peaks

data structures, divide and conquer, dp, greedy, implementation, trees, 1700

https://codeforces.com/contest/2205/problem/D

My loveliest wishes dissolved into the air; At eighteen, I poured my dreams into the mic to share.

— SHUN, 720

We call an array 𝑏 of length 𝑚 cool if and only if:

There exists no index 𝑖 (1<𝑖<𝑚) such that 𝑏𝑖=max({𝑏𝑖−1,𝑏𝑖,𝑏𝑖+1}).

Simons has an array 𝑎 of size 𝑛. Initially, the array is a permutation∗.

He must perform the following operation until the array is cool:

Choose an index 𝑖 (1<𝑖<𝑛) such that 𝑎𝑖=max({𝑎𝑖−1,𝑎𝑖,𝑎𝑖+1}).
Then, he can remove either 𝑎𝑖−1 or 𝑎𝑖+1 from the array. After removal, a gap appears in the array, and the left and right sides of the gap will be rejoined.

Find the minimum number of operations for Simons to perform.

∗A permutation of length 𝑛 is an array consisting of 𝑛 distinct integers from 1 to 𝑛 in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (𝑛=3 but there is 4 in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤5⋅104). The description of the test cases follows.

The first line contains an integer 𝑛 (3≤𝑛≤5⋅105) — the size of 𝑎.

The second line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛, all 𝑎𝑖-s are distinct) — the array Simons has initially.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 5⋅105.

Output

For each test case, print a single integer — the minimum number of operations for Simons to perform.

Example

input

5
3
1 2 3
5
4 1 3 2 5
6
4 5 3 6 2 1
7
6 5 1 7 4 2 3
15
7 4 10 12 9 14 5 3 8 11 1 15 2 13 6

output

Note

In the first test case, the array is cool initially, so Simons can't perform any operation. The answer is 0.

In the second test case, Simons can perform as follows:

Choose index 3, because 𝑎3=max({𝑎2,𝑎3,𝑎4}). Then, he removes 𝑎2 from the array. The array becomes [4,3,2,5].

We can see the array is cool now. Thus, the answer is 1.

In the third test case, Simons can perform as follows:

Choose index 2. Then, he removes 𝑎1 from the array. The array becomes [5,3,6,2,1].
Choose index 3. Then, he removes 𝑎2 from the array. The array becomes [5,6,2,1].
Choose index 2. Then, he removes 𝑎1 from the array. The array becomes [6,2,1].

Thus, Simons makes the array cool in 3 operations.

【汤立祥、物理学院】思路：这道题目很有意思，要看你怎么去思考这个问题。本题要求我们去选择 $a_{i} = max {a_{i - 1}, a_{i}, a_{i + 1}}$ 的区间，然后删去 $a_{i - 1}$ 或 $a_{i + 1}$ ，直到这类区间不存在。但是你会发现无论怎么删，整个序列的最大值一定不会被删掉。因此我们可以先保留好最大值。

第二个注意点就是最大值一定在边缘上，因为若最大值不是边缘的值，一定就是整个序列中的“峰”，是本题结果不允许的，所以最后的序列肯定就在最大值的左区间或右区间内。我们由此将原先的问题分为两个小问题来解决。

这种解决问题的方式就和二叉树的结构很相似，具体而言，我们可以选取整个序列的最大值为根，其左孩子是左区间的最大值，右孩子是右区间的最大值，……依次类推。（查了一下发现这种树叫做笛卡尔树，有 $O (n)$ 复杂度的构建算法）。若要进行最少次数的删除，就意味着需要保留最多的元素，最多元素的数量也就是整棵树的高度。

整体上而言，想到分治→二叉树之后就可以轻松解决这个问题了。

代码：

python

import sys
from collections import deque
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
    
    def calc_depth(self):
        bfs_deque = deque([(self, 1)])
        max_depth = 1
        while bfs_deque:
            curr, depth = bfs_deque.popleft()
            if depth > max_depth:
                max_depth = depth
            if curr.left:
                bfs_deque.append((curr.left, depth+1))
            if curr.right:
                bfs_deque.append((curr.right, depth+1))
        return max_depth
        
input_data = list(map(int, sys.stdin.read().split()))
input_ptr = iter(input_data)

def build_cartesian_tree(seq) -> TreeNode:
    stack = []
    for x in seq:
        node = TreeNode(x)
        last = None
        while stack and stack[-1].val < x:
            last = stack.pop()
        node.left = last
        if stack:
            stack[-1].right = node
            
        stack.append(node)
    return stack[0] if stack else None
        

def solve():
    n = next(input_ptr)
    lst = [next(input_ptr) for _ in range(n)]
    cart = build_cartesian_tree(lst)
    print(n - cart.calc_depth())

def main():
    t = next(input_ptr)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

2205 D. Simons and Beating Peaks ​

2205 D. Simons and Beating Peaks