F. Array Partition(Codeforces Round #686 (Div. 3))
Codeforces Round #686 (Div. 3)
枚举第一段区间。得到一个max值。
再对第三段区间进行二分，很显然区间越大max越大，满足单调性。
二分得到满足条件的一段区间l到r。
最后再l-1到r-1区间二分满足第二段区间的答案。
两种二分方法
1.二分+线段树RMQ
二分区间，用线段树RMQ进行判断 时间 复杂度为(O（nlog^2n）)
2.线段树上二分
首先找到二分区间，然后再线段树上判断左右子节点。时间复杂度为(O(nlogn))
方法一：
#include <iostream>
#define lch 2*k
#define rch 2*k+1
#define mid (l+r)/2
using namespace std;
const int N=2e5+7;
int t,a[N],tree[4*N][3];
int n;
void init(int k,int l,int r){
if(l>=r){
tree[k][1]=a[l];
tree[k][2]=a[l];
return;
}
init(lch,l,mid);
init(rch,mid+1,r);
tree[k][1]=max(tree[lch][1],tree[rch][1]);
tree[k][2]=min(tree[lch][2],tree[rch][2]);
}
int qryMax(int k,int l,int r,int ql,int qr){
if(ql>qr){
return 1e9+7;
}
if(ql<=l&&r<=qr){
return tree[k][1];
}
int Max1=0,Max2=0;
if(ql<=mid) Max1=qryMax(lch,l,mid,ql,qr);
if(mid+1<=qr) Max2=qryMax(rch,mid+1,r,ql,qr);
return max(Max1,Max2);
}
int qryMin(int k,int l,int r,int ql,int qr){
if(ql>qr){
return 1e9+7;
}
if(ql<=l&&r<=qr){
return tree[k][2];
}
int Min1=1e9+7,Min2=1e9+7;
if(ql<=mid) Min1=qryMin(lch,l,mid,ql,qr);
if(mid+1<=qr) Min2=qryMin(rch,mid+1,r,ql,qr);
return min(Min1,Min2);
}
bool judgeL(int ql,int qr,int key){
int cnt=qryMin(1,1,n,ql,qr);
if(cnt<=key){
return true;
}else{
return false;
}
}
bool judgeR(int ql,int qr,int key){
int cnt=qryMin(1,1,n,ql,qr);
if(cnt>=key){
return true;
}else{
return false;
}
}
int searchL(int ll,int rr,int key){
int ql=ll,qr=rr;
while(ql<=qr){
int md=(ql+qr)/2;
if(judgeL(ll,md,key)){
qr=md-1;
}else{
ql=md+1;
}
}
return ql;
}
int searchR(int ll,int rr,int key){
int ql=ll,qr=rr;
while(ql<=qr){
int md=(ql+qr)/2;
if(judgeR(ll,md,key)){
ql=md+1;
}else{
qr=md-1;
}
}
return qr;
}
bool judge(int ql,int qr,int key){
int cnt=qryMax(1,1,n,ql,qr);
if(cnt<=key){
return true;
}else{
return false;
}
}
int search(int ll,int rr,int key){
int ql=ll,qr=rr;
while(ql<=qr){
int md=(ql+qr)/2;
if(judge(md,n,key)){
qr=md-1;
}else{
ql=md+1;
}
}
return ql;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int ok=0;
init(1,1,n);
for(int i=1;i<=n-2;i++){
int key=qryMax(1,1,n,1,i);
int sl=searchL(i+1,n,key);
int sr=searchR(i+1,n,key);
if(((sl<i+1||sl>n)||(sr<i+1||sr>n))&&qryMin(1,1,n,i+1,sl)!=key){
continue;
}else{
if(sl+1>n) continue;
int z=search(sl+1,min(sr+1,n),key);
if((z>=sl+1&&z<=min(sr+1,n))&&qryMax(1,1,n,z,n)==key){
ok=1;
printf("YES
");
printf("%d %d %d
",i,z-i-1,n-z+1);
break;
}else{
continue;
}
}
}
if(ok==0){
printf("NO
");
}
}
}
方法二：
#include <iostream>
#define lch 2*k
#define rch 2*k+1
#define mid (l+r)/2
using namespace std;
const int N=2e5+7;
int t,n,a[N],tree[4*N][3];
void init(int k,int l,int r){
if(l>=r){
tree[k][1]=a[l];
tree[k][2]=a[l];
return;
}
init(lch,l,mid);
init(rch,mid+1,r);
tree[k][1]=max(tree[lch][1],tree[rch][1]);
tree[k][2]=min(tree[lch][2],tree[rch][2]);
}
int qryMax(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tree[k][1];
}
int Max1=0,Max2=0;
if(ql<=mid) Max1=qryMax(lch,l,mid,ql,qr);
if(mid+1<=qr) Max2=qryMax(rch,mid+1,r,ql,qr);
return max(Max1,Max2);
}
int qryMin(int k,int l,int r,int ql,int qr){
//cout<<" "<<l<<" "<<r<<" "<<tree[k][2]<<endl;
if(ql<=l&&r<=qr){
return tree[k][2];
}
int Min1=1e9+7,Min2=1e9+7;
if(ql<=mid) Min1=qryMin(lch,l,mid,ql,qr);
if(mid+1<=qr) Min2=qryMin(rch,mid+1,r,ql,qr);
return min(Min1,Min2);
}
int searchR(int k,int l,int r,int key){
if(l>=r){
return r;
}
int tem=tree[rch][1];
int inx=-1;
if(tem>=key){
inx=searchR(rch,mid+1,r,key);
}else{
inx=searchR(lch,l,mid,key);
}
return inx;
}
int searchL(int k,int l,int r,int key){
if(l>=r){
return r;
}
int tem=tree[rch][1];
int inx=-1;
if(tem>key){
inx=searchL(rch,mid+1,r,key);
}else{
inx=searchL(lch,l,mid,key);
}
return inx;
}
int search(int k,int l,int r,int key){
if(l>=r){
return r;
}
int tem=tree[rch][2];
int inx=-1;
if(tem<=key){
inx=search(lch,l,mid,key);
}else{
inx=search(rch,mid+1,r,key);
}
return inx;
}
int ikuzo(int k,int l,int r,int ql,int qr,int key){
if(ql>qr){
return 1e9+7;
}
if(ql<=l&&r<=qr){
//cout<<"tree="<<tree[k][2]<<endl;
if(tree[k][2]<=key)
return search(k,l,r,key);
else
return 1e9+7;
}
int inx=1e9+7;
if(ql<=mid) inx=min(inx,ikuzo(lch,l,mid,ql,qr,key));
if(mid+1<=qr) inx=min(inx,ikuzo(rch,mid+1,r,ql,qr,key));
return inx;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
init(1,1,n);
int ok=1;
for(int i=1;i<=n-2;i++){
int key=qryMax(1,1,n,1,i);
int jl=searchL(1,1,n,key);
int jr=searchR(1,1,n,key);
int ql=max(i+1,jl),qr=jr-1;
if(ql>qr) continue;
int inx;
if(qryMin(1,1,n,i+1,ql)<=key){
inx=ql;
}else{
inx=ikuzo(1,1,n,ql+1,qr,key);
}
if(inx!=1e9+7&&qryMin(1,1,n,i+1,inx)==key){
printf("YES
");
printf("%d %d %d
",i,inx-i,n-inx);
ok=0;
break;
}
}
if(ok==1){
printf("NO
");
}
}
}