[CEOI2008] Dominance-题解

· · 题解

摘抄自我的博客

曼哈顿距离转换成切比雪夫距离，那么辐射范围变成了一个矩形，我们可以轻易地用 O(n^2) 的扫描线进行解答。但是因为这道题坐标是整点，而转换会出现小数，我们考虑如何避免小数。

对于转换后的的点 (x,y)，它在转换前是 (\frac{x+y}{2},\frac{x-y}{2})，我们们发现有些点虽然可能在转换后是整点，但转换前不是，只有转换后奇偶性相同的点转换前才是整点。

所以我们要单独维护转换后 x,y 同为奇数或同为偶数的点的数量。

#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;
}