自动搬运

查看原文

来自洛谷，原作者为

	Godzilla ?

搬运于2025-08-24 23:04:23，当前版本为作者最后更新于2024-10-03 11:25:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11119 [ROI 2024 Day 2] 保持连接

更好的阅读体验

设 $L_i,R_i$ 分别表示覆盖了 $i$ 的的线段中最靠左的左端点和最靠右的右端点，特殊的，如果没有覆盖，则 $L_i=R_i=i$。显然所有 $R_i$ 就刻画了一种局面。

如果没有 $X$ 的操作，设 $g_i$ 表示从 $i$ 出发到 $[i,n]$ 的重新连接的次数之和，转移为 $g_i=n-R_i+g_{R_i+1}$，那么答案就是 $\sum g_i$。

加上 $X$ 的操作，考虑其对位置 $i$ 的影响，设 $p$ 为覆盖了 $\min(n,i+X)$ 的线段的最靠左的左端点，那么有影响的是跳到过 $[\max(1,i-X),p-1]$ 的区间的点，它们的 $R$ 会改变为 $\min(n,i+X)$，接下来要求出经过此区间的点的个数，减去他们接下来原本的贡献，加上新的贡献。

设 $f_i$ 表示以 $[1,i]$ 为起点，经过 $i$ 的起点个数，转移为 $f_i=1+\sum\limits_{R_j+1=i}f_j$。设经过该区间的点数为 $c$，他们接下来原本的贡献之和为 $s$，原本不操作 $X$ 的答案为 $S$，那么位置 $i$ 的答案为 $S-s+c(n-r+g_{r+1})$。考虑 $i$ 从小到大枚举，设 $l=\max(1,i-X)$，当 $l>1$ 时，在树状树组的位置 $R_{l-1}+1$ 处加入贡献，这样可以保证加入 $x$ 是第一次跳到区间中的，特殊的，以 $i$ 为起点的贡献可以在扫描之前加入。

实现时可以开两棵树状树组维护个数和贡献，代码非常精简。

#include <bits/stdc++.h>
#define int long long
#define lb(x) (x & (-x))

using namespace std;

bool START;

const int N = 1e6 + 5;

int n, X, a[N], L[N], R[N];
int f[N], g[N], S, ans;

struct bit {
  int c[N];
  void add(int x, int k) {for (; x <= n; x += lb(x)) c[x] += k;}
  int ask(int x) {int s = 0; for (; x; x -= lb(x)) s += c[x]; return s;}
} t1, t2;

bool END;

signed main() {
  cin >> n >> X; for (int i = 1; i <= n; ++i) L[i] = i, R[i] = i;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i]; int r = min(n, i + a[i]), l = max(1ll, i - a[i]);
    L[r] = min(L[r], l), R[l] = max(R[l], r);
  }
  for (int i = n - 1; i; --i) L[i] = min(L[i], L[i + 1]);
  for (int i = 2; i <= n; ++i) R[i] = max(R[i], R[i - 1]);
  for (int i = n - 1; i; --i) g[i] = n - R[i] + g[R[i] + 1];
  for (int i = 1; i <= n; ++i) f[i]++, f[R[i] + 1] += f[i];
  for (int i = 1; i <= n; ++i) S += g[i];
  ans = S;

  for (int i = 1; i <= n; ++i) t1.add(i, g[i]), t2.add(i, 1);
  for (int i = 1; i <= n; ++i) {
    int p = (i + X <= n ? L[i + X] : n + 1);
    int l = max(1ll, i - X), r = min(n, i + X);
    if (l > 1) {
      int t = l - 1;
      if (R[t] + 1 <= n) t1.add(R[t] + 1, f[t] * g[R[t] + 1]), t2.add(R[t] + 1, f[t]);
    }
    if (X <= a[i]) continue;
    if (p <= l) continue;
    int s = S - (t1.ask(p - 1) - t1.ask(l - 1)) + (t2.ask(p - 1) - t2.ask(l - 1)) * (n - r + g[r + 1]);
    ans = min(ans, s);
  }
  cout << ans << endl;
  return 0;
}