Solution P7482 | Best Wishes

BreakPlus · 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);
}