首页 > 其他分享 >Array Partition

Array Partition

时间:2022-10-08 20:23:16浏览次数:42  
标签:200000 bb int Partition mid printf 区间 Array

题意

选出三个区间,区间不重叠,且完美覆盖序列a[n]

左区间最大值等于中区间最小值等于右区间最大值

可以发现,在左区间确定的情况下,中区间和右区间的断点是具有单调性的

越往左,中区间最小值会减小,右区间的最大值会减小

所以简简单单的二分以后求一下前缀最大和后缀后最大,维护一下区间最小值,即可

#include<bits/stdc++.h>
using namespace std;
int tree[2000000],x[200000],y[200000],a[200000];
void build(int l,int r,int p)
{
	if (l==r) 
	{
		tree[p]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
int query(int l,int r,int x,int y,int p)
{
	if (l==x&&r==y) return tree[p];
	else
	{
		int mid=(l+r)>>1;
		if (y<=mid) return query(l,mid,x,y,p<<1);
		else
		{
			if (x>mid) return query(mid+1,r,x,y,p<<1|1);
			else
			{
				int tmp=query(l,mid,x,mid,p<<1);
				tmp=min(tmp,query(mid+1,r,mid+1,y,p<<1|1));
				return tmp;
			}
		}
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int n,flag(0);
		scanf("%d",&n);
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);	
		build(1,n,1);
		x[1]=a[1], y[n]=a[n];
		for (int i=2;i<=n;i++) x[i]=max(x[i-1],a[i]);
		for (int i=n-1;i>=1;i--) y[i]=max(y[i+1],a[i]);
		for (int i=1;i<=n-2;i++)
		{
			int aa=x[i];
			int l(i+1),r(n-1);
			while (l<=r)
			{
				int mid=(l+r)>>1;
				int bb=query(1,n,i+1,mid,1),cc=y[mid+1];
				if (aa==bb&&bb==cc) 
				{
					printf("YES\n");
					printf("%d %d %d\n",i,mid-i,n-mid);
					flag=1; i=n;
					break;
				}
				if (bb<aa) r=mid-1; 
				if (bb>aa) l=mid+1;
				if (aa==bb)
				{
					if (cc<aa) r=mid-1;
					if (cc>aa) l=mid+1;
				}
			}
		}
		if (flag==0) printf("NO\n");
	}
	return 0;
}

标签:200000,bb,int,Partition,mid,printf,区间,Array
From: https://www.cnblogs.com/by-w/p/16770098.html

相关文章