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

· · 题解

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

博客园链接：P11119 [ROI 2024] 保持连接 (Day 2) - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

DP，前缀和。

分析

设 L_i,R_i 表示能够覆盖到点 i 的区间的左端点最小值、右端点最大值。考虑不带修改的情况。

那么设 g_i 表示以 i 作为起点，以 [i,n] 内端点作为终点的贡献和，那么就有 g_i = (n-R_i)+g_{R_i+1}。我们统计原答案 sum=\sum g_i。

现在再来考虑 X 的影响，那么如果 X>a_i，则有：设 p 为原本覆盖 i+X 的线段中左端点最小值减一（如果 i+X>n 就设为 n），如果满足 \max(1,i-X)\le p，所有在往后跳的时候经过区间 [\max(1,i-X),p] 的点就会受到影响，它们会直接跳到 i+X+1。

考虑求出经过某个点 i 的点数 f_i，转移较为简单：f_i = \sum_{R_j + 1 = i} f_j + 1。

那么设经过该区间的点数为 c，原本它们在该区间产生的贡献为 s，r=\min(n,i+X)，那么明显答案为 sum-s+c(n-r+g_{r+1})。

那么考虑如何维护 s,c，由于 i-X 是递增的，我们直接双指针加入 <i-X 的部分即可，用树状数组即可 O(n\log_2{n}) 解决。

考虑优化，发现树状数组修改的点也是递增的，那么我们先对于修改和未修改都求出贡献前缀和数组，然后在加入 X 的时候借助 L 求一下修改的边界 q，分别把两部分放到答案里即可，复杂度 O(n)。

代码

constexpr int N(1e6+10);
int n,X;
int a[N],L[N],R[N];
ll ans(LINF),sum(0);
ll f[N],g[N],h0[N],h1[N];

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    I(n,X);
    FOR(i,1,n)L[i]=R[i]=i;
    FOR(i,1,n) {
        I(a[i]);
        int l(max(1,i-a[i])),r(min(n,i+a[i]));
        tomin(L[r],l),tomax(R[l],r);
    }
    DOR(i,n,2)tomin(L[i-1],L[i]);
    FOR(i,2,n)tomax(R[i],R[i-1]);
    DOR(i,n-1,1)g[i]=(n-R[i])+g[R[i]+1],sum+=g[i];
    ans=sum;
    FOR(i,1,n)f[R[i]+1]+=(++f[i]),h0[i]=h0[i-1]+f[i]*g[i],h1[i]=h1[i-1]+f[i]*(g[i]-g[R[i]+1]),f[i]+=f[i-1];
    FOR(i,1,n)if(X>a[i]) {
        int l(max(1,i-X)),r(min(n,i+X)),p(i+X<=n?L[i+X]-1:n),q(max(l,L[p]));
        if(p<l)continue;
        tomin(ans,sum-(h0[p]-h0[q-1])+(f[p]-f[q-1])*(n-r+g[r+1])-(h1[q-1]-h1[l-1]));
    }
    O(ans,'\n');
    return 0;
}