题解：P10093 [ROIR 2022] 礼物 (Day 2)

Meta_Morph · 2025-11-23 15:03:06 · 题解

[ROIR 2022] 礼物 (Day 2) 题解

博客园哦哦哦：[ROIR 2022] 礼物 (Day 2) 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

链表。

分析

首先看到数据范围 k\le\min(100,n)，说明复杂度与 k 有关，那么我们就可以考虑暴力一点地解决这个问题。

一开始我们可以想到按顺序插入数值，这样会有较好的性质，比如从大到小插入一个 u 时，包含 u 和它之前插入的值作为区间前 k 大的情况其实只有 k 种。

假设 k=2，以 1/0 分别代表插入和没插入的值，\color{red}1 表示我们这次插入的值：

那么其实可以分为两种情况：

1. 包括 {\color{blue}1} 和 {\color{red}1}。
2. 包括 {\color{red}1} 和 {\color{green}1}。

我们可以考虑用求前缀和数组区间 \min,\max 优化，那么一次只要遍历 O(k) 就可以解决。

但是这样实现较为麻烦，插入需要 set<int> 之类的，维护区间 \min,\max 需要 ST 表之类的，我们可以转化问题：把从大到小插入改为从小到大删除。

那么删除只需维护链表，维护区间 \min,\max 也可以直接在链表上一起维护，代码变得非常简洁，复杂度 O(nk)。

最后，注意恶心的 k=0。

代码

constexpr int N(2e5+10);

int n,m;
int a[N],idx[N],pre[N],nxt[N];
ll ans;
ll mn[N],mx[N],sum[N];

signed main() {
    /*DE("Input");*/
    scanf("%d%d",&n,&m);
    FOR(i,1,n)scanf("%d",&a[i]);
    FOR(i,1,n)sum[i]=sum[i-1]+a[i];
    if(!m) {
        ans=-LINF;
        ll mn(0);
        FOR(i,1,n)tomax(ans,sum[i]-mn),tomin(mn,sum[i]);
        printf("%lld\n",ans);
        return 0;
    }
    /*DE("Init");*/
    FOR(i,1,n)idx[i]=i;
    sort(idx+1,idx+n+1,[](int x,int y) { return a[x]<a[y]; });
    pre[0]=0,nxt[0]=1,pre[n+1]=n,nxt[n+1]=0;
    FOR(i,1,n)pre[i]=i-1,nxt[i]=i+1;
    FOR(i,0,n)mn[i]=mx[i]=sum[i];
    /*DE("Solve");*/
    FOR(i,1,n-m+1) {
        const int &u(idx[i]);
        int l(u);
        for(int j(m); l&&j>0; l=pre[l],--j);
        int r(l);
        ll cnt(0);
        for(int j(m); j>0; cnt+=a[r=nxt[r]],--j);
        for(; l<=u&&r<=n; cnt-=a[l=nxt[l]],cnt+=a[r=nxt[r]])tomax(ans,mx[r]-mn[l]-cnt);
        tomin(mn[pre[u]],mn[u]),tomax(mx[pre[u]],mx[u]);
        pre[nxt[u]]=pre[u],nxt[pre[u]]=nxt[u];
    }
    /*DE("Output");*/
    printf("%lld\n",ans);
    return 0;
}