CodeForces - 1454F Array Partition(线段树+二分)

题目链接：点击查看

题目大意：给出一个长度为 n 的序列，现在要求求出任意一组 x , y , z，满足下列条件：

1. x + y + z = n
2. max( 1 , x ) = min( x + 1 , x + y ) = max( x + y + 1 , n )

题目分析：昨晚上用单调栈写的写崩了，到现在还是不知道哪里写崩了。。太拉胯了

因为这个题目给出的序列是需要静态查询最值，用 st 表或线段树都可以快速查询，因为感觉线段树写起来简单就直接上线段树了

最简单的一种思路是直接 n^2 去枚举两个断点，然后查找符合条件的答案，不过这种方法即使配合上 st 表时间复杂度也是有点高，所以考虑优化

枚举其中的一个断点肯定是无法避免的，我们假设枚举的第一个断点记为 x，此时 max( 1 , x ) 是已经确定了的，第一步先要去找到 y 的位置，使得 min( x + 1 , x + y ) == max( 1 , x ) 才行，不难看出的一个小结论是，对于一段前缀的最值来说，是具有单调性的，更具体的来说，前缀最大值随着下标的递增，这个值只会更大而不会减小，前缀最小值亦然，所以对于第二个断点 y 我们可以直接二分去查找，此时我们已经确定下来了第一个断点 x 的位置，设第一段的最大值为 mmax1，第二段的最小值为 mmin，第三段的最大值为 mmax2，此时分四种情况讨论即可：

1. mmax1 < mmin：此时最小值的前缀偏大，需要扩大长度，故 l = mid + 1 
2. mmax1 > mmin：同上，r = mid - 1
3. mmax1 < mmax2：此时最大值的后缀偏大，需要减小长度，故 l = mid + 1 
4. mmax1 > mmax2：同上，r = mid - 1

需要注意的是，上面二分的是断点 y 的位置，所以想要扩大 mmin 的长度就需要将 y 右移，同理如果想要扩大 mmax2 的长度就需要将 y 左移

代码：
 

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
     
typedef long long LL;
     
typedef unsigned long long ull;
     
const int inf=0x3f3f3f3f;

const int N=1e6+100;

struct Node
{
	int l,r,mmin,mmax;
}tree[N<<2];

void build(int k,int l,int r)
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		scanf("%d",&tree[k].mmax);
		tree[k].mmin=tree[k].mmax;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);
	tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);
}

int query_min(int k,int l,int r)
{
	if(tree[k].l>r||tree[k].r<l)
		return inf;
	if(tree[k].l>=l&&tree[k].r<=r)
		return tree[k].mmin;
	return min(query_min(k<<1,l,r),query_min(k<<1|1,l,r));
}

int query_max(int k,int l,int r)
{
	if(tree[k].l>r||tree[k].r<l)
		return -inf;
	if(tree[k].l>=l&&tree[k].r<=r)
		return tree[k].mmax;
	return max(query_max(k<<1,l,r),query_max(k<<1|1,l,r));
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int w;
	cin>>w;
	while(w--)
	{
		int n;
		scanf("%d",&n);
		build(1,1,n);
		for(int x=1;x<n-1;x++)//枚举第一个断点x
		{
			int l=x+1,r=n-1;//二分第二个断点y
			//区间分为了三段：[1,x][x+1,y][y+1,n]
			int mmax1=query_max(1,1,x);
			while(l<=r)
			{
				int y=l+r>>1;
				int mmin=query_min(1,x+1,y);
				int mmax2=query_max(1,y+1,n);
				if(mmax1<mmin||mmax1<mmax2)
					l=y+1;
				else if(mmax1>mmin||mmax1>mmax2)
					r=y-1;
				else
				{
					puts("YES");
					printf("%d %d %d\n",x,y-x,n-y);
					goto end;
				}
			}
		}
		puts("NO");
		end:;
	}









    return 0;
}

 

本文地址：https://blog.csdn.net/qq_45458915/article/details/110138103