1.前言
（怎么每次都有这个？）
之前好像也做过两三道二维一维混杂的题目（而且我写的代码也非常冗），现在来总结一下吧。
2.题解
牛是一维的，线段（之后称为栅栏，因为觉得要贴近现实一点 qwq）也是一维的，就连数组也是一个一维的概念（应该很好理解），但是，答案所求是面积，是一个二维的概念，这样多维混杂的题目如果思路混乱，不仅代码冗长，而且会浪费大量的时间在调试上。
QAQ: 遇见这种问题，我们该怎么办呢？
AWA: 统一维度
由于我们的操作肯定是用数组进行，所以我们将面积变为一维去表示。
\(Firstly\)，\(x,y\) 的范围特别大，所以我们自然会想到离散化。
\(Secondly\)，我们的牛（起始点）就不需要一个单位一个单位的动了，而是一大格一大格地“跳跃”，如图。
没有离散化的话，我们只能像红点一样一个单位一个单位的走，但是离散化之后，我们就可以像蓝点一样，从 \(x_i\) 直接跳到下一个 \(x_{i + 1}\)。
\(Third\)，由于我们的牛只会在 \((x_i, y_j)\) 上，所以它可能会走到的点将成网格状分布，而且满足要求的部分一定会被划分成许多个矩阵。
如样例一，就可以这样划分。
\(Fourth\)，这样我们表达答案面积就可以表达为满足条件的矩阵之和，对于每一个矩阵，我们可以用一个“标兵”来表达它的位置，我这里选择的是右上角，所以说:离散化数组横纵坐标分别为 \(v1,v2\)，则左上角为 \((x,y)\)（离散化之后的坐标）的矩阵面积为 \((v1[x + 1] - v1[x]) \times (v2[y + 1] - v2[y])\)。
\(Fifth\)，那么，这个坐标要满足什么条件呢，首先，根据题意 \((0, 0)\)（未离散化）一定满足要求，直接丢进队列就行了。然后我们考虑当前的点是 \((x, y)\) （离散化后），则它向各个方向移动的条件为：
- 向下移动：\((x + 1, y)\) 不在横着的栅栏上
- 向上移动：\((x, y)\) 不在横着的栅栏上
- 向右移动：\((x, y + 1)\) 不在竖着的栅栏上
- 向左移动：\((x, y)\) 不在竖着的栅栏上
\(Fifth‘\)，还有一种 \(INF\) 的情况怎么判呢?即某个点可以走到 \(x < 0 \lor x \geq v1.size () \lor y < 0 \lor y \geq v2.size ()\) 的情况时，输出 \(INF\) 后 \(return\) \(0\) 就可以啦 owo。
3.参考代码
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define int long long
#define ULL unsigned long long
using namespace std;
template <typename T> int read (T &x) {x = 0; T f = 1;char tem = getchar ();while (tem < ‘0‘ || tem > ‘9‘) {if (tem == ‘-‘) f = -1;tem = getchar ();}while (tem >= ‘0‘ && tem <= ‘9‘) {x = (x << 1) + (x << 3) + tem - ‘0‘;tem = getchar ();}x *= f; return 1;}
template <typename T> void write (T x) {if (x < 0) {x = -x;putchar (‘-‘);}if (x > 9) write (x / 10);putchar (x % 10 + ‘0‘);}
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
const int Maxn = 1000;
const int Maxx = 3000;
int n, m;
int tox[10] = { 0, 1, -1, 0, 0 };
int toy[10] = { 0, 0, 0, 1, -1 };
bool h[Maxx + 5][Maxx + 5];
bool w[Maxx + 5][Maxx + 5];
bool vis[Maxx + 5][Maxx + 5];
struct Node {
int a, b, c;
void scan () { cin >> a >> b >> c; }
}sa[Maxn + 5], sb[Maxn + 5];
vector <int> v1, v2;
int Find1 (int x) { return lower_bound (v1.begin (), v1.end (), x) - v1.begin (); }
int Find2 (int x) { return lower_bound (v2.begin (), v2.end (), x) - v2.begin (); }
signed main () {
cin >> n >> m;
v1.push_back (0); v2.push_back (0);
for (int i = 1; i <= n; i++) {
sa[i].scan ();
v1.push_back (sa[i].a);
v1.push_back (sa[i].b);
v2.push_back (sa[i].c);
}
for (int i = 1; i <= m; i++) {
sb[i].scan ();
v1.push_back (sb[i].a);
v2.push_back (sb[i].b);
v2.push_back (sb[i].c);
}
sort (v1.begin (), v1.end ()); v1.erase (unique (v1.begin (), v1.end ()), v1.end ());
sort (v2.begin (), v2.end ()); v2.erase (unique (v2.begin (), v2.end ()), v2.end ());
//输入 + 离散化
for (int i = 1; i <= n; i++) {
sa[i].a = Find1 (sa[i].a);
sa[i].b = Find1 (sa[i].b);
sa[i].c = Find2 (sa[i].c);
for (int j = sa[i].a; j < sa[i].b; j++)
h[j][sa[i].c] = 1;
}
//竖着的线段
for (int i = 1; i <= m; i++) {
sb[i].a = Find1 (sb[i].a);
sb[i].b = Find2 (sb[i].b);
sb[i].c = Find2 (sb[i].c);
for (int j = sb[i].b; j < sb[i].c; j++)
w[sb[i].a][j] = 1;
}
//横着的线段
queue <pair <int, int> > q;
int sx = Find1 (0), sy = Find2 (0);
LL ans = 0;
vis[sx][sy] = 1;
q.push (make_pair (sx, sy));
while (q.size ()) {
pair <int, int> tem = q.front (); q.pop ();
int x = tem.first, y = tem.second;
ans += (v1[x + 1] - v1[x]) * (v2[y + 1] - v2[y]);
//左上角是 (x, y)，矩阵面积直接加上就行啦 qwq
for (int i = 1; i <= 4; i++) {
if (w[x][y] == 1 && i == 2) continue;
if (h[x][y] == 1 && i == 4) continue;
int xx = x + tox[i], yy = y + toy[i];
if (xx < 0 || xx >= (int)v1.size () || yy < 0 || yy >= (int)v2.size ()) {
printf ("INF");
return 0;
}
if (w[xx][yy] == 1 && i == 1) continue;
if (h[xx][yy] == 1 && i == 3) continue;
//之前说的各种判断条件
if (vis[xx][yy] == 1) continue;//已经走过啦
vis[xx][yy] = 1;//标记为已走过
q.push (make_pair (xx, yy));//扔进去
}
}
cout << ans;//Finshed 完结撒花
return 0;
}
4.小结
这道题卡了我好久，我之前一直强制用夹在线段中间的坐标 \((\frac{x * 2 + 1}{2}, \frac {y * 2 + 1}{2})\) 来表示二维面积，结果代码冗长，而且心态爆炸，后来代码越改越乱，思路也越来越乱。之后遇见这种多种维度并存的题，尽量选用一维的表示方法，因为用于存储的数据结构大多都是一维的概念，这样就会方便记录和操作。
之后这种题就不需要写题解辣