题解 P7503 「HMOI R1」文化课

Miko35 · 2021-04-08 09:31:29 · 题解

upd：改正了一处笔误（将 l 打成了 1）

验题人又来水题解了。

for(rgi i=1;i<=n;++i){
    for(rgi j=1;j<=i;++j)dp[i]=max(dp[i],dp[j-1]+sum(j,i,ma[j][i]));
}

考虑这个 n^2 的 dp，其中 dp_i 表示前 i 个数的答案，\textrm{sum}(l,r,x) 表示“将 [l,r] 都改为 x 取得的收益”，ma_{l,r} 表示 [l,r] 的 range_max。

看似不大能优化，其实是可以的。记 s_{l,r}=\textrm{sum}(l,r,ma_{l,r})，也就是“在 [l,r] 举行一场作弊的收益”。令 t 时刻的 S_i 表示 s_{i,t}，只要我们在 dp 的过程中能随着时间有效维护 S 数组，就可以使用线段树优化这个 dp 解决问题。

考虑分开计算每个人的贡献。对于一个人 (a_x,l_x,r_x)，它对一个区间 [L,R] 产生贡献当且仅当 ma_{L,R}\in [l_x,r_x],x\in [L,R]。

把它写成 \max(ma_{L,x},ma_{x,R})\in [l_x,r_x]，换句话说也就是：ma_{L,x},ma_{x,R} 都要 \leq r_x，且其中至少一个 \geq l_x。

我们分别预处理出 ma_{L,x},ma_{x,R}\in [l_x,r_x] 的 L,R 的范围，记为 [Ll_x,Lr_x],[Rl_x,Rr_x]。所以当 i\in[x,Rl_x) 时，L 的范围是 [Ll_x,Lr_x]；当 i\in[Rl_x,Rr_x] 时，L 的范围是 [Ll_x,x]；当 i>Rr_x 时，没有贡献。

我们在 i 到达几个临界点的时候，通过线段树的区间加操作更新 x 的贡献区间即可。

这样的复杂度是 O(n \log n)，可以通过此题。

核心代码：

for(rgi i=1;i<=n;++i){
    if(a[i][0]>r[i])continue;
    ll[i]=lr[i]=rl[i]=rr[i]=i;
    for(rgi w=LOG;~w;--w){
        chg(rl[i],w,l[i]-1,1),chg(rr[i],w,r[i],1);
        chg(lr[i],w,l[i]-1,-1),chg(ll[i],w,r[i],-1);
    }
    if(a[lr[i]][0]<l[i])--lr[i];
    if(a[rl[i]][0]<l[i])++rl[i];
    v[i].push_back(opt{ll[i],lr[i],1});
    v[rl[i]].push_back(opt{lr[i]+1,i,1});
    v[rr[i]+1].push_back(opt{ll[i],i,-1});
}
for(rgi i=1;i<=n;++i){
    for(opt o:v[i])upd(o);
    upd(opt{i+1,i+1,ans=qry(1,0,n,0,n)});
}