离散化 — 题解 for 程序自动分析

传送门

初一看是道并查集题。但是 $10^9$ 的数据范围开数组一定会炸内存。但是我们注意到 $n$ 的范围比较小，所以可以考虑用一种绝妙的优化空间的方法——离散化。

离散化

为了应对这种询问量少而编号特别大的情况，可以考虑把那些大数据映射到小数据中。

具体操作就是离散化三部曲。

1. 排序
2. 去重
3. 二分查找对应位置

这样把旧位置映射到新位置上，就是离散化的过程。

for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &data[i].x, &data[i].y, &data[i].e);
    vec.push_back(data[i].x);    // 使用 vector 来存储数据
    vec.push_back(data[i].y);
}
sort(vec.begin(), vec.end());    // 排序
vec.erase(unique(vec.begin(), vec.end()), vec.end());    // 去重
for (int i = 1; i <= n; i++) {
    data[i].x = lower_bound(vec.begin(), vec.end(), data[i].x) - vec.begin();    // 二分查找旧数据在新数组的位置，并把它赋值到原来的数组上
    data[i].y = lower_bound(vec.begin(), vec.end(), data[i].y) - vec.begin();    // lower_bound 函数返回的是一个地址，把它减去 vec 的初始地址就是下标
}
// 这样进行一波操作后，data 数组就变成了离散化后的数组

需要注意的是，并查集初始化需要使用新的数组长度，即 vec 的长度，为 vec.end() - vec.begin() 的值。

完整代码

#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 10;
struct node {
    int x, y, e;
    bool operator < (const node &rhs) const {
        return e > rhs.e;
    }
} data[maxN];
int n, T;
int par[maxN];
void init(int len) {
    for (int i = 1; i <= len; i++) par[i] = i;
}
int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}
bool same(int x, int y) {
    return find(x) == find(y);
}
void unite(int x, int y) {
    if (!same(x, y)) par[find(y)] = par[x];
}
int main() {
    scanf("%d", &T);
    while (T--) {
        vector<int> vec;
        bool flag = true;
        memset(data, 0, sizeof(data));
        memset(par, 0, sizeof(par));    // 并查集的 par 数组每次需要初始化
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &data[i].x, &data[i].y, &data[i].e);
            vec.push_back(data[i].x);
            vec.push_back(data[i].y);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        for (int i = 1; i <= n; i++) {
            data[i].x = lower_bound(vec.begin(), vec.end(), data[i].x) - vec.begin();
            data[i].y = lower_bound(vec.begin(), vec.end(), data[i].y) - vec.begin();
        }
        init(vec.end() - vec.begin());    // 以 vec 的长度初始化并查集
        sort(data + 1, data + n + 1);
        for (int i = 1; i <= n; i++)
            if (data[i].e) unite(data[i].x, data[i].y);    // 如果满足 e == 1 则合并
            else if (same(data[i].x, data[i].y)) flag = false;    // 否则判断它们是否在一个集合内，如果是则输出 NO
        printf("%s\n", flag ? "YES" : "NO");
    }
}