P9895 [ICPC2018 Qingdao R] Airdrop
Alex_Wei
·
·
题解
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_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)$。
```cpp
#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
*/
```