题意：

化简一下题意就是求满足 $m a x (1, x) = m i n (x + 1, y) = m a x (y + 1, n)$ 的 $l e n 1 = x, l e n 2 = y - x, l e n 3 = n - y$ 。

思路：

首先我们暴力做法就是 $n^2$ 枚举 $x, y$ 的位置，让后判断 $(y + 1, n)$ 是否符合条件，复杂度 $O(n^2logn)$ 。

考虑优化一下，我们可以只枚举

x

，让后根据

m i n

和

m a x

的可二分性，即越往后

m i n

越小，

m a x

越大。根据这个性质我们二分

y

的位置。设

m a x (1, x) = m x

，如果

[x + 1, m i d]

的

m i n

小于

m x

，那么说明位置太靠前了，需要向后移动，如果大于

m x

,说明位置太靠后了，要往前移动，如果等于

m x

的话，说明

m i n

符合了，我们就根据

[m i d + 1, n]

的

m a x

值来判断，跟判断

m i n

的方法差不多。

用的线段树，复杂度 $O(nlog^2n)$ 。

//#pragma GCC optimize(2)#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define pb push_back#define mk make_pair#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define random(a,b) ((a)+rand()%((b)-(a)+1))#define db puts("---")using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL;typedef unsigned long long ULL;typedef pair
                 
                   PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int a[N],pre[N];struct Node{ int l,r; int mi,mx;}tr[N<<2];void pushup(int u){ tr[u].mi=min(tr[L].mi,tr[R].mi); tr[u].mx=max(tr[R].mx,tr[R].mx);}void build(int u,int l,int r){ tr[u]={ l,r}; if(l==r) { tr[u].mx=tr[u].mi=a[l]; return; } build(L,l,Mid); build(R,Mid+1,r); pushup(u);}int query_max(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mx; int ans=0; if(l<=Mid) ans=max(ans,query_max(L,l,r)); if(r>Mid) ans=max(ans,query_max(R,l,r)); return ans;}int query_min(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mi; int ans=INF; if(l<=Mid) ans=min(ans,query_min(L,l,r)); if(r>Mid) ans=min(ans,query_min(R,l,r)); return ans;}bool check(int id,int mx){ int l=id+1,r=n; while(l<=r) { int mid=l+r>>1; int mi=query_min(1,id+1,mid); if(mi>mx) l=mid+1; else if(mi
                  
                   mx) l=mid+1; else if(pre[mid+1]
                   
                    =1;i--) pre[i]=max(pre[i+1],a[i]); build(1,1,n); int flag=0,mx=0;; for(int i=1;i<=n;i++) { mx=max(mx,a[i]); if(check(i,mx)) { flag=1; break; } } if(!flag) puts("NO"); for(int i=1;i<=n;i++) pre[i]=0; } return 0;}/**/