题解：P12546 [UOI 2025] Convex Array

目前暂无修正。

% 你赛出了这题，赛后补题参照FFTotoro的题解详细化了一下具体转移过程及思路，在此感谢原作者（怎么套娃了）。

不难得出题意等价于找出两个不同的序列使得相邻两数差单调不降，两个序列的并集为原序列集合（可重集），两个序列的交集为升序排序后的 \(\{a_1\}\)。类似一个下凸包的形式，其中最低点就是 \(a_1\)。

考虑怎么找到这个可行解，进行可行性 DP，发现我们要记录四个下标，分别是两端选择的元素（最大值）及其最上面相邻两数差（或者记录次大值）。这是繁杂的，考虑到我们必然包含 \(i\) 且可行性 DP 可以把信息放在 DP 值上（只针对某些有最有决策的 DP），我们可以稍微优化。

具体来说，我们归纳出 \(3\) 种本质不同的状态（两序列本质相同）：

1. \(\{(i,i-1),(b,c)\}\)

2. \(\{(i,i-2),(i-1,c)\}\)

3. \(\{(i,c),(i-1,i-2)\}\)

分类依据是 \(i-1\) 是否为 \(i\) 所在序列次大值，然后用已知量尝试填满其中一个序列，这样如果还有其他已知量可能会加在这个序列后面，然后就是已知量 \(i-2\) 分配到哪边的问题。

然后我们考虑转移，具体地，从 \(i\to i+1\)，不妨令 \(i'=i+1\)，分别用 \(i+1\) 塞进任意状态的任意新序列中得到：

对于状态 \([1]\)：

\[\begin{aligned} \{(i,i-1),(b,c)\}&\to\{(i+1,i),(b,c)\}&=&\{(i',i'-1),(b,c)\} & [1]\\ &(a_{i+1}-a_i\geq a_i -a_{i-1})\\ \{(i,i-1),(b,c)\}&\to\{(i,i-1),(i+1,b)\}&=&\{(i'-1,i'-2),(i',b)\} & [3]\\ &(a_{i+1}-a_b\geq a_b -a_c) \end{aligned} \]

对于状态 \([2]\)：

\[\begin{aligned} \{(i,i-2),(i-1,c)\}&\to\{(i+1,i),(i-1,c)\}&=&\{(i',i'-1),(i'-2,c)\} & [1]\\ &(a_{i+1}-a_i\geq a_i -a_{i-2})\\ \{(i,i-2),(i-1,c)\}&\to\{(i,i-2),(i+1,i-1)\}&=&\{(i'-1,i'-3),(i',i'-2)\} & [2]\\ &(a_{i+1}-a_{i-1}\geq a_{i-1} -a_c)\\ \end{aligned} \]

对于状态 \([3]\)：

\[\begin{aligned} \{(i,c),(i-1,i-2)\}&\to\{(i+1,i),(i-1,i-2)\}&=&\{(i',i'-1),(i'-2,i'-3)\} & [1]\\ &(a_{i+1}-a_i\geq a_i -a_c)\\ \{(i,c),(i-1,i-2)\}&\to\{(i,c),(i+1,i-1)\}&=&\{(i'-1,c),(i',i'-2)\} & [2]\\ &(a_{i+1}-a_{i-1}\geq a_{i-1} -a_{i-2})\\ \end{aligned} \]

不难发现，对于 \([2][3]\) 两个序列的最大值都是固定的，那么只需要让次大值 \(c\) 尽可能大，就能使其中一个序列的 \(\Delta=\text{序列最上方两个数之差}\) 最小化，也最有可能让转移合法化。所以对于 \([2][3]\) 我们只需要记最大 \(c\)，如果不合法就记 \(-1\) 即可。

然后描述 \([1]\)。对于 \([1]\to[1]\) 的转移，发现转移条件与 \(b,c\) 无关，即如果符合条件保留上一次的所有状态即可。对于 \([1]\to [3]\) 的转移，发现把未知量移到一边就是 \(a_{i+1}\geq 2a_b -a_c\)，然后转移给 \([3]\) 就是要求 \(b\) 最大化（因为 \([1]\) 的 \(b\) 对于 \([3]\) 来说是次大值），那么我们不妨用一个 STL map<int,int> 来存储下标 \(2a_b -a_c\) 的 \(b\) 的最大值，然后需要做到前缀查。类似单调栈的思想，我们保证随着限制的松弛，\(b\) 也相应地单调不减，这样每次查到最后一个 \(\le 2a_b -a_c\) 的位置就是最大 \(b\) 的位置。只需要插入的时候找到后面的下标然后如果 \(b\) 比插入的 \(b\) 还小就删除这个信息就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e5+5;
int n,a[N];
map<int,int>f1,g1;
int main(){//freopen("seq.in","r",stdin);//freopen("seq.out","w",stdout);int Tn;scanf("%d",&Tn);while(Tn--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);f1.clear();if(a[3]-a[2]>=a[2]-a[1])f1[a[1]]=1;int f2=-1,f3=-1;f2=f3=1;for(int i=3;i<n;i++){int g2=-1,g3=-1;g1.clear();int ip=i+1;//f1 to g1if(a[i+1]-a[i]>=a[i]-a[i-1])g1=f1;//f1 to g3if(!f1.empty()){auto it=f1.upper_bound(a[i+1]);if(it!=f1.begin()){it=prev(it);g3=max(g3,it->second);}}if(f2!=-1&&a[i+1]-a[i]>=a[i]-a[i-2]){//f2 to g1auto it=g1.upper_bound(2*a[ip-2]-a[f2]);while(it!=g1.end()){if(it->second<=ip-2){auto dt=next(it);g1.erase(it);it=dt;}else break;}g1[2*a[ip-2]-a[f2]]=max(ip-2,g1[2*a[ip-2]-a[f2]]);}if(f2!=-1&&a[i+1]-a[i-1]>=a[i-1]-a[f2]){//f2 to g2g2=max(g2,ip-3);}if(f3!=-1&&a[i+1]-a[i]>=a[i]-a[f3]){//f3 to g1auto it=g1.upper_bound(2*a[ip-2]-a[ip-3]);while(it!=g1.end()){if(it->second<=ip-2){auto dt=next(it);g1.erase(it);it=dt;}else break;}g1[2*a[ip-2]-a[ip-3]]=max(ip-2,g1[2*a[ip-2]-a[ip-3]]);}if(f3!=-1&&a[i+1]-a[i-1]>=a[i-1]-a[i-2]){//f3 to g2g2=max(g2,f3);}f1=g1;f2=g2,f3=g3;}printf((f2!=-1||f3!=-1||!f1.empty())?"YES\n":"NO\n");}return 0;
}