\(b_{i-1}+b_{i+1}\ge b_i\) 等价 \(b_{i+1}-b_i\ge b_i-b_{i-1}\) 即 \(b\) 数组差分数组单调不降。
若出现次数为 2，则必定是最小值在排列中左右各有 1 个。（不能相同元素放一起否则差分为 0）。
若存在元素出现次数大于 2 且不为最小值，则必定无解（多余的元素无论放在哪必定会破坏差分数组的单调）。
所以假设排列中最小值为 \(M\)，则排列 \(b\) 必定形如 \(B_1,B_2,B_3,\cdots,M,\cdots,C_1,C_2,C_3,\cdots\)。
\(M\) 全部在中间，而 \(B,C\) 分别是差分数组单调不增与单调不降的序列。
将 \(B\) 反转，转化成将 \(a\) 划分为两个序列，均满足差分数组单调不降。
于是与 \(a\) 中元素顺序无关，要差分单调不降，则将 \(a\) 升序排序，从小到大插入。
可行性 dp，暴力状态 \(f_{bx,by,cx,cy}\) 分别表示 \(B,C\) 中的最大、次大值这样是 \(O(n^4)\)。
首先插入到 \(i\) 时，\(bx,by,cx,cy\) 中必定包含 \(i\)，将状态改为 \(f_{i,y,X,Y}\) 表示 \(a_i\) 所在的序列次大值为 \(a_y\)，另一序列最大、次大值为 \(a_X,a_Y\)。
接下来一步感觉很不自然，不知道怎么想的。
对 \(f_{i,y,X}\) 的状态分类。
- \(f_{i,i-1,X,Y}\)
- \(f_{i,X,i-1,i-2}\)
- \(f_{i,i-2,i-1,Y}\)
当前 dp 值只有 0/1 表示可行性，很浪费。考虑用 dp 值来存储一维信息。假设另一序列 \(a_X\) 固定，则 \(a_Y\) 越大对插入到末尾的元素限制就越宽松（插入元素的限制为 \(x\ge 2\cdot a_X-a_Y\)）。
而对于 2，3 情况的状态就只用维护 \(g\) 为 \(f_{i,X,i-1,i-2}\) 最大可能 \(X\)，\(w\) 为 \(f_{i,i-2,i-1,Y}\) 最大可能 \(Y\)。第 1 种情况前两维是固定的，表示为 \(F_{X,Y}\) 即可。
于是状态怎么转移。
::::info[(I). 对于第一种状态]
- \(a_{i+1}\) 插入第一个序列（\(a_{i+1}+a_{i-1}\ge 2\cdot a_i\)）。
则原本的状态 \(f_{i,i-1,X,Y}\to f_{i+1,i,X,Y}\) 还是属于第一类。后两维均没改变，所以 \(F_{X,Y}\) 直接继承即可。
- \(a_{i+1}\) 插入第二个序列（\(a_{i+1}+a_Y\ge 2\cdot a_X\)）。
状态 \(f_{i,i-1,X,Y}\to f_{i,i-1,i+1,X}\)，把 \(i+1\) 看成当前轮即 \(f_{i-1,i-2,i,X}\)（\(f_{i,X,i-1,i-2}\)）属于第 2 种情况，即第 \(i+1\) 轮的 \(g\to \max(g,X)\)。
这样的话复杂度是 \(O(n^2)\)，本质上是找满足 \(a_{i+1}+a_Y\ge 2\cdot a_X\) 可行状态中最大的 \(X\)。
\(a_{i+1}+a_Y\ge 2\cdot a_X\to a_{i+1}\ge 2\cdot a_X-a_Y\)。
\(2\cdot a_X-a_Y\) 只跟状态，所以可以用任意数据结构维护最大的 \(X\)。时间复杂度 \(O(n\log n)\)。
::::
::::info[(II). 对于第二种状态]
- \(a_{i+1}\) 插入第一个序列（\(a_{i+1}+a_X\ge 2\cdot a_i\)）。
状态 \(f_{i,X,i-1,i-2}\to f_{i+1,i,i-1,i-2}\) 把 \(i+1\) 看成当前轮，就是 \(f_{i,i-1,i-2,i-3}\) 看作第一种情况插入数据结构维护即可。
- \(a_{i+1}\) 插入第二个序列（\(a_{i+1}+a_{i-2}\ge 2\cdot a_{i-1}\)）。
状态 \(f_{i,X,i-1,i-2}\to f_{i,X,i+1,i-1}\)，把 \(i+1\) 看成当前轮，就是 \(f_{i-1,X,i,i-2}\) 即 \(f_{i,i-2,i-1,X}\) 更新 \(h\)。
::::
::::info[(III). 对于第三种状态]
- \(a_{i+1}\) 插入第一个序列（\(a_{i+1}+a_{i-2}\ge 2\cdot a_i\)）。
状态 \(f_{i,i-2,i-1,Y}\to f_{i+1,i,i-1,Y}\) 把 \(i+1\) 看成当前轮，就是 \(f_{i,i-1,i-2,Y}\) 看作第一种情况插入数据结构维护即可。
- \(a_{i+1}\) 插入第二个序列（\(a_{i+1}+a_{Y}\ge 2\cdot a_{i-1}\)）。
状态 \(f_{i,i-2,i-1,Y}\to f_{i,i-2,i+1,i-1}\)，把 \(i+1\) 看成当前轮，就是 \(f_{i-1,i-3,i,i-2}\) 即 \(f_{i,i-2,i-1,i-3}\) 更新 \(g\)。
::::
::::info[code]
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define Cinout ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
const int N=3e5+5;
int a[N];set<pii>w;
void add(int x,int y){int id=2*a[x]-a[y];auto it=w.upper_bound(mp(id,1e9));if(it!=w.begin()&&(*--it).second>=x)return;while(w.size()){auto it=w.lower_bound(mp(id,1e9));if(it==w.end()||(*it).second>x)break;w.erase(it);}w.insert(mp(id,x));
}
void solve(){int n;cin>>n;int f=-1,g=-1;//f:(i,x,i-1,i-2),g:(i,i-2,i-1,x)//(i,i-1,i-2,x)(i,i-1,x,y)for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);w.clear(),w.insert(mp(a[1],1));//a2,a1,a1,1for(int i=3;i<=n;i++){int F=-1,G=-1;if(w.size()){auto it=w.upper_bound(mp(a[i],1e9));if(it!=w.begin())F=(*--it).second;//(i,x,i-1,i-2)}if(a[i]-a[i-1]<a[i-1]-a[i-2])w.clear();//ai-ai-1>=ai-1-ai-2if(f!=-1){if(a[i]-a[i-2]>=a[i-2]-a[i-3])G=max(G,f);//(i,i-2,i-1,c)if(a[i]-a[i-1]>=a[i-1]-a[f])add(i-2,i-3);//(i,i-1,i-2,i-3)}if(g!=-1){if(a[i]-a[i-2]>=a[i-2]-a[g])G=max(G,i-3);//(i,i-2,i-1,i-3)if(a[i]-a[i-1]>=a[i-1]-a[i-3])add(i-2,g);//(i,i-1,i-2,x)}f=F,g=G;}cout<<((f!=-1||g!=-1||w.size())?"YES\n":"NO\n");
}
int main(){
// freopen("convex_array.in","r",stdin);
// freopen("convex_array.out","w",stdout);Cinout;int _;for(cin>>_;_;_--)solve();return 0;
}
::::
感觉优化过程的步骤还是值得学习的 /shui，但是这个分类还是感觉很不自然，或许是固定 dp 状态中的较多维度减少状态数（？）。