题意
选出三个区间,区间不重叠,且完美覆盖序列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