题解：P14681 [ICPC 2025 Yokohama R] Minimizing Wildlife Damage

· · 题解

题意：

给你 N(\leq 2\times 10^5) 和一个自然数数列 A(A_i\leq 10^{12})，Q(\leq 2\times 10^5) 次询问对于如下策略和给定的执行策略 k(\leq 10^{17}) 能达到的最大值是多少。

Part1

首先理解清题意，为什么删去一些数可以让答案变大。

这是因为将一个数变为 0 就是等价与提前切断一个子段，这样一次删除的数就少了。

Part2

考虑怎么删除才是最优秀的。稍微推导可以发现，除了一开始序列中的 0，一定不会有超过三个连续的零，否则可以保留中间一个。并且不会有连续两个正数，否则可以把其中一个较小的改了一定等价。

所以对于每个前缀，都可以求出保留一些不相邻的 A_i 的最大和让其为最大答案，即最大带权独立集。

Part3

注意到操作完之后，我们的序列一定会分成三段，第一段全都被减成 0，第二段是最后的连续一段被减小的部分，第三段没有被修改过。

显然第一段是 \text{Part2} 已然解决的问题，接下来考虑第二第三段。

首先如果第三段没有被修改，那么它一定被一个 0 所分割。

对于第二段，假设有连续很长一段大于 0，你需要找到中间一个位置把它改成 0。那么后面的部分不会变，前面的部分会减去剩余的 k 乘上长度（如果减到 0 以下，那么这么算也不会变差）。

并且对于每个 k，你会让第一段尽量长，也就是剩余的 k 一定小于第二段的开头，否则把这个数会加入的一段。那么这样的第二段的开头就会很少。

所以从后往前，对于每个可行的第二段的开头，查询即可。然后将把这个位置改成 0 的选项（是一个一次函数），用李超树维护即可。

思路来自 jiangly

code:

struct Line{
    __int128 k,b;
    Line():k(0),b(0){}
    Line(int _k,int _b):k(_k),b(_b){}
    __int128 operator()(int x){
        return k*x+b;
    }
};
struct Node{
    int ls,rs;
    Line v;
}t[N];
int tot,root;
inline void insert(int &p,Line v,int L,int R){
    if(!p)p=++tot;
    int mid=(L+R)>>1;
    if(t[p].v(mid)<v(mid)||!t[p].v.k)swap(t[p].v,v);
    if(L==R||!v.k)return;
    if(t[p].v(L)<v(L))insert(t[p].ls,v,L,mid);
    if(t[p].v(R)<v(R))insert(t[p].rs,v,mid+1,R);
}

inline __int128 query(int p,int x,int L,int R){
    if(!p)return -inf;
    int mid=(L+R)>>1;
    if(x<=mid)return max(t[p].v(x),query(t[p].ls,x,L,mid));
    else return max(t[p].v(x),query(t[p].rs,x,mid+1,R));
}

int n,q;
int a[N],f[N];
int sum[N],ans[N],k[N];
pair<int,int>kval[N],val[N],fval[N];
vector<pair<int,int>>qry[N];
solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=q;i++){
        cin>>k[i];
        kval[i]=make_pair(k[i],i);
    }
    f[1]=a[1];
    f[2]=a[2];
    f[3]=a[1]+a[3];
    for(int i=4;i<=n;i++)f[i]=max(f[i-2],f[i-3])+a[i];
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
        f[i]-=a[i];
    }
    for(int i=1;i<=n;i++){
        val[i]={f[i]+a[i],i};
        fval[i]={f[i],i};
    }
    sort(kval+1,kval+q+1,greater<>());
    sort(val+1,val+n+1,greater<>());
    sort(fval+1,fval+n+1,greater<>());
    set<int>S;
    for(int i=1,j=0,t_=0;i<=q;i++){
        if(kval[i].first==kval[i-1].first){
            for(int x:S)qry[x].emplace_back(kval[i].first,kval[i].second);
            continue;
        }
        while(j+1<=n&&val[j+1].first>kval[i].first)S.emplace(val[++j].second);
        while(t_+1<=n&&fval[t_+1].first>kval[i].first)S.erase(fval[++t_].second);
        for(int x:S)qry[x].emplace_back(kval[i].first,kval[i].second);
    }
    for(int i=n+1;i>=1;i--){
        if(i<=n){
            for(auto asd:qry[i]){
                int k_=asd.first,id=asd.second;
                __int128 res=query(root,f[i]-k_,-1e18,1e18);
                res+=sum[n]-sum[i-1];
                res+=__int128(k_)*i-__int128(f[i])*i;
                ans[id]=max(ans[id],(int)res);
            }
        }
        insert(root,Line(i,-a[i]),-1e18,1e18);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
    return 0;
}