自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:50:00，当前版本为作者最后更新于2023-09-10 18:54:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P9600 [IOI2023] 封锁时刻

设 $dx_i$ 表示 $X$ 到 $i$ 的距离，$dy_i$ 表示 $Y$ 到 $i$ 的距离。

一个原始的想法：显然地，$c_i$ 只会取到 $dx_i$ 或 $dy_i$。如果 $c_i = \min(dx_i, dy_i)$，那么它对答案贡献 $1$；如果 $c_i = \max(dx_i, dy_i)$，那么它对答案贡献 $2$。这样问题转化为了非常经典的 Cardboard Box：枚举被取到的最大的 $b_i$，那么所有 $b_k < b_i$ 的 $k$ 至少取也会取 $a_i$。将 $b$ 从小到大排序，枚举 $i$，设 $S$ 为 $1\leq k\leq i$ 的 $b_k - a_k$ 和 $i < k \leq n$ 的 $a_k$ 构成的可重集，求出最大的 $j$ 使得 $S$ 的前 $j$ 小的元素之和加上 $\sum_{k = 1} ^ i a_k$ 不超过 $K$。将所有 $a_i$ 和 $b_i - a_i$ 离散化后 BIT 上二分即可。

然而直接这样做是有问题的：城市 $i$ 由 $X$ 可达的前提条件是 $X$ 到 $i$ 所有城市均可达，也就是 $i$ 在 $X$ 方向上的后继 $s(i, X)$ 可达。我们求出的方案不一定能满足限制。来看看什么样的贡献是不符合限制的吧：

• 先把后继不存在的情况考虑掉：不妨设 $i = X$。设 $j = s(i, Y)$。如果 $c_i = 0$，那么它产生的 $1$ 的贡献显然合法。如果 $c_i = dy_i$，则要求 $c_j \geq dy_j$。因为 $dy_i > dy_j$，所以如果 $c_j < dy_j$，那么令 $c_j$ 变成 $dy_j$（增加至少 $1$ 贡献，增加至多 $dy_j$ 代价），$c_i$ 变成 $0$（减少 $1$ 贡献，减少 $dy_i$ 代价）可得更优的方案。

• $c_i$ 等于 $\min(dx_i, dy_i)$ 且不等于 $\max(dx_i, dy_i)$。不妨设 $dx_i < dy_i$。设 $j = s(i, X)$，则要求 $c_j\geq dx_j$。首先，因为 $dx_j = dx_i - w(i, j)$ 且 $dy_j \geq dy_i - w(i, j)$，所以 $dx_j \leq dy_j$。这说明只要 $c_j$ 不为 $0$ 就行。而 $c_j$ 显然不会为 $0$，否则令 $c_j$ 变成 $dx_j$（增加 $1$ 贡献，增加 $dx_j$ 代价），$c_i$ 变成 $0$（减少 $1$ 贡献，减少 $dx_i$ 代价）可得更优的方案。这说明在不考虑限制时用 Cardboard Box 的做法求出的解在该情况下的贡献是符合限制的。

• $c_i$ 等于 $\max(dx_i, dy_i)$。不妨设 $dx_i \leq dy_i$。设 $j_x = s(i, X)$，$j_y = s(i, Y)$。这里又有两种情况：

  • $j_x = j_y$，设为 $j$，则 $dx_j = dx_i - w(i, j)$，$dy_j = dy_i - w(i, j)$，且要求 $c_j = dy_j$。此时 $i$ 恰好不在 $X, Y$ 的简单路径上。

    • 如果 $c_j = 0$，那么令 $c_j$ 变成 $dy_j$（增加 $2$ 贡献，增加 $dy_j$ 代价），$c_i$ 变成 $0$（减少 $2$ 贡献，减少 $dy_i$ 代价）可得更优的方案。

    • 如果 $c_j = dx_j$，那么令 $c_j$ 变成 $dy_j$（增加 $1$ 贡献，增加 $dy_j - dx_j$ 代价），$c_i$ 变成 $dx_i$（减少 $1$ 贡献，减少 $dy_i - dx_i$ 代价）得到代价相等的方案。

    这说明在不考虑限制时用 Cardboard Box 的做法求出的解在该情况下的贡献要么符合限制，要么可以通过调整得到符合限制且代价不劣的方案。

  • 唯一的问题发生在 $j_x\neq j_y$，即 $i$ 落在 $X, Y$ 简单路径上且不等于 $X, Y$ 的时候。而且我们很容易举出一个这种情况下的反例：由 $(1, 2, 2), (2, 3, 1), (3, 4, 1), (4, 5, 2)$ 组成的五元链，且 $K = 3$。答案显然为 $3$，但我们会求出 $c_3 = 3$ 使得总贡献为 $4$。

但是，如果至少一个点贡献了 $2$，那么 $X$ 和 $Y$ 之间所有点都要至少贡献 $1$。从这一点出发，考虑钦定 $X$ 和 $Y$ 之间所有点至少贡献 $1$。在此基础上做 Cardboard Box（这是容易的）是否就符合限制了呢？

我们来具体分析一下：要求 $c_{j_x} \geq dx_{j_x}$ 且 $c_{j_y}\geq dy_{j_y}$。

• 对于 $c_{j_x}\geq dx_{j_x}$：因为 $dx_i \leq dy_i$，所以 $dx_{j_x} < dy_{j_x}$。若 $c_{j_x} > 0$，这个条件就一定满足。
• 对于 $c_{j_y}\geq dy_{j_y}$：
  • 如果 $dy_{j_y}\leq dx_{j_y}$，那么若 $c_{j_y} > 0$，这个条件就一定满足。
  • 如果 $dy_{j_y} > dx_{j_y}$，那么若 $c_{j_y} = dx_{j_y}$，可以令 $c_i$ 变成 $dx_i$，$c_{j_y}$ 变成 $dy_{j_y}$，贡献不变，但注意到 $i$ 和 $j_y$ 在链上都是向 $X$ 偏的，所以代价会减少 $2w(i, j_y)$（把式子写出来可得同样的结果）。因此，若 $c_{j_y} > 0$，这个条件就一定满足。

也就是说，只要 $c_{j_x} > 0$ 且 $c_{j_y} > 0$，方案就一定合法。而这个先决条件恰好被 “钦定 $X$ 和 $Y$ 之间所有点至少贡献 $1$" 这一步操作满足了（特别地，对于 $j_x = X$ 或 $j_y = Y$ 的情况，因为此时 $dx_{j_x} = 0$ 或 $dy_{j_y} = 0$，所以合法），而该操作是必要条件，即所有合法方案都必须满足的条件，所以该操作不会丢掉合法方案。

别忘了还有不存在一个城市从 $X, Y$ 均可达的情况，此时答案为最大的 $k$ 使得 $\{dx_i\} \cup \{dy_i\}$ 前 $k$ 小的元素之和不大于 $K$。合法性已经证明过了，且如果方案有城市从 $X, Y$ 均可达，因为只会将代价算大，所以不影响答案的合法性。

时间复杂度 $\mathcal{O}(N\log N)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int N = 4e5 + 5;

ll z[N];
struct level {
  ll a, b;
  bool operator < (const level &z) const {
    return b < z.b;
  }
} c[N];

namespace Cardboard_Box {
  int cnt, p[N], q[N];
  ll d[N], nu[N], su[N];
  void add(int x, int v1, ll v2) {
    while(x <= cnt) {
      nu[x] += v1, su[x] += v2;
      x += x & -x;
    }
  }

  int solve(int n, ll K, level *c, int m, ll *z) {
    cnt = 0;
    for(int i = 1; i <= m; i++) d[++cnt] = z[i];
    for(int i = 1; i <= n; i++) {
      d[++cnt] = c[i].a;
      d[++cnt] = c[i].b - c[i].a;
    }
    sort(c + 1, c + n + 1);
    sort(d + 1, d + cnt + 1);
    cnt = unique(d + 1, d + cnt + 1) - d - 1;
    
    ll sum = 0;
    memset(nu, 0, cnt + 2 << 3);
    memset(su, 0, cnt + 2 << 3);
    for(int i = 1; i <= m; i++) {
      int pos = lower_bound(d + 1, d + cnt + 1, z[i]) - d;
      add(pos, 1, z[i]);
    }
    for(int i = 1; i <= n; i++) {
      p[i] = lower_bound(d + 1, d + cnt + 1, c[i].a) - d;
      q[i] = lower_bound(d + 1, d + cnt + 1, c[i].b - c[i].a) - d;
      add(p[i], 1, c[i].a);
    }

    ll ans = 0;
    for(int i = 0; i <= n; i++) {
      if(i) {
        add(p[i], -1, -c[i].a);
        add(q[i], 1, c[i].b - c[i].a);
        K -= c[i].a;
      }
      if(K < 0) break;
      ll p = 0, num = 0, sum = 0;
      for(int j = __lg(cnt); ~j; j--) {
        int np = p + (1 << j);
        if(np > cnt || sum + su[np] > K) continue;
        p = np, num += nu[p], sum += su[p];
      }
      if(p < cnt) num += (K - sum) / d[p + 1];
      ans = max(ans, num + i);
    }
    return ans;
  }
}

ll dx[N], dy[N];
vector<pii> e[N];
void dfs(int id, int ff, ll *d) {
  if(ff == -1) d[id] = 0;
  for(pii _ : e[id]) {
    int it = _.first;
    if(it == ff) continue;
    d[it] = d[id] + _.second;
    dfs(it, id, d);
  }
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
  for(int i = 0; i < N; i++) e[i].clear();
  for(int i = 0; i + 1 < N; i++) {
    e[U[i]].push_back({V[i], W[i]});
    e[V[i]].push_back({U[i], W[i]});
  }
  dfs(X, -1, dx), dfs(Y, -1, dy);

  vector<ll> arr;
  for(int i = 0; i < N; i++) {
    arr.push_back(dx[i]);
    arr.push_back(dy[i]);
  }
  sort(arr.begin(), arr.end());

  int ans = 0;
  ll sum = 0;
  for(int i = 0; i < arr.size(); i++) {
    if((sum += arr[i]) > K) break;
    ans++;
  }

  int n = 0, m = 0, cnt = 0;
  for(int i = 0; i < N; i++) {
    ll mn = min(dx[i], dy[i]);
    ll mx = max(dx[i], dy[i]);
    if(dx[i] + dy[i] == dx[Y]) {
      cnt++, K -= mn;
      z[++m] = mx - mn;
    }
    else c[++n] = {mn, mx};
  }

  if(K >= 0) ans = max(ans, cnt + Cardboard_Box::solve(n, K, c, m, z));
  return ans;
}