P11119 [ROI 2024 Day 2] 保持连接

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