Codeforces Round #686 (Div. 3) F. Array Partition
程序员文章站
2022-03-28 16:27:19
题意:找到三个正整数x、y、z满足下面两个条件思路:首先我们很容易处理得到前后缀的最大值。前缀最大值直接遍历过去就好,后缀最大值开个数组suf维护后缀最大值即可。对于中间那部分,因为不存在修改操作,是个静态的区间问题,预处理打个st表即可。然后我们难点在于如何找到x+y的位置,满足等式首先,我们要知道这么两个常识。区间最小值会随着区间长度增大而保持不变或者减小区间最大值会随着区间长度增大而保持不变或者增大那么这里就有了单调性。所以我们枚举每个位置作为x,然后通过二分得到x+y的位置。1、如...
题意:找到三个正整数x、y、z
满足下面两个条件
思路:首先我们很容易处理得到前后缀的最大值,前缀最大值直接遍历过去就好,后缀最大值开个数组suf维护后缀最大值即可。对于中间那部分,因为不存在修改操作,是个静态的区间问题,预处理打个st表即可。
然后我们难点在于如何找到x+y的位置,满足等式
首先,我们要知道这么两个常识。
区间最小值会随着区间长度增大而保持不变或者减小
区间最大值会随着区间长度增大而保持不变或者增大
那么这里就有了单调性。
所以我们枚举每个位置作为x,然后通过二分得到x+y的位置。
1、如果前缀最大值ma>min(x+1,x+y) 说明区间最小值太小了,要增大他,那么就要让区间长度变小,因为左端点是不变的,所以让r=m,缩小右端点。
2、如果前缀最大值ma<min(x+1,x+y) 说明区间最小值过大,要减少他,那么就要让区间长度增大,左端点不变,所有就让l=m,扩大右端点。
3、如果满足ma=min(x+1,x+y),我们还需要比较ma和后缀最大值,即max(x+y+1,n),如果前缀最大值更大,说明后缀偏小,那么要扩大区间长度,因为右端点n不变,所以要让左端点x+y+1缩小,即让r=m,反之让l=m.
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+50;
int lg[N],st[N][20];
int suf[N],a[N];
int getMin(int l,int r){
int k=lg[r-l+1];
return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
for(int i=2;i<N;i++){
lg[i]=lg[i-1];
if(i%2==0) lg[i]=lg[i/2]+1;
}
int T;cin>>T;
while(T--){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
st[i][0]=a[i];
}
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
suf[n]=a[n];
for(int i=n-1;i;i--) suf[i]=max(suf[i+1],a[i]);
int k=0;
int ma=0;
for(int i=1;i<n;i++){
ma=max(ma,a[i]);
int l=i,r=n;
while(l+1<r){
int m=l+r>>1;
int mi=getMin(i+1,m);
if(ma>mi) r=m;
else if(ma<mi) l=m;
else {
if(ma>suf[m+1]) r=m;
else if(ma<suf[m+1]) l=m;
else {
k=m;
break;
}
}
}
if(k){
cout<<"YES\n";
cout<<i<<" "<<k-i<<" "<<n-k<<endl;
break;
}
}
if(!k) cout<<"NO\n";
}
return 0;
}
本文地址:https://blog.csdn.net/qq_43563669/article/details/110122497
上一篇: ios配置证书报错
推荐阅读
-
Codeforces Round #650 (Div. 3) B. Even Array
-
Codeforces Round #686 (Div. 3) A. Special Permutation
-
Codeforces Round #686 (Div. 3) F. Array Partition
-
Codeforces Round #686 (Div. 3)_A. Special Permutation
-
Codeforces Round #627 (Div. 3) F. Maximum White Subtree(树dp)
-
C.Good Array (思维) Codeforces Round #521 (Div. 3)
-
Codeforces Round #498 (Div. 3)--F. Xor-Paths
-
Codeforces Round #686 (Div. 3) A. Special Permutation
-
Codeforces Round #650 (Div. 3) B. Even Array
-
Codeforces Round #686 (Div. 3) F. Array Partition