CF2124G

sunkuangzheng · 2025-07-07 01:47:26 · 题解

感觉这个题 2400 啊，是不是放到 G 把大家骗了。

首先最优解中 a_i 一定是前缀 \min，否则往前移到前缀 \min 上不劣。记 pre_i 表示 \min(a_1,a_2,\ldots,a_i)，特别的，记 pre_0 = 2n。

不难发现改完 a_i 后 pre'_i 只可能在 [a_i+1,pre_{i-1}] 之间，所有前缀 \min 的 i 对应的区间长度和不超过 2n。

于是不妨枚举 pre'_i 的值，贪心地找到最大的 j 满足 a_j + a_i \ge pre'_i 即可。pre_i' 确定后需要重新计算后面的贡献，这也是非常简单的，找到第一个小于 a_i 的位置 j，j 之后的贡献不变；i \sim j 的贡献是一段 pre_i' 和一段定后缀，后缀和一下即可。（不知道单侧递归能不能过但是如果能过那就搞笑了）

精细实现应当可以线性，这里贴一份 \mathcal O(n \log n) 代码，由于是赛时写的可能比较混乱。

#include<bits/stdc++.h>
using ll = long long;
const int N = 1e6+5;
using namespace std;
int T,n,a[N],nxt[N],st[N],tp,pre[N],suf[N];
void los(){
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    st[tp = 0] = n + 1,suf[n+1] = 0;
    for(int i = n;i >= 1;i --){
        while(tp && a[i] <= a[st[tp]]) tp --;
        nxt[i] = st[tp],st[++tp] = i;
    }vector<ll> c(n + 2),as(n + 1),d(n + 2); pre[0] = 2 * n;
    for(int i = 1;i <= n;i ++)
        pre[i] = min(pre[i-1],a[i]),c[i] = pre[i];
    for(int i = n;i >= 1;i --) suf[i] = max(suf[i+1],a[i]);
    for(int i = n - 1;i >= 1;i --) c[i] += c[i + 1];
    auto lb = [&](int x){
        int l = 1,r = n;
        while(l <= r){
            int mid = (l + r) / 2;
            if(suf[mid] >= x) l = mid + 1; else r = mid - 1;
        }return l - 1;
    }; 
    as[n] = c[1]; ll A = as[n]; a[n+1] = -1;
    for(int i = 1;i <= n;i ++) if(a[i] < pre[i-1]){
        int j = nxt[i],k = i+1,cur = pre[i-1],mn = cur; vector<int> pos;
        for(;k <= j;k ++)
            if(a[k] < cur) pos.push_back(k),cur = a[k];
        assert(pos.back() == j);
        for(int k = i + 1;k <= j;k ++) mn = min(mn,a[k]),d[k] = mn;
        d[j] = c[j];
        for(int k = j - 1;k > i;k --) d[k] += d[k+1];
        int m = pos.size(),pt = m - 1; 
        for(int k = a[i] + 1;k <= pre[i-1];k ++){
            int dif = k - a[i],r = lb(dif);
            if(r <= i) break;
            // debug(k,dif,r);
            if(pt > 0 && a[pos[pt - 1]] < k) pt --;
            ll cut = c[r];
            int dis = r - i; r = min(r,j);
            ll nw = 1ll * k * (pos[pt] - i) + d[pos[pt]] - d[r];
            ll od = c[i] - c[r];
            ll del = nw - od - cut;
            as[dis] = max(as[dis],A + del);
            // debug(A+del);
        }  
    }for(int i = n - 1;i >= 0;i --) as[i] = max(as[i],as[i + 1]);
    for(int i = 0;i < n;i ++) cout << as[i] << " \n"[i == n - 1];
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}