自动搬运

查看原文

来自洛谷，原作者为

	Miko35 阿玮你又在打电动喔，去看会书好不好

搬运于2025-08-24 22:30:29，当前版本为作者最后更新于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)});
}