P9600 [IOI2023] 封锁时刻

· · 题解

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) 可达。我们求出的方案不一定能满足限制。来看看什么样的贡献是不符合限制的吧：

但是，如果至少一个点贡献了 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} > 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;
}