思路：
枚举最后一部分，根据最后一部分的最大值确定若干个可能的第一部分，再从这些候选中二分查找确定最终答案。利用了前缀最大值和子段最小值的单调性。
实现：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int N = 200005; 5 int a[N], st[N][20]; 6 int log2(int x) 7 { 8 int res = -1; 9 while (x) { x >>= 1; res++; } 10 return res; 11 } 12 void init(int n) 13 { 14 for (int i = 0; i < n; i++) st[i][0] = a[i]; 15 for (int j = 1; (1 << j) < n; j++) 16 { 17 for (int i = 0; i + (1 << j) - 1 < n; i++) 18 { 19 st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); 20 } 21 } 22 } 23 int query(int l, int r) 24 { 25 if (l > r) return INF; 26 int p = log2(r - l + 1); 27 return min(st[l][p], st[r - (1 << p) + 1][p]); 28 } 29 int main() 30 { 31 int t; cin >> t; 32 while (t--) 33 { 34 int n; cin >> n; 35 for (int i = 0; i < n; i++) cin >> a[i]; 36 init(n); 37 vector<int> prefix_max(n, 0), suffix_max(n, 0); 38 prefix_max[0] = a[0]; 39 for (int i = 1; i < n; i++) prefix_max[i] = max(prefix_max[i - 1], a[i]); 40 suffix_max[n - 1] = a[n - 1]; 41 for (int i = n - 2; i >= 0; i--) suffix_max[i] = max(suffix_max[i + 1], a[i]); 42 int L = -1, R = -1; 43 for (int i = n - 1; i >= 0; i--) 44 { 45 int x = suffix_max[i]; 46 int l = lower_bound(prefix_max.begin(), prefix_max.begin() + i, x) - prefix_max.begin() + 1; 47 int r = upper_bound(prefix_max.begin(), prefix_max.begin() + i, x) - prefix_max.begin(); 48 if (l > r) continue; 49 while (l <= r) 50 { 51 int m = l + r >> 1; 52 int tmp = query(m, i - 1); 53 if (tmp < x) l = m + 1; 54 else 55 { 56 if (tmp == x) { L = m; break; } 57 r = m - 1; 58 } 59 } 60 if (L != -1) { R = i; break; } 61 } 62 if (L != -1) 63 { 64 int end = n - R, mid = n - L - end; 65 cout << "YES" << endl; 66 cout << L << " " << mid << " " << end << endl; 67 } 68 else cout << "NO" << endl; 69 } 70 return 0; 71 }