本文共 1670 字，大约阅读时间需要 5 分钟。

开始想错了方向…害

其实很简单,直接暴力枚举$x$

然后区间扩张的话,最大值不减,最小值不加,这就有单调性

那么可以得到$[1,x]$的最大值$kl$

那么在区间$[x+1,n-1]$去二分一个$x+y$使得$[x+1,x+y]$的最小值等于$kl$

当最小值等于$kl$时,就根据$[x+y+1,n]$的区间最大值去二分

总之就是双二分…

维护区间最值这里用的线段树,实际上如果用$st$表会快很多

#include 
   
    using namespace std;#define mid (l+r>>1)#define ls (rt<<1) #define rs (rt<<1|1)#define lson ls,l,mid#define rson rs,mid+1,rconst int maxn = 2e5+10;int a[maxn],mi[maxn<<2],mx[maxn<<2];void push_up(int rt,int l,int r){
   	mi[rt] = min( mi[ls],mi[rs] );	mx[rt] = max( mx[ls],mx[rs] );}void build(int rt,int l,int r){
   	if( l==r ){
    mi[rt]=mx[rt]=a[l]; return; }	build(lson); build(rson);	push_up(rt,l,r);}int askmin(int rt,int l,int r,int L,int R){
   	if( L>r||R
    
     =L&&r<=R )	return mi[rt];	return min( askmin(lson,L,R),askmin(rson,L,R) );}int askmax(int rt,int l,int r,int L,int R){
   	if( L>r||R
     
      =L&&r<=R )	return mx[rt];	return max( askmax(lson,L,R),askmax(rson,L,R) );}int main(){
   	int t,n; cin >> t;	while( t-- )	{
   		cin >> n;		for(int i=1;i<=n;i++)	cin >> a[i];		build(1,1,n);		int mid1=-1,mid2=-1;		for(int i=1;i<=n-2;i++)//枚举第一段的起使位置 		{
   			int x = askmax(1,1,n,1,i);			int l=i+1,r=n-1,MID;			while( r>=l )			{
   				MID = l+r>>1;				int two = askmin(1,1,n,i+1,MID);				int three = askmax(1,1,n,MID+1,n);				if( two
      
       x )	l=MID+1;				else//相等了,那么比较后缀 				{
   					if( three
       
        x )	l=MID+1;					else	{
    mid1=i,mid2=MID; break; }				}			}			if( mid1!=-1 )	break;		}		if( mid1!=-1 )	printf("YES\n%d %d %d\n",mid1,mid2-mid1,n-mid2);		else	printf("NO\n");	}}
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110223757 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！