题解：P12074 [OOI 2025] The arithmetic exercise

· · 题解

比较神秘的题目。

考虑既然 x_i 之间是独立的，且若从前往后考虑的话，每次都要乘上一个 -1，不妨将其翻转，倒着考虑，这样子第一次贡献一定是正，第二次一定为负，...，这样就方便储存信息。

设 f_{i,j} 表示考虑了搞了前 i 个，目前 j 个若得到贡献会为负数（即 j 个接受了奇数次贡献）的最大值。

则 f_{0,0}=0，且 f_{i,j}=\max(f_{i-1,j-1}+x_i,f_{i-1,j+1}-x_i)。

那么一个加，一个减，不好看，变化为：f_{i,j}=\max(f_{i-1,j-1}+2x_i,f_{i-1,j+1})-x_i，那么最后减去 \sum x_i，式子变为：f_{i,j}=\max(f_{i-1,j-1}+2x_i,f_{i-1,j+1})。

那么发现一个非常有趣的性质，由于 j-1,j+1 的奇偶性相同，根据我们的初始状态，那么当 i,j 奇偶性相同的时候，f_{i,j} 才有实际意义。

那么不妨把 2j,2j+1(j\ge 0) 视作一个东东，那么有：

一眼丁真，鉴定为 slope trick。

凸性如何证明，设 \Delta_{i,j}=f_{i,j}-f_{i,j-1}，实际上我们可以证明其是单调递减的，即是一个上凸包。

  1. 若 i 为偶数，那么 f_{i,j}=f_{i-1,j-1}+\max(\Delta_{i-1,j},2x_i)。

    那么前面一段会选择 \Delta，后面一段会选择 2x_i。

    考虑取到 \Delta 的那一段，有：\Delta_{i,j}=f_{i,j}-f_{i,j-1}=(f_{i-1,j-1}+\Delta_{i-1,j})-(f_{i-1,j-2}+\Delta_{i-1,j-1})=\Delta_{i-1,j}

    对于取到 2x_i 那一段，更简单，\Delta_{i,j}=\Delta_{i-1,j-1}。

    对于分界点，\Delta_{i,k}=(f_{i-1,k-1}+2x_i)-(f_{i-1,k-2}+\Delta_{i-1,k-1})=2x_i

    由于有 2x_i\ge \Delta_{i-1,k}=\Delta_{i,k+1}，那么显然 \Delta 继续单调递增。

  2. 若 i 为奇数，那么 f_{i,j}=f_{i-1,j}+\max(2x_i,\Delta_{i-1,j+1})。

    那么前面一段会选择 \Delta，后面一段会选择 2x_i。

    考虑取到 \Delta 的那一段，有：\Delta_{i,j}=f_{i,j}-f_{i,j-1}=(f_{i-1,j}+\Delta_{i-1,j+1})-(f_{i-1,j-1}+\Delta_{i-1,j})=\Delta_{i-1,j+1}

    对于取到 2x_i 那一段，更简单，\Delta_{i,j}=\Delta_{i-1,j}。

    对于分界点，\Delta_{i,j}=(f_{i-1,j}+2x_i)-(f_{i-1,j-1}+\Delta_{i-1,j})=2x_i

那么直接用 multiset 维护这个 \Delta 即可。

细节：

#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
const int N=3e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m,a[N],ans,val;
multiset<int,greater<int> > s;
void solve(){
    n=rd();m=rd();for(int i=1;i<=m;i++)a[i]=rd(),val-=a[i];
    reverse(a+1,a+1+m);
    for(int i=1;i<=m;i++){
        s.insert((a[i]<<1ll));
        if(i&1) val+=(*s.begin()),s.erase(s.begin());
        int lim=(n+2-(i&1))>>1;
        while(s.size()>=lim) s.erase(prev(s.end()));
    }
    ans=val;
    for(auto u : s) val+=u,ans=max(ans,val);
    printf("%lld\n",ans);
}
void clean(){
    ans=val=0;
    s.clear();
}
signed main(){
    int T=rd();while(T--)solve(),clean();
    return 0;
}