借鉴大佬博客 ：https://blog.csdn.net/qq_45458915/article/details/110138103
题意:
将给定数组分成 x y z 长度的三部分，并满足 max(1,x)=min(x+1,x+y)=max(x+y+1,n) ，输出任意一组满足题意的x y z;如果不存在,输出"NO;
思路：
处理区间最值直接上线段树，重点是处理区间长度分配问题。
枚举遍历 x 断点不可避免，如果也去朴素的遍历断点 y ，时间复杂度将爆炸（我自己想到这里就崩了，大佬的二分是真的秒，老蒟蒻了）
随着区间的增大 ，区间最大值递增不减 ， 区间最小值递减不增
设第一段区间最大值 f1,中间区间的最小值 fMin ,第三段区间的最大值 f2; // 以下区间均指中间区间
1. f1 > fMin 区间需减小（使 fMin 尽可能变大）， r=mid-1;
2. f1 < fMin 区间需增大 （使 fMin 尽可能减小）， l=mid+1;
3. f1 > f2 区间需减小 （使 f2 尽可能增大）， r=mid-1;
4. f1 < f2 区间需增大 （使 f2 尽可能减小）， l=mid+1;
1 #include<bits/stdc++.h>
2 #define db double
3 using namespace std;
4 typedef long long ll;
5 const int inf =0x3f3f3f3f;
6 const int qs =2e5+7;
7 struct node{
8 int Min,Max;
9 };
10 struct Tree{
11 int Max,Min,l,r;
12 }t[qs*4];
13 int n,T,A[qs];
14 void build(int p,int l,int r){
15 t[p].l=l; t[p].r=r;
16 if(l==r){
17 t[p].Max=t[p].Min=A[l];
18 return ;
19 }
20 int mid=(l+r)>>1;
21 build(p*2,l,mid);
22 build(p*2+1,mid+1,r);
23 t[p].Max=max(t[p*2].Max,t[p*2+1].Max);
24 t[p].Min=min(t[p*2].Min,t[p*2+1].Min);
25 }
26 node ask(int p,int l,int r){
27 if(l<=t[p].l&&r>=t[p].r){
28 node b;
29 b.Max=t[p].Max;
30 b.Min=t[p].Min;
31 return b;
32 }
33 int mid=(t[p].l+t[p].r)>>1;
34 node f;
35 f.Min=inf,f.Max=-1;
36 if(l<=mid){
37 node a=ask(p*2,l,r);
38 f.Min=min(f.Min,a.Min);
39 f.Max=max(f.Max,a.Max);
40 }
41 if(r>mid){
42 node a=ask(p*2+1,l,r);
43 f.Max=max(a.Max,f.Max);
44 f.Min=min(f.Min,a.Min);
45 }
46 return f;
47 }
48 void solve(){
49 int mid;
50 for(int i=1;i<n-1;++i){
51 int l=i+1,r=n-1;
52 node f;
53 f=ask(1,1,i);
54 int f1=f.Max;
55 while(l<=r){
56 mid=(l+r)>>1;
57 f=ask(1,i+1,mid);
58 int fMin=f.Min;
59 f=ask(1,mid+1,n);
60 int f3=f.Max;
61 if(f1>fMin||f1>f3) r=mid-1;
62 else if(f1<fMin||f1<f3) l=mid+1;
63 else{
64 printf("YES
");
65 printf("%d %d %d
",i,mid-i,n-mid);
66 return;
67 }
68 }
69 }
70 puts("NO");
71 }
72 int main(){
73 std::ios::sync_with_stdio(false);
74 cin>>T;
75 while(T--){
76 cin>>n;
77 for(int i=1;i<=n;++i) cin>>A[i];
78 build(1,1,n);
79 solve();
80 }
81 return 0;
82 }