题解：P11119 [ROI 2024] 保持连接 (Day 2)

· · 题解

提供一个 O(n\log n) 的做法。

显然我们先计算一下每个点下一次跳动的位置，第 i 个点的结果记为 nxt_i。nxt 显然是有单调性的。

我们得到 f(s,t)=f(nxt_s,t)+1\ \ (nxt_s\le t)。

那么记录 g_i 表示所以以 i 为左端点的答案，就有 g_i=g_{nxt_i}+n-nxt_i+1。

于是不带修改的答案就 O(n) 解决了。

接下来考虑修改操作，模拟一下发现会对一段连续的区间的 nxt 值取 max。由于单调性，所以实际修改的也时一段连续的区间，且左端点相同。

设覆盖区间 [st,ed]，实际修改区间是 [st,r]， 其中 st=max(1,i-a_i),ed=min(n,i+a_i)，那么修改后的每个点的 g_i 的值都是 g_{ed+1}+n-ed，记为 x。

其实还需要考虑连带的影响，也就是满足 nxt_j=i 的所有j 的 g 值的变化，以及连带的连带的影响。

那么从 i 连一条边向 nxt_i，形成一棵树，连带的范围就是对应子树。为了不重复计算，我们只连满足 i<st 的边 (i,nxt_i)统计子树大小。可以证明是不重不漏的。

把第 i 个子树的大小记为 size_i，那么答案的改变值就是 \sum_{i=st}^r\ (x-f_i)\times size_i。

展开显然树状数组单点修改区间查询分别维护 size_i 和 f_i\times size_i 即可。

代码十分简单。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) ((x)&(-(x)))
ll n,a[1000005],k,v,ans,res,st,ed,lst;
ll sz[1000005],f[1000005],nxt[1000005];
ll fs[1000005];
void mg(ll x,ll k)
{
    for(int i=x;i<=n;i+=lowbit(i)) sz[i]+=k,fs[i]+=f[x]*k;
}
ll qu(ll x)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) res+=sz[i];
    return res;
}
ll qfs(ll x)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) res+=fs[i];
    return res;
}
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        nxt[max(1ll,i-a[i])]=max(nxt[max(1ll,i-a[i])],min(n,i+a[i])+1);
    }
    for(int i=1;i<=n;i++) nxt[i]=max(nxt[i],nxt[i-1]);
    for(int i=n;i>=1;i--) f[i]=f[nxt[i]]+(n-nxt[i]+1);
    for(int i=1;i<=n;i++) res+=f[i];
    for(int i=1;i<=n;i++) mg(i,1);
    ans=res,lst=1;
    for(int i=1;i<=n;i++)
    {
        while(v<n&&nxt[v+1]<=min(n,i+k)) v++;
        st=max(1ll,i-k),ed=min(n,i+k)+1;
        if(v<st) continue;
        while(lst<st) mg(nxt[lst],qu(lst)-qu(lst-1)),lst++; 
        ll tt=f[ed]+(n-ed+1);
        ans=min(ans,res+tt*(qu(v)-qu(st-1))-(qfs(v)-qfs(st-1)));
    }
    printf("%lld\n",ans);
    return 0;
}