这题网上貌似还没有完整的题解呢，我来口胡一下~
Description
(W imes 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) 点对（方向不能反），还要支持删除点。
如果我们考虑每个点匹配的最优点，我们是可以通过 ( ext{set}) 在 (log) 时间算出前驱后继，但删除一个点的时候，可能有多个点的最有匹配是他，要修改多个点，这样就挂了。不妨考虑双向匹配，我们维护 (x, y) 互相都作为对方的最优匹配这样的点对，这样是对的，因为单向匹配总能找到更优的双向匹配。所以在删除的一个点的时候，如果他在双向匹配里，让他的匹配点找新的匹配，即可。
这样时间复杂度就是 (O(n log n))
接下来的工作就是把双向匹配放进一个堆里，每次把所有时间最短的点拿出来删除就行。
一些细节
- 关于横竖直线，距离为奇数点的相撞时间问题。比如相邻的两个 → ←，如果右箭头上方有一个下箭头（如题面右下角的图），那个箭头不会相撞，说明相撞时间 (> 1)，但如果相撞时间又得 $ < 2$，否则会和左箭头相撞，因此这种的相撞时间应该是 (1.5)。我是把时间整体 ( imes 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
", ans);
return 0;
}