[UOI2025] Convex Array 题解

· · 题解

参考了 未来姚班 zyl 的题解，在此表示对作者的感谢。

先分析一些简单的性质。题目描述中的“下凸序列”是单谷的，构造这个序列的过程相当于维护一个双端队列，先将最小的元素放进去，接下来从小到大加入每个元素（要么加入队头，要么加入队尾）。假设目前要尝试在队尾加入 a_i，最靠近队尾的两个元素为 a_j,a_k（a_j 更靠近队尾），那么能加入当且仅当 a_i-a_j\ge a_j-a_k；队头同理。

尝试进行可行性 DP，将 a 从小到大排序，观察到只需要记录最靠近队头的两个数和最靠近队尾的两个数的下标，即可在转移时获取所有必要的信息。设 f_{i,j,k,l} 表示最靠近队头的两个元素为 a_i,a_j（a_i 更靠近，即 a_i\ge a_j），最靠近队尾的两个元素为 a_k,a_l（a_k 更靠近，即 a_k\ge a_l）是否可行。转移是 O(1) 的（枚举放队头 / 队尾）。时间复杂度 O(n^4)，期望得分 31。

假设当前考虑 f_{i,j,k,l}，发现 j/k 中必然有一个是 i-1，于是记一维 0/1 表示 j=i-1 还是 k=i-1（即 a_{i-1} 和 a_i 是否在队列的同一端）——设 f'_{0/1,i,j,k} 表示当前加入的最后一个元素为 a_i，0/1 表示 a_{i-1} 是否和 a_i 在队列同一端，与 a_i 不同端的两个下标中较小的那个为 k（即 a_k< 与它同一端的另一个数），a_j 是除了上面三个数以外剩下的那个数。时间复杂度变为 O(n^3)，期望得分 41。

观察到答案只可能为 0/1，所以尝试“换维”技巧，把其中一维的下标换到答案上：设 f''_{0/1,i,j} 表示上面定义的 f' 数组中，满足 f'_{0/1,i,j,k}=\mathrm{true} 的最大 k（因为 k 越大，后面的条件就越松，更容易达到）。时间、空间复杂度均为 O(n^2)，期望得分 54；注意到有些测试点 MLE 了，于是改为滚动数组，空间复杂度 O(n)，期望得分 63。

想要进一步优化，需要考察上述 DP 的性质。观察到最初的 DP 记录的四个数总体上可以归类为三大种（不妨认为 a_i 在队头）：

后两种状态的量级运用上面的技巧可以做到 O(n)，只需要对于每个 i 记录最大的 j/l 即可（对应代码中的 f_{0/1}）。第一种情况看起来比较棘手，继续追本溯源，考虑 (i-1,i-2,k,l) 有哪些转移到 (i,?,?,?) 的情况：

时间复杂度 O(n\log n)，可以轻松通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
class tree:map<int,int>{
  public:
    inline void set(int p,int x){
      int w=(*this)[p]=max((*this)[p],x);
      auto it=this->lower_bound(p);
      if(it!=this->begin()&&prev(it)->second>w){
        this->erase(p); return;
      }
      it=this->upper_bound(p);
      while(it!=this->end()&&it->second<=w)it=this->erase(it);
    } // 单点插入，删无用后继
    inline int pre_max(int p){
      auto it=this->upper_bound(p);
      return it==this->begin()?-1:prev(it)->second;
    } // 前缀最大值查询
    inline void clear(){map<int,int>().swap(*this);}
    inline bool any(){return !(this->empty());}
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a(n);
    for(auto &i:a)cin>>i;
    sort(a.begin(),a.end());
    vector<int> f(2,-1);
    tree t; t.set(a[0],0);
    auto add=[&](int x,int y){t.set((a[x]<<1)-a[y],x);};
    for(int i=2;i<n;i++){
      vector<int> g(2,-1);
      g[1]=t.pre_max(a[i]);
      if(a[i]-a[i-1]<a[i-1]-a[i-2])t.clear();
      if(~f[0]){
        if(a[i]-a[i-1]>=a[i-1]-a[i-3])add(i-2,f[0]);
        if(a[i]-a[i-2]>=a[i-2]-a[f[0]])g[0]=max(g[0],i-3);
      }
      if(~f[1]){
        if(a[i]-a[i-1]>=a[i-1]-a[f[1]])add(i-2,i-3);
        if(a[i]-a[i-2]>=a[i-2]-a[i-3])g[0]=max(g[0],f[1]);
      } // 分类讨论各种转移
      f=g;
    }
    cout<<(~f[0]||~f[1]||t.any()?"YES\n":"NO\n");
    // 只要三种状态中有一种存在答案即为 YES
  }
  return 0;
}