题解：P12546 [UOI 2025] Convex Array

首先将数组按从小到大的顺序排序。

那么合法的重排一定形如

a_1

在中间，然后左边和右边分成两个独立的部分，每个部分都可以视为一个单调不降的序列，且差分数组单调不降。

这样我们可以从小到大加入

a_i

，维护两个序列的最大值和次大值，尝试

dp

。

设

dp_{i,a,b,c}

表示处理完前

i

个数，是否能做到第一个序列的最大值和次大值的下标分别为

i,a

，第二个序列的最大值和次大值的下标分别为

b,c

。转移是

O(1)

的，复杂度

O(n^4)

。如果参赛者这部分没想清楚，导致退化到

O(n^5)

或者

O(n^6)

，应该也可以得到这部分的分数。

做一个简单的观察：

i-1

一定也在状态当中，复杂度就可以降为

O(n^3)

。

做一个简单的优化：我们没必要记录

01

状态，而是记录次大值的最大值，因为我们总是希望次大值能够更大，这样差值更小，限制也就更松，这样复杂度可以降为

O(n^2)

。

考虑最大值与次大值（的下标）构成的形式，分讨

i-2

的分布：

$(i,i-1,b,c)$
$(i,i-2,i-1,c)$
$(i,c,i-1,i-2)$

容易发现只有这三种形式，对于当前的

i

，后两种形式的状态是

O(1)

的，可以直接暴力转移，考虑第一种形式的状态如何转移。即考虑

a_{i+1}

应该放在哪里。

放在第一个序列

条件为

a_{i+1}+a_{i-1}\ge 2a_i

。转移与

b

和

c

无关。所以只要满足这个条件，那么这些状态就可以保留，否则不行。

放在第二个序列

条件为

a_{i+1}\ge 2a_b-a_c

，转移到

(i,b,i-1,i-2)

。将

2a_b-a_c

做为下标，这相当于一次求前缀的

b

的最大值，可以用各种大家喜欢的数据结构维护。

如果过滤掉没用的状态，则构成形如

2a_b-a_c

递增且

b

递增的序列，使用 set 维护加入和删除，使用 lower_bound 查找前驱即可，

O(n\log n)

。

CPP

#include<bits/stdc++.h>
#define ll long long
#define L x<<1
#define R x<<1|1
#define mid ((l+r)>>1)
#define lc L,l,mid
#define rc R,mid+1,r
#define Root 1,1,n
#define OK Ll<=l&&r<=Rr
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned ll
#define yy return puts("Yes"),void()
#define nn return puts("No"),void()
#define YY puts("Yes"),exit(0)
#define NN puts("No"),exit(0) 
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=5e5+5,M=1e7+5,inf=(1LL<<31)-1,mod=998244353;
const ll llf=1e18;
inline void add(int &a,int b){if(b<0)b+=mod;((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){add(b,mod);return 1LL*a*b%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,ll b){if(!b)return 1;int c=qp(a,b>>1LL);Mul(c,c);if(b&1)Mul(c,a);return c;}
inline int INV(int x){return qp(x,mod-2);}
int n,a[N],F1=-1,F2=-1,G1,G2;
map<int,int>P;
inline int Get(int x){
  if(P.empty())return -1;
  auto it=P.upper_bound(x);
  if(it==P.begin())return -1;
  it--;
  return (*it).second;
}
inline void Insert(int b,int c){
  int W=2*a[b]-a[c],k=Get(W);
  if(k>=b)return;
  while(1){
    if(P.empty())break;
    auto it=P.upper_bound(W);
    if(it==P.end())break;
    int k=(*it).second,id=(*it).first;
    if(k>b)break;
    P.erase(id);
  }
  P[W]=b;
}
inline void Main(){
  n=read(),F1=F2=-1;
  repn(i)a[i]=read();
  sort(a+1,a+n+1),P.clear(),P[a[1]]=1;
  /*
  (i,i-1,b,c) //P
  (i,i-2,i-1,c) //F1
  (i,c,i-1,i-2) //F2 
  */
  rep(i,3,n){
    G1=G2=-1;
    int Mx=-1;
    Mx=Get(a[i]);
    //转移F1
    // (i,i-1,b,c)->(i,b,i-1,i-2)
    G2=Mx;
    if(a[i]+a[i-2]<a[i-1]*2)P.clear();//(i,i-1,b,c)
    if(F1!=-1){
      //(i,i-2,i-1,c)
      if(a[i]-a[i-1]>=a[i-1]-a[i-3])Insert(i-2,F1);//(i,i-1,i-2,c)
      if(a[i]-a[i-2]>=a[i-2]-a[F1])G1=max(G1,i-3);//(i,i-2,i-1,i-3)
    }
    //转移F2 
    if(F2!=-1){
      //(i,c,i-1,i-2)
      if(a[i]-a[i-1]>=a[i-1]-a[F2])Insert(i-2,i-3);//(i,i-1,i-2,i-3)  
      if(a[i]-a[i-2]>=a[i-2]-a[i-3])G1=max(G1,F2);//(i,i-2,i-1,c)
    }
    F1=G1,F2=G2;
  }
  if(F1!=-1||F2!=-1||!P.empty())puts("YES");
  else puts("NO");
}
signed main(){
  int T=read();
  while(T--)Main();
  return 0;
}

题解：P12546 [UOI 2025] Convex Array

文章操作

相关推荐

评论

题解：P12546 [UOI 2025] Convex Array