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