题目地址

https://codeforces.com/contest/1454/problem/F

题目大意

给一串序列，是否能有一种方案把序列划分成连续的三段$d1,d2,d3$，使得$max(d1)=min(d2)=max(d3)$。

比如序列$[1,2,3,3,3,4,4,3,4,2,1]$可以划分成$[1,2,3,3,3,4],[4],[3,4,2,1]$

解法

这题我是根本想不到要二分。这题的二分比较奇妙。

首先预处理两个$max$,从头开始的$max$值从结尾开始的$max$值（用于快速查询$d1$和$d3$)。再维护一个st表查询区间最小值$min$（用于快速查询$d2$）

设$d2$左右端点分别为$l,r$。

我们枚举$l$再二分寻找$r$,复杂度$O(n^2)$

如果$min(d2)>max(d1)$，说明d2太长或者d1太短，这时候l已经固定，所以只能让d2变短，即mid向左移动。
如果$max(d1)>max(d3)$，说明d1太长或者d3太短，这时候l已经固定，所以只能让d3变长，即$mid$向左移动。

再看看这句对不对？

如果$min(d2)>max(d3)$，说明$d2$太长或者$d3$太短，所以应该向左移动$mid$?

不对，因为在向左移动$mid$的时候，$max(d3)$增大的同时$min(d2)$也在增大，并不是在向更接近的地方行进，所以不行！

while(l<r){
	mid = (l+r)>>1;
	tmp = qry(i,mid);
	//这里我一开始多写了个条件就是max2和tmp比较的,这个不能有
	//因为扩的时候max2和tmp都可能下降，并不是往更接近的方向走
    if(tmp>max1[i-1]||max1[i-1]<max2[mid+1])
		l = mid+1;
	else if(tmp<max1[i-1]||max1[i-1]>max2[mid+1])
		r = mid-1;
	else break;
}

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define log(x) (31-__builtin_clz(x))//谢谢hjt
const int MAXN = 2e5+5;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int LOGN = log(MAXN)/log(2); 
int M[MAXN][LOGN+3]; 
int a[MAXN];
int z,m,n;
int max1[MAXN];
int max2[MAXN];

void init(){//初始化，复杂度O(nlogn) 
	for(int i=1;i<=n;i++) M[i][0]=i;//长度为1的区间最值是自己 
	for(int j=1;j<=LOGN;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			if(a[M[i][j-1]]<a[M[i+(1<<(j-1))][j-1]]) M[i][j] = M[i][j-1];//这里以最小值为例 
			else M[i][j] = M[i+(1<<j-1)][j-1];
		}
	} 
}
inline int query(int l,int r){
	int k = log(r-l+1)/log(2);//向下取整
	if(a[M[l][k]]<a[M[r-(1<<k)+1][k]]) return M[l][k];
	else return M[r-(1<<k)+1][k];
}
inline int qry(int l,int r){
    return a[query(l,r)];//直接返回数值
}
bool flag;
void solve(){
    int la,lb,lc;
    flag = 0;
    cin>>n;
    rep(i,1,n) cin>>a[i];
    init();
    max1[0]=max2[n+1] = 0;
    rep(i,1,n) max1[i] = max(max1[i-1],a[i]);//前缀最大值
    repb(i,n,1) max2[i] = max(max2[i+1],a[i]);
    int l,r,mid,tmp;
    rep(i,2,n-1){//枚举中间段的开头
        l = i,r = n-1;//二分
        while(l<r){
            mid = (l+r)>>1;
            tmp = qry(i,mid);
            //这里我一开始多写了个条件就是max2和tmp比较的,这个不能有
            //因为扩的时候max2和tmp都可能下降，并不是往更接近的方向走
            if(tmp>max1[i-1]||max1[i-1]<max2[mid+1])
                l = mid+1;
            else if(tmp<max1[i-1]||max1[i-1]>max2[mid+1])
                r = mid-1;
            else break;
        }
        mid = (l+r)>>1;
        if(mid>=i&&mid<=n-1){
            tmp = qry(i,mid);
            if(tmp==max1[i-1]&&tmp==max2[mid+1]){
                flag = 1;
                la = i-1,lb = mid-i+1,lc = n-mid;
                break;
            }
        }
    }
    if(!flag) cout<<"NO"<<endl;
    else{
        cout<<"YES"<<endl;
        cout<<la<<' '<<lb<<' '<<lc<<endl;
    }
}
signed main(){
    int z;
    cin>>z;
    while(z--) solve();
}
//二分yyds