自动搬运

查看原文

来自洛谷，原作者为

	BreakPlus empty should not be filled

搬运于2025-08-24 22:30:19，当前版本为作者最后更新于2024-06-20 22:20:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个好写 $\mathcal{O}(n)$ 的做法。好像题解区都是分治？

考虑对于每个右端点计算答案。

众所周知，最大独立集问题是可以 DP 的。具体地，维护两个 DP 值 $f,g$，其中 $f$ 表示最后一个数任意的最大独立集的值，$g$ 表示最后一个数必须不选的最大独立集的值。

若在末尾加入一个值为 $a_i$ 的数，则转移如下：

这类问题有一个经典转化（类似 PKUSC2024 D1T3）。把转移式子写成以下形式：

发现每次新加入一个数， $f$ 的变化量与新的 $f'-g'$ 均为 $\max(0, a_i-(f-g))$。这个值只和 $f-g$ 有关。

也就是说，我们将答案进行拆贡献，每加入一个数，答案就增加 $\max(0, a_i-(f-g))$。这样，我们只需要时刻维护 $f-g$ 的值，每次转移就 $f'-g'=\max(0, a_i-(f-g))$。于是可以完成对答案的计算。

我们从左往右扫，假设扫到 $x$，对每个 $i$ 维护以 $i$ 为左端点，$x$ 为右端点的区间的 $f-g$ 的值。维护一个多重集 $S$，囊括所有的 $f-g$。

记录 $r_x$ 表示所有右端点为 $x$ 的区间的最大独立集之和。每次移动 $x$，都相当于对 $i \in [1,x-1]$ 的 $d_i$ 做了一次转移（右边新加一个 $a_x$）。

实时维护 $r_x$ 的变化量，即 $r_x - r_{x-1}$，记作 $\Delta_x$。其实这个值也就等于 $\sum \max(0, a_x - (f-g)) = \sum (f'-g')$。

如果不考虑要与 $0$ 取 $\max$，不难得到 $\Delta_x=-\Delta_{x-1}+xa_x$，也就是每一个 $(f-g)$ 都变成 $a_x-(f-g)$。

发现会有一些 $a_x - (f-g)$ 小于 $0$。我们直接从 $S$ 的最大值开始判断，暴力将所有这样的 $f-g$ 全部手动改成 $0$。而其它的 $f-g$ 在全局打 tag 完成修改（这个地方略有一点细节）。

手动改成 $0$ 是否复杂度寄了？发现 $f-g$ 值相同的可以捆绑在一起维护，所有手动修改的 $f-g$ 都变成了 $0$。

于是我们可以在 $S$ 中维护二元组，记录 $f-g$ 的值和这种值出现的次数。通过势能分析，我们只会往 $S$ 里加入 $n$ 个数，每次手动修改都会使 $|S|$ 减小 $1$。

具体实现的时候发现 $S$ 时刻保持着有序，只会在头尾修改，拿个 deque 搞一下就是 $\mathcal{O}(n)$ 的了。

ll n,a[100005],tx=1,ty=0,sum=0,ans=0,Ans=0;
deque<P>S;
// tx, ty 是全局 tag，S 中的一个数 x 其实已经变成了 tx * x + ty
// tx 为 1 或 -1，所以序列有时候升序有时候降序，但时刻保持有序

ll decode(ll x){ return tx * x + ty; } // 还原真正的 x
ll encode(ll x){ return (x - ty) / tx; } // 加入的时候需要进行逆操作 
void solve(){
    n=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    for(ll i=1;i<=n;i++){
        if(S.empty() || encode(0) <= S.front().fi) S.push_front(mkp(encode(0), 1));
        else S.push_back(mkp(encode(0), 1));
        tx=-tx; sum=mod-sum;
        ty=-ty+a[i]; sum=(sum+a[i]*i)%mod; // 全局修改

        ll cnt = 0;
        while(!S.empty() && decode(S.front().fi) < 0){
            sum=(sum+(-decode(S.front().fi))*(S.front().se))%mod;
            cnt+=S.front().se; S.pop_front();
        }

        while(S.size() && decode(S.back().fi) < 0){
            sum=(sum+(-decode(S.back().fi))*(S.back().se))%mod;
            cnt+=S.back().se; S.pop_back();
        } // 对首尾的特殊修改
      // sum 是 r[x] 的变化量

        if(S.empty() || encode(0) <= S.front().fi) S.push_front(mkp(encode(0), cnt));
        else S.push_back(mkp(encode(0), cnt));
        _Add(ans, sum); // ans 是 r[x]
        _Add(Ans, ans); // Ans 是总的答案
    }
    printf("%lld\n", Ans);
}