专栏文章

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

MMeta_Morph
P11119题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1jsrp
此快照首次捕获于
2025/12/02 11:51
3 个月前
此快照最后确认于
2025/12/02 11:51
3 个月前
查看原文

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

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

知识点

DP，前缀和。

分析

设 Li,RiL_i,R_i 表示能够覆盖到点 ii 的区间的左端点最小值、右端点最大值。考虑不带修改的情况。
那么设 gig_i 表示以 ii 作为起点，以 [i,n][i,n] 内端点作为终点的贡献和，那么就有 gi=(n−Ri)+gRi+1g_i = (n-R_i)+g_{R_i+1}。我们统计原答案 sum=∑gisum=\sum g_i。
现在再来考虑 XX 的影响，那么如果 X>aiX>a_i，则有：设 pp 为原本覆盖 i+Xi+X 的线段中左端点最小值减一（如果 i+X>ni+X>n 就设为 nn），如果满足 max⁡(1,i−X)≤p\max(1,i-X)\le p，所有在往后跳的时候经过区间 [max⁡(1,i−X),p][\max(1,i-X),p] 的点就会受到影响，它们会直接跳到 i+X+1i+X+1。
考虑求出经过某个点 ii 的点数 fif_i，转移较为简单：fi=∑Rj+1=ifj+1f_i = \sum_{R_j + 1 = i} f_j + 1。
那么设经过该区间的点数为 cc，原本它们在该区间产生的贡献为 ss，r=min⁡(n,i+X)r=\min(n,i+X)，那么明显答案为 sum−s+c(n−r+gr+1)sum-s+c(n-r+g_{r+1})。
那么考虑如何维护 s,cs,c，由于 i−Xi-X 是递增的，我们直接双指针加入 <i−X<i-X 的部分即可，用树状数组即可 O(nlog⁡2n)O(n\log_2{n}) 解决。
考虑优化，发现树状数组修改的点也是递增的，那么我们先对于修改和未修改都求出贡献前缀和数组，然后在加入 XX 的时候借助 LL 求一下修改的边界 qq，分别把两部分放到答案里即可，复杂度 O(n)O(n)。

代码

CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...