308030: CF1454F. Array Partition

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Array Partition

题意翻译

给定序列 $a$,要求将其划分为三个**非空子串**(设三个子串长分别为 $x,y,z$),使得 $\max\limits_{i=1}^x a_i = \min\limits_{i=x+1}^{x+y} a_i = \max\limits_{i=x+y+1}^n a_i$。 若存在方案,输出 $\texttt{YES}$ 和任意一组 $x,y,z$ 的值;若不存在,输出 $\texttt{NO}$。 $3 \le n \le 2 \cdot 10^5$,$1 \le a_i \le 10^9$ Translation by @LTb_

题目描述

You are given an array $ a $ consisting of $ n $ integers. Let $ min(l, r) $ be the minimum value among $ a_l, a_{l + 1}, \ldots, a_r $ and $ max(l, r) $ be the maximum value among $ a_l, a_{l + 1}, \ldots, a_r $ . Your task is to choose three positive (greater than $ 0 $ ) integers $ x $ , $ y $ and $ z $ such that: - $ x + y + z = n $ ; - $ max(1, x) = min(x + 1, x + y) = max(x + y + 1, n) $ . In other words, you have to split the array $ a $ into three consecutive non-empty parts that cover the whole array and the maximum in the first part equals the minimum in the second part and equals the maximum in the third part (or determine it is impossible to find such a partition). Among all such triples (partitions), you can choose any. You have to answer $ t $ independent test cases.

输入输出格式

输入格式


The first line of the input contains one integer $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of the test case contains one integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the length of $ a $ . The second line of the test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ), where $ a_i $ is the $ i $ -th element of $ a $ . It is guaranteed that the sum of $ n $ does not exceed $ 2 \cdot 10^5 $ ( $ \sum n \le 2 \cdot 10^5 $ ).

输出格式


For each test case, print the answer: NO in the only line if there is no such partition of $ a $ that satisfies the conditions from the problem statement. Otherwise, print YES in the first line and three integers $ x $ , $ y $ and $ z $ ( $ x + y + z = n $ ) in the second line. If there are several answers, you can print any.

输入输出样例

输入样例 #1

6
11
1 2 3 3 3 4 4 3 4 2 1
8
2 9 1 7 3 9 4 1
9
2 1 4 2 4 3 3 1 2
7
4 2 1 1 4 1 4
5
1 1 1 1 1
7
4 3 4 3 3 3 4

输出样例 #1

YES
6 1 4
NO
YES
2 5 2
YES
4 1 2
YES
1 1 3
YES
2 1 4

Input

题意翻译

给定序列 $a$,要求将其划分为三个**非空子串**(设三个子串长分别为 $x,y,z$),使得 $\max\limits_{i=1}^x a_i = \min\limits_{i=x+1}^{x+y} a_i = \max\limits_{i=x+y+1}^n a_i$。 若存在方案,输出 $\texttt{YES}$ 和任意一组 $x,y,z$ 的值;若不存在,输出 $\texttt{NO}$。 $3 \le n \le 2 \cdot 10^5$,$1 \le a_i \le 10^9$ Translation by @LTb_

加入题单

上一题 下一题 算法标签: