题目描述
给你一个数组,让你中间切两刀,分成三份 $a[1…k1],a[k1+1…k2],a[k2+1…n]$,要求满足$\max_{i=1}^{k1} a[i] = \min_{j=k1+1}^{k2} a[j] = \max_{z=k2+1}^{n} a[z]$
输入
第一行T组数据。
每组数据第一行一个n,第二行n个数。
输出
YES+三个部分的区间长度。或NO。
样例
输入
6
11
1 2 3 3 3 4 4 3 4 2 1
8
2 9 1 7 3 9 4 1
9
2 1 4 2 4 3 3 1 2
7
4 2 1 1 4 1 4
5
1 1 1 1 1
7
4 3 4 3 3 3 4
输出
YES
6 1 4
NO
YES
2 5 2
YES
4 1 2
YES
1 1 3
YES
2 1 4
思路
(枚举+线段树) $O(nlogn)$
先离散化。
设 g=$\max_{i=1}^{k1} a[i] = \min_{j=k1+1}^{k2} a[j] = \max_{z=k2+1}^{n} a[z]$
枚举这个g。
对于每一个g,我们枚举每次出现的位置j,那么k1$<$j,k2$>$j+1。在满足前缀最大值与后缀最大值等于g的前提下,贪心地使k1尽可能大,k2尽可能小,也就是使第一部分和第三部分的区间长度尽可能大,这样能使中间那部分尽可能得小。
如果$\min_{i=k1+1}^{k2}$a[i] 与g相等,也就是中间那一部分的最小值等于g,那么就找到答案了。
前缀最大值与后缀最大值O(n) 预处理,中间部分最小值询问用数据结构维护一下就可以了,我用的是线段树。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ls x<<1
#define rs x<<1|1
const int Mn=2e5+17;
struct BTree{
int left,right,mi;
}T[Mn*4];
int a[Mn],d[Mn],pre[Mn],pre2[Mn],bin[Mn],nex[Mn];
void build(int left,int right,int x){
T[x].left=left,T[x].right=right;
if(left==right){
T[x].mi=a[left];
} else{
int mid=(left+right)>>1;
build(left,mid,ls),build(mid+1,right,rs);
T[x].mi=min(T[ls].mi,T[rs].mi);
}
}
int query(int L,int R,int x){
if(L<=T[x].left&&T[x].right<=R){
return T[x].mi;
} else {
int mid=(T[x].left+T[x].right)>>1;
if(R<=mid) return query(L,R,ls);
else if(mid+1<=L) return query(L,R,rs);
return min(query(L,R,ls),query(L,R,rs));
}
}
int main(){
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),d[i]=a[i];
sort(d+1,d+1+n);
int index=unique(d+1,d+1+n)-(d+1);
for(int i=1;i<=n;++i) a[i]=lower_bound(d+1,d+1+index,a[i])-(d+1)+1;
build(1,n,1);
for(int i=1;i<=n;++i) pre[i]=max(pre[i-1],a[i]);
pre2[n+1]=0;
for(int i=n;i>=1;--i) pre2[i]=max(pre2[i+1],a[i]);
for(int i=1;i<=n;++i) bin[i]=n+1;
for(int i=n;i>=1;--i) nex[i]=bin[a[i]],bin[a[i]]=i;
bool flag=true;
for(int i=1;i<=index&&flag;++i){
int firstpos=lower_bound(pre+1,pre+1+n,i)-(pre+1)+1;
if(a[firstpos]!=i) continue;
for(int j=nex[firstpos];j<=n&&flag;j=nex[j]){
int x=j-1,y=j+1,l,r,mid;
l=1,r=j-1,x=j-1;
while(l<=r){
mid=(l+r)>>1;
if(pre[mid]<=a[j]) l=mid+1,x=mid;
else r=mid-1;
}
l=j+1,r=n,y=j+1;
while(l<=r){
mid=(l+r)>>1;
if(pre2[mid]<=a[j]) r=mid-1,y=mid;
else l=mid+1;
}
if(y>n||pre[x]!=a[j]||pre2[y]!=a[j]) continue;
if(query(x+1,y-1,1)==a[j]) {
puts("YES");
printf("%d %d %d\n",x,y-1-x,n-y+1);
flag=false;
}
}
}
if(flag) puts("NO");
}
}