Codeforces Round #686 (Div. 3) F. Array Partition

时间:2021-2-20 作者:admin

题意:找到三个正整数x、y、z
满足下面两个条件Codeforces Round #686 (Div. 3) F. Array Partition
思路:首先我们很容易处理得到前后缀的最大值,前缀最大值直接遍历过去就好,后缀最大值开个数组suf维护后缀最大值即可。对于中间那部分,因为不存在修改操作,是个静态的区间问题,预处理打个st表即可。
然后我们难点在于如何找到x+y的位置,满足等式

首先,我们要知道这么两个常识。
区间最小值会随着区间长度增大而保持不变或者减小
区间最大值会随着区间长度增大而保持不变或者增大
那么这里就有了单调性
所以我们枚举每个位置作为x,然后通过二分得到x+y的位置。
1、如果前缀最大值ma>min(x+1,x+y) 说明区间最小值太小了,要增大他,那么就要让区间长度变小,因为左端点是不变的,所以让r=m,缩小右端点。
2、如果前缀最大值ma<min(x+1,x+y) 说明区间最小值过大,要减少他,那么就要让区间长度增大,左端点不变,所有就让l=m,扩大右端点。
3、如果满足ma=min(x+1,x+y),我们还需要比较ma和后缀最大值,即max(x+y+1,n),如果前缀最大值更大,说明后缀偏小,那么要扩大区间长度,因为右端点n不变,所以要让左端点x+y+1缩小,即让r=m,反之让l=m.

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+50;
int lg[N],st[N][20];
int suf[N],a[N];
int getMin(int l,int r){
	int k=lg[r-l+1];
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
	for(int i=2;i<N;i++){
		lg[i]=lg[i-1];
		if(i%2==0) lg[i]=lg[i/2]+1;
	}

	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			st[i][0]=a[i];
		}
		for(int j=1;j<=18;j++){
			for(int i=1;i<=n;i++){
				st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
		}
		suf[n]=a[n];
		for(int i=n-1;i;i--) suf[i]=max(suf[i+1],a[i]);
		int k=0;
		int ma=0;
		for(int i=1;i<n;i++){
			ma=max(ma,a[i]);
			int l=i,r=n;
			while(l+1<r){
				int m=l+r>>1;
				int mi=getMin(i+1,m);
				if(ma>mi) r=m;
				else if(ma<mi) l=m;
				else {
					if(ma>suf[m+1]) r=m;
					else if(ma<suf[m+1]) l=m;
					else {
						k=m;
						break;
					}
				}
			}
			if(k){
				cout<<"YES\n";
				cout<<i<<" "<<k-i<<" "<<n-k<<endl;
				break;
			}
		}
		if(!k) cout<<"NO\n";
	}

	return 0;
}
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。