这题网上貌似还没有完整的题解呢，我来口胡一下~

Description

$W \times H$ 的二维坐标系，$W, H \le 10^9$

给 $n (n \le 10^5)$ 个点 $(x, y)$，每个点有个方向，每 $1$ 时刻箭头朝其位置移动一个单位，如果点相遇就会消失。问点经过轨迹的格子并。

Solution

整体框架分析

如果我们能快速确定每个苦无运动的轨迹（最终在何时刻消失），之后的问题是矩形面积并，用扫描线 $O(n \log n)$ 解决。

首先我们可以发现，如果不考虑苦无的消失，两个苦无相撞的充要条件即在一条横线、竖线或斜线（呈 $45°$ 角）上，然后满足一些方向限制，比如，左右相撞的苦无 $i, j$ 要满足在同一条横线 $X_i = Y_i$，然后 $Y_i < Y_j, D_i = 0, D_j = 2$。

令我们比较困扰的事，可能两个苦无满足上述条件，但在此之前其中有苦无已经消失了，所以这次相遇就失败了。

我们可以按照时间顺序处理，每次把冲突时间最短的若干苦无都拿出来然后让他们消失，如果我们遇到的相遇事件中又苦无已经消失了，就跳过。

快速维护 & 算出最短相撞的苦无

由于每个点分别在一条横线、竖线、斜线上，所以我们可以把每条这样的线及方向当成一个集合，每个点至多在四个集合中。

然后我们现在的问题就变成了：一个数轴上，每个位置可能有两种种类的点（$0, 1$），然后要求最近匹配的 $01$ 点对（方向不能反），还要支持删除点。

如果我们考虑每个点匹配的最优点，我们是可以通过 $\text{set}$ 在 $\log$ 时间算出前驱后继，但删除一个点的时候，可能有多个点的最有匹配是他，要修改多个点，这样就挂了。不妨考虑双向匹配，我们维护 $x, y$ 互相都作为对方的最优匹配这样的点对，这样是对的，因为单向匹配总能找到更优的双向匹配。所以在删除的一个点的时候，如果他在双向匹配里，让他的匹配点找新的匹配，即可。

这样时间复杂度就是 $O(n \log n)$

接下来的工作就是把双向匹配放进一个堆里，每次把所有时间最短的点拿出来删除就行。

一些细节

关于横竖直线，距离为奇数点的相撞时间问题。比如相邻的两个 → ←，如果右箭头上方有一个下箭头（如题面右下角的图），那个箭头不会相撞，说明相撞时间 $> 1$，但如果相撞时间又得 $ < 2$，否则会和左箭头相撞，因此这种的相撞时间应该是 $1.5$。我是把时间整体 $\times 2$，这样就可以没有小数。
一定要每次把所有同一时间的点一块删除，不然可能会存在同一时间，但后者认为前者已经消失的恐怖方法。

时间复杂度

$O(n \log n)$

Code

感觉自己确实写的很麻烦，其实独自开个结构体维护那个数轴可能会更简单一点。

#include <iostream>

#include <cstdio>

#include <set>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

typedef long long LL;

const int N = 100005, INF = 2e9;

int W, H, n, X[N], Y[N], D[N], L[N][4], f[N], m, a[N << 1], len, d[4][N], tot[4];

int nxt[4][4], pre[4][4], match[N][4], val[N][4], stk[N], top;

LL ans;

bool st[N], re[N];

struct O {

	int v, x, y;

	bool operator < (const O &b) const { return v > b.v; }

};

struct Node{

	int x, id;

	bool operator < (const Node &b) const { return x < b.x; }

};

typedef set<Node>::iterator SIT;

set<Node> s[4][N][4];

// 第一维：横 / 竖 / 左下 - 右上 / 左上 / 右下; 第二维：离散后线编号; 第三维：存储的方向值

priority_queue<O> q;

int inline get(int x, int o) { return lower_bound(d[o] + 1, d[o] + 1 + tot[o], x) - d[o]; }

void inline find(int c, int i) {

	match[i][c] = 0;

	int x = L[i][c], k = c == 0 ? Y[i] : X[i];

	if (nxt[c][D[i]] != -1) {

		int cq = nxt[c][D[i]];

		SIT it = s[c][x][cq].lower_bound( (Node) { k, 0 } );

		if (it != s[c][x][cq].end()) {

			int j = it -> id, w = (it -> x - k + 1) * 2;

			if (c < 2) w = w / 2 + 1;

			if (!match[j][c] || w < val[j][c]) {

				match[i][c] = j, match[j][c]  = i, val[i][c] = val[j][c] = w;

				q.push((O){ val[i][c], i, j });

			}

		}

	}

	if (pre[c][D[i]] != -1) {

		int cq = pre[c][D[i]];

		SIT it = s[c][x][cq].lower_bound( (Node) { k, 0 } );

		if (it != s[c][x][cq].begin()) {

			--it; int j = it -> id, w = (k - it -> x + 1) * 2;

			if (c < 2) w = w / 2 + 1;

			if (!match[j][c] || w < val[j][c]) {

				match[i][c] = j, match[j][c]  = i, val[i][c] = val[j][c] = w;

				q.push((O){ val[i][c], i, j });

			}

		}

	}

}

void inline insert(int c, int i) {

	int x = L[i][c], k = c == 0 ? Y[i] : X[i];

	s[c][x][D[i]].insert((Node) { k, i } );

	find(c, i);

}

void inline init() {

	memset(nxt, -1, sizeof nxt);

	memset(pre, -1, sizeof pre);

	nxt[0][0] = 2, pre[0][2] = 0, nxt[1][3] = 1, pre[1][1] = 3;

	pre[2][0] = 3, nxt[2][3] = 0, pre[2][1] = 2, nxt[2][2] = 1;

	nxt[3][0] = 1, pre[3][1] = 0, nxt[3][3] = 2, pre[3][2] = 3;

	for (int i = 1; i <= n; i++) {

		d[0][++tot[0]] = X[i], d[1][++tot[1]] = Y[i];

		d[2][++tot[2]] = X[i] + Y[i], d[3][++tot[3]] = X[i] - Y[i];

	}

	for (int i = 0; i < 4; i++) {

		sort(d[i] + 1, d[i] + 1 + tot[i]);

		tot[i] = unique(d[i] + 1, d[i] + 1 + tot[i]) - d[i] - 1;

	}

	for (int i = 1; i <= n; i++) {

		L[i][0] = get(X[i], 0), L[i][1] = get(Y[i], 1);

		L[i][2] = get(X[i] + Y[i], 2), L[i][3] = get(X[i] - Y[i], 3);

		for (int j = 0; j < 4; j++) insert(j, i);

	}

}

void inline del(int i) {

	if (re[i]) return;

	re[i] = true;

	for (int c = 0; c < 4; c++) {

		int x = L[i][c], k = c == 0 ? Y[i] : X[i];

		s[c][x][D[i]].erase((Node) { k, i } );

		if (match[i][c]) find(max(nxt[c][D[i]], pre[c][D[i]]), match[i][c]);

	}

}

void inline clear() { while (!q.empty() && (st[q.top().x] || st[q.top().y])) q.pop(); }

void inline work() {

	while (!q.empty()) {

		clear();

		if (q.empty()) break;

		int v = q.top().v;

		while (1) {

			clear();

			if (q.empty() || q.top().v != v) break;

			O u = q.top();

			f[u.x] = f[u.y] = v >> 1, del(u.x), del(u.y);

			stk[++top] = u.x, stk[++top] = u.y; q.pop();

		}

		while (top) st[stk[top--]] = true;

	}

}

struct E{

	int x, l, r, c;

	bool operator < (const E &b) const { return x < b.x; }

} e[N << 1];

void inline add(int x1, int y1, int x2, int y2) {

	e[++m] = (E) { x1, y1, y2 + 1, 1 };

	e[++m] = (E) { x2 + 1, y1, y2 + 1, -1 };

	a[++len] = y2 + 1, a[++len] = y1;

}

int inline getY(int y) {

	return lower_bound(a + 1, a + 1 + len, y) - a;

}

struct T{

	int len, cnt;

} t[N * 8];

void inline pushup(int p, int l, int r) {

	t[p].len = t[p].cnt ? a[r + 1] - a[l] : t[p << 1].len + t[p << 1 | 1].len;

}

void change(int p, int l, int r, int x, int y, int k) {

	if (x <= l && r <= y) {

		t[p].cnt += k;

		if (l == r) t[p].len = t[p].cnt ? a[r + 1] - a[r] : 0;

		else pushup(p, l, r);

		return;

	}

	int mid = (l + r) >> 1;

	if (x <= mid) change(p << 1, l, mid, x, y, k);

	if (mid < y) change(p << 1 | 1, mid + 1, r, x, y, k);

	pushup(p, l, r);

}

void inline fill() {

	for (int i = 1; i <= n; i++) {

		if (D[i] == 0) add(X[i], Y[i], X[i], Y[i] + f[i] - 1);

		else if (D[i] == 1)  add(X[i] - f[i] + 1, Y[i], X[i], Y[i]);

		else if (D[i] == 2) add(X[i], Y[i] - f[i] + 1, X[i], Y[i]);

		else add(X[i], Y[i], X[i] + f[i] - 1, Y[i]);

	}

	sort(e + 1, e + 1 + m);

	sort(a + 1, a + 1 + len);

	len = unique(a + 1, a + 1 + len) - a - 1;

	for (int i = 1; i <= m; i++) {

		change(1, 1, len, getY(e[i].l), getY(e[i].r) - 1, e[i].c);

		if (i != m && e[i].x != e[i + 1].x)

		 	ans += (e[i + 1].x - e[i].x) * (LL)t[1].len;

	}

}

int main() {

	scanf("%d%d%d", &W, &H, &n);

	for (int i = 1; i <= n; i++) {

		scanf("%d%d%d", Y + i, X + i, D + i);

		if (D[i] == 0) f[i] = W - Y[i] + 1;

		else if (D[i] == 1) f[i] = X[i];

		else if (D[i] == 2) f[i] = Y[i];

		else f[i] = H - X[i] + 1;

	}

	init();

	work();

	fill();

	printf("%lld\n", ans);

	return 0;

}

巴特西

APIO2012 苦无 Kunai