[CEOI2008] Dominance-题解

摘抄自[我的博客](https://www.luogu.com.cn/article/ur9n70t7) 曼哈顿距离转换成切比雪夫距离，那么辐射范围变成了一个矩形，我们可以轻易地用 $O(n^2)$ 的扫描线进行解答。但是因为这道题坐标是整点，而转换会出现小数，我们考虑如何避免小数。 对于转换后的的点 $(x,y)$，它在转换前是 $(\frac{x+y}{2},\frac{x-y}{2})$，我们们发现有些点虽然可能在转换后是整点，但转换前不是，只有转换后奇偶性相同的点转换前才是整点。 所以我们要单独维护转换后 $x,y$ 同为奇数或同为偶数的点的数量。 ```cpp #include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 3e3; int n, m, p; int cl; struct line { int x, y1, y2, d; } a[MAXN * 2 + 5]; int recnt, re[MAXN * 2 + 5]; struct node { int o, e; }; node get(int l, int r) { return {(r - l + 1) / 2 + (((r - l + 1) & 1) & (r & 1)), (r - l + 1) / 2 + (((r - l + 1) & 1) & !(r & 1))}; } int b[MAXN + 5]; node W, B, answ, ansb; int find(int x) { return lower_bound(re + 1, re + 1 + recnt, x) - re; } signed main() { scanf("%lld%lld%lld", &n, &m, &p); for (int i = 1; i <= p; i ++) { char ch; cin >> ch; int x, y, d; scanf("%lld%lld%lld", &x, &y, &d); x = x + y; y = x - 2 * y; a[++ cl] = {x - d, y - d, y + d + 1, (ch == 'W') ? 1 : -1}; a[++ cl] = {x + d + 1, y - d, y + d + 1, (ch == 'W') ? -1 : 1}; re[++ recnt] = y - d; re[++ recnt] = y + d + 1; } sort(re + 1, re + 1 + recnt); recnt = unique(re + 1, re + 1 + recnt) - re - 1; sort(a + 1, a + 1 + cl, [](line a, line b) {return a.x < b.x; }); for (int i = 1; i <= cl; i ++) { node cur = get(a[i - 1].x, a[i].x - 1); answ.e += cur.e * W.e, answ.o += cur.o * W.o; ansb.e += cur.e * B.e, ansb.o += cur.o * B.o; int Y1 = find(a[i].y1), Y2 = find(a[i].y2); for (int j = Y1; j < Y2; j ++) { cur = get(re[j], re[j + 1] - 1); if (b[j] == 0 && a[i].d == -1) B.e += cur.e, B.o += cur.o; if (b[j] == 0 && a[i].d == 1) W.e += cur.e, W.o += cur.o; if (b[j] == 1 && a[i].d == -1) W.e -= cur.e, W.o -= cur.o; if (b[j] == -1 && a[i].d == 1) B.e -= cur.e, B.o -= cur.o; b[j] += a[i].d; } } printf("%lld %lld", answ.e + answ.o, ansb.e + ansb.o); return 0; } ``` ####