自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:52:47，当前版本为作者最后更新于2024-01-20 15:19:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

K. P9895 [ICPC2018 Qingdao R] Airdrop

先考虑 $(x_0, y_0)$ 确定时怎么计算答案。

因为所有人都是优先沿 $y$ 轴移动，不走到 $y = y_0$ 不横向移动，所以相撞只会发生在 $y = y_0$ 这条水平线上。

将点根据 $x_i$ 和 $x_0$ 的大小关系分成三类：

• 若 $x_i = x_0$，那么他不会和任何人撞到，因为他一走到 $y = y_0$ 就安全了。
• 若 $x_i < x_0$，那么他只有可能和 $x_j < x_0$ 且与 $(x_0, y_0)$ 曼哈顿距离相同的 $(x_j, y_j)$ 撞起来。
• 若 $x_i > x_0$，同理。

现在固定曼哈顿距离相同且 $x_i < x_0$，由于这些人最终都要走到 $(x_0 - 1, y_0)$，所以最多只有一个人活下来。如果一定只是两个人相撞，则答案就是人数的奇偶性。但有可能出现三个人相撞在 $(x' < x_0, y_0)$，三个人分别从该点的上下两侧和左侧走进来的情况。按 $x$ 从小到大的顺序扫描，维护标记表示是否有人从左边走过来。

• 如果当前 $x$ 没有人，则标记不变。
• 如果当前 $x$ 有一个人，则标记改变。
• 如果当前 $x$ 有两个人，则标记清空。

扫描到 $x_0$ 时如果标记为 $1$ 则产生贡献，否则产生贡献。

现在会算 $(x_0, y_0)$ 的答案，考虑对所有 $x_0$ 求答案。

$x_0$ 从小往大扫，算 $x_i < x_0$ 的贡献。然后 $x_0$ 从大往小扫，算 $x_i > x_0$ 的贡献。两种情况对称，只研究第一种情况。

$x_0$ 从小扫到大的过程中，发现 $x_0$ 的方向和固定某个曼哈顿距离时 $x$ 扫动的方向是一致的。也就是说，$x_0$ 向右移动 $1$，只需考虑所有 $x_i = x_0$ 的点对标记的影响，而不需要重新计算答案。

还有一个问题，就是本题多测，不能对每组数据都从 $0$ 扫到 $10 ^ 5$。只有 $x_i$ 和 $x_i\pm 1$ 作为 $x_0$ 是重要的，其它 $x_0$ 都可以向左或向右移动直到它们等于 $x_i\pm 1$，而不改变答案。

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

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;
using LL = __int128_t;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {
  x += y, x >= mod && (x -= mod);
}
int add(int x, int y) {
  return x += y, x >= mod && (x -= mod), x;
}

struct FastMod {
  ull b, m;
  FastMod(ull b = 1) : b(b), m(ull((LL(1) << 64) / b)) {}
  ull reduce(ull a) {
    ull q = ull((LL(m) * a) >> 64);
    ull r = a - q * b; // can be proven that 0 <= r < 2 * b
    return r >= b ? r - b : r;
  }
} R;

// ---------- templates above ----------

constexpr int N = 3e5 + 5;
constexpr int V = 1e5 + 1;

int n, y;
int cnt, d[N], res[N];
struct point {
  int x, y;
  bool operator < (const point &z) const {
    return x != z.x ? x < z.x : abs(y - ::y) < abs(z.y - ::y);
  }
} c[N];

int cur, pt, buc[N], tp[N], vis[N], num, ap[N];
void init() {
  for(int i = 1; i <= num; i++) {
    buc[ap[i]] = vis[ap[i]] = tp[ap[i]] = 0;
  }
  cur = pt = num = 0;
}
int calc(int x) {
  while(pt < n && c[pt + 1].x < x) {
    int pos = V;
    if(c[++pt].y >= y) pos += c[pt].x - (c[pt].y - y);
    else pos += c[pt].x + (c[pt].y - y);
    if(!vis[pos]) ap[++num] = pos, vis[pos] = 1;
    if(pt < n && c[pt].x == c[pt + 1].x && c[pt].y + c[pt + 1].y == 2 * y) {
      if(tp[pos]) {
        buc[pos] ? cur-- : cur++;
        buc[pos] ^= 1;
      }
      tp[pos] = 1;
    }
    else tp[pos] ^= 1;
    buc[pos] ? cur-- : cur++;
    buc[pos] ^= 1;
  }
  return cur;
}

void solve() {
  cin >> n >> y, cnt = 0;
  map<int, int> mp;
  for(int i = 1; i <= n; i++) {
    cin >> c[i].x >> c[i].y;
    mp[c[i].x]++;
    d[++cnt] = c[i].x - 1;
    d[++cnt] = c[i].x;
    d[++cnt] = c[i].x + 1;
  }
  sort(d + 1, d + cnt + 1);
  cnt = unique(d + 1, d + cnt + 1) - d - 1;
  sort(c + 1, c + n + 1);
  init();
  for(int i = 1; i <= cnt; i++) {
    auto it = mp.find(d[i]);
    if(it != mp.end()) res[i] = it->second;
    else res[i] = 0;
    res[i] += calc(d[i]);
  }
  init();
  for(int i = 1; i <= n; i++) c[i].x = V - c[i].x;
  for(int i = 1; i <= cnt; i++) d[i] = V - d[i];
  reverse(c + 1, c + n + 1);
  reverse(d + 1, d + cnt + 1);
  reverse(res + 1, res + cnt + 1);
  init();
  for(int i = 1; i <= cnt; i++) res[i] += calc(d[i]);
  int mn = n, mx = 0;
  for(int i = 1; i <= cnt; i++) {
    mn = min(mn, res[i]);
    mx = max(mx, res[i]);
  }
  cout << mn << " " << mx << "\n";
}

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  cin >> T;
  while(T--) solve();
  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/