自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 23:16:23，当前版本为作者最后更新于2025-05-20 07:45:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

那么合法的重排一定形如 $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)$。

#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;
}