欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-28 16:27:19
题意:找到三个正整数x、y、z满足下面两个条件思路:首先我们很容易处理得到前后缀的最大值。前缀最大值直接遍历过去就好,后缀最大值开个数组suf维护后缀最大值即可。对于中间那部分,因为不存在修改操作,是个静态的区间问题,预处理打个st表即可。然后我们难点在于如何找到x+y的位置,满足等式首先,我们要知道这么两个常识。区间最小值会随着区间长度增大而保持不变或者减小区间最大值会随着区间长度增大而保持不变或者增大那么这里就有了单调性。所以我们枚举每个位置作为x,然后通过二分得到x+y的位置。1、如...

题意:找到三个正整数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;
}

本文地址:https://blog.csdn.net/qq_43563669/article/details/110122497