Solution P9051 | F**king Convexity

· · 题解

拿到这个题，哇，时限 6 秒，先二分答案肯定不劣。就算多个 log 应该也能冲过去。

二分答案，要求最大子段和 \le M，然后设计一个 dp。由于 V 很大，我们争取让 dp 的维度都是 \mathcal{O}(n) 级别。

考虑从左往右确定 i 选择 a_i 还是 b_i，同时为了维护最大子段和，我们应该记录最大后缀和，要求最大后缀和保持 \le M。

那么 f_{i,j} 表示前 i 个数中选 j 个 a_i（剩下的选 b_i）的最大后缀和的最小值，不难写出转移：

f_{i,j} = \max(0, \min(f_{i-1,j} + b_i, f_{i-1,j-1} + a_i))

特别地，当 f_{i,j} > M，将其赋值为 +\infty。

注意到 f_i 具有凸性，考虑用一个堆去维护差分数组，每次会插入一个 a_i - b_i。

需要进行的操作：

什么，你想让我讲讲怎么处理细节？还是自己吃一下这坨吧。

这里给一个技巧：令 x = \sum [a_i \le b_i]，若 k \le x，那么 k 越大，答案越小，维护的凸包就是单调递减的，不用维护后面上升的部分，大大方便了实现。

那么当 k > x 的时候，交换序列 a 和 b 并令 k' = n - k 即可。

然后讲讲输出方案，其实就是找到最后堆中较小的 k 个数值的对应位置（a_i - b_i 对应的 i），所以用 set<pair<ll,ll>> 维护堆，顺便记录编号。

但是有一个问题，堆中的数值会被修改，有些会被修改成 0，而有些 0 不能计入方案，就是那些一开始 b_i < a_i 的 i。由于之前保证了 k \le x，把这个编号 i 标记作不能用即可，后面不会出现不够用的情况（因为选 i 只会让答案更劣）。

以下是完整的 checker 部分代码，供参考。

bool flg; // 表示一开始是否有交换 a,b
namespace Check{ 
    set<pair<ll,ll>>Q; // 记录差分数值及其对应位置
    ll ht=0, sum=0;
    vector<ll>zero_edge; // 末尾有一车 0，记录其对应位置
    vector<ll>ans; // 开头有一些因为 >mid 被删除的元素，记录其对应位置
    bool check(ll mid){
        Q.clear(), zero_edge.clear(), ans.clear();
        ht = sum = 0; // ht 是 dp 值的首项，sum 是差分数组的总和
        for(ll i=1;i<=n;i++){
            ht += b[i];
            if(a[i]-b[i] <= 0){
                Q.emplace(a[i]-b[i], i), sum+=a[i]-b[i];
            }else{
                Q.emplace(0, n+1);
            } // n+1 表示不能计入最终方案
            // erase <0
            while(ht+sum<0){
                if(!Q.size()) {
                    ht = 0;
                    break;
                }
                auto p = *(--Q.end()); auto [x,y] = p;

                if(ht+sum-x<=0){
                    sum -= x; zero_edge.pb(y);
                    Q.erase(p);
                }else{
                    // make ht+sum=0
                    ll fw = ht+sum;
                    x -= fw, sum -= fw;
                    Q.erase(p); Q.emplace(x,y);
                    break;
                }
            }

            // erase >mid
            while(ht > mid){
                if(!Q.size()) return 0;
                auto p = *Q.begin(); auto [x,y] = p;

                ht += x, sum -= x, ans.pb(y);
                Q.erase(p);
            }
        }

        // output
        ll K = k;
        if(ans.size() <= K && K <= ans.size() + Q.size() + zero_edge.size()){
            for(int i=1; i<=n; i++) str[i] = 'B'-flg;
            for(auto x: ans){
                if(x != n+1){
                    str[x] = 'A'+flg;
                    K--;
                }
            }
            while(K && Q.size()){
                auto [x,y] = *Q.begin();
                Q.erase({x,y});
                if(y != n+1){
                    str[y] = 'A'+flg;
                    K--;
                }
            }
            reverse(zero_edge.begin(), zero_edge.end());
            while(K && zero_edge.size()){
                if(zero_edge.back() != n+1){
                    str[zero_edge.back()] = 'A'+flg;
                    K--;
                }
                zero_edge.pop_back();
            }

            return 1;
        }
        return 0;
    }
}