专栏文章

CF2124G

ssunkuangzheng
CF2124G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioyvo2v
此快照首次捕获于
2025/12/03 03:24
3 个月前
此快照最后确认于
2025/12/03 03:24
3 个月前
查看原文
感觉这个题 2400 啊，是不是放到 G 把大家骗了。
首先最优解中 aia_i 一定是前缀 min⁡\min，否则往前移到前缀 min⁡\min 上不劣。记 preipre_i 表示 min⁡(a1,a2,…,ai)\min(a_1,a_2,\ldots,a_i)，特别的，记 pre0=2npre_0 = 2n。
不难发现改完 aia_i 后 prei′pre'_i 只可能在 [ai+1,prei−1][a_i+1,pre_{i-1}] 之间，所有前缀 min⁡\min 的 ii 对应的区间长度和不超过 2n2n。
于是不妨枚举 prei′pre'_i 的值，贪心地找到最大的 jj 满足 aj+ai≥prei′a_j + a_i \ge pre'_i 即可。prei′pre_i' 确定后需要重新计算后面的贡献，这也是非常简单的，找到第一个小于 aia_i 的位置 jj，jj 之后的贡献不变；i∼ji \sim j 的贡献是一段 prei′pre_i' 和一段定后缀，后缀和一下即可。（不知道单侧递归能不能过但是如果能过那就搞笑了）
精细实现应当可以线性，这里贴一份 O(nlog⁡n)\mathcal O(n \log n) 代码，由于是赛时写的可能比较混乱。
CPP
#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();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...