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

zrl123456 · 2025-12-11 20:49:49 · 题解

:::::info[题目基本信息] 考察：图论，动态规划 DP，双指针（省选/NOI-）。
题目简介：
给定 \{a_n\}，你初始时有一个数，第 i 个数代表你位于 [\max(1,i-a_i),\min(n,i+a_i)] 内时你可以选择 i 作为你手中的数。
假设现在你需要从 l 走到 r，初始时你可以在 l 处选择一个数，然后你不断走向下一个位置（设你现在从 x 走到 x+1，手上的数是 p）：

• 若在 x+1 上可以选择 p，那么直接走过去。
• 否则，在 x+1 处重新选择一个数，然后再走过去。

设 f(l,r) 为从 l 走到 r 时重新选择一个数的次数的最小值，那么 \{a_n\} 所带来的贡献为：

特别地，你现在还有一个数 x，你可以将一个 a_i 更换为 x（可以不更换），问上式的最小值是多少。
数据范围：

• 1\le n\le 10^6
• 0\le x\le n
• \forall i\in[1,n],0\le a_i\le n

  ::::: 先考虑没有这个 x 我们要怎么做。
  令 l_i=\max(1,i-a_i),r_i=\min(n,i+a_i)，那么当我们位于 pos 时，我们肯定会选择 r_i 尽可能大的 i 作为手中的数字。这时我们可以连一条 pos\rightarrow r_i+1 的边，这样就变成了一个以 n+1 为根的内向树，下文中我们称 r_i+1 为 pos 的父亲（ft_{pos}=r_i+1）。
  自然而然地想要设 DP 状态，设 f_i 表示在 i 到 n+1 的贡献，那么容易得到 DP 转移：

  f_i=f_{ft_i}+n-ft_i+1

  其中最初时 f_{n+1}=0。
  那么在 x=0 时答案就是 \displaystyle\sum_{i=1}^nf_i。

现在 x\ne 0 了考虑怎么做。
观察一下通过把 a_i 换成 x 会发生什么变化，那么满足 pos\in[\max(1,i-x),\min(n,i+x)]\land ft_{pos}\le\min(n,i+x) 条件的 pos 的父亲全部会改为 \min(n,i+x)+1，考虑详细刻画这个东西。
随便写一下点 i 的贡献是 (f_{r+1}+n-r-f_i)siz_i 的，但是这样区间内的点加起来就算重了，考虑怎么修改。
注意到若存在边 i\rightarrow j，那么在 i 的时候就不需要再算一遍 j 的贡献了，那么在算 i 的时候就可以把 j 的贡献减去（至于为什么不只算 i 不算 j 是因为这样算 i 时就需要处理 j 的所有儿子，同时儿子不被算后还需要再 i 中加回贡献，这样很麻烦而且时间复杂度实现不好会爆）。
这样我们就基本做完了这道题。最开始使用 multiset 寻找所有 pos 的父亲，最后统计答案的时候双指针拆成 f_{r+1}+n-r 和 f_i 两项后使用 BIT 维护即可 \Theta(n\log n) 的时间复杂度，不过这是 DS 学傻了的后果。

• 寻找 pos 的父亲：
  注意到 pos 的父亲下界也是 pos+1，也就是说 r_i<pos 的 i 可以不删去，反正也统计不到答案里，这样只需要维护前缀最大值就可以消掉 \log。
• 统计答案：
  你都双指针了你干嘛还要上 BIT，你直接开桶维护每个位置的权值然后动态维护上述两项的值就可以消掉 \log。

时空复杂度均为 \Theta(n)。

code