【杂项】离散化

CNS_5t0_0r2 · 2023-09-30 19:20:04 · 算法·理论

引入：

离散化是一种忽略无用数据，起到压缩值域的作用。

一般，用到离散化的题需要具备两个条件：

1. 题目需要离线，强制在线基本就挂了。

2. 题目只与数值的大小关系相关，与具体的值无关。

一种很简单的方法，就是将所需要离散化的值用一个临时数组存起来，然后排序去重，再使用二分查找将原序列的每一个数对应到离散化数组对应数的下标，就可以将一个值域很大的序列值域压缩到 O(n) 级别（n 为序列长度）。

例题1：程序自动分析

不难想到，可以使用并查集解此题。

问题是这个值域太大了，不难发现，这 10^9 个变量最多只有 2 \times 10^5 个会用到，其他的都与答案没有任何关系，并且与变量是第几个这个具体数值无关。所以我们用离散化，将关系变量值域压缩至 2 \times 10^5，即可通过此题。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int fa[N << 2];
int father(int x){
    return fa[x] == x ? x : fa[x] = father(fa[x]);
}
void join(int x,int y){
    int fa_x = father(x),fa_y = father(y);
    fa[fa_y] = fa_x;
}
struct queries{
    int i,j,e;
} q[N << 1];
int t,n;
int tmp[N << 2],top;
int main(){
    scanf("%d", &t);
    for(;t;t--){
        scanf("%d", &n);
        top = 0;
        for(int i = 1;i <= n;i++){
            scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].e);
            tmp[++top] = q[i].i;
            tmp[++top] = q[i].j;
        }
        sort(tmp + 1,tmp + top + 1);
        top = unique(tmp + 1,tmp + top + 1) - tmp - 1;
        for(int i = 1;i <= top;i++)
            fa[i] = i;
        for(int i = 1;i <= n;i++){
            q[i].i = lower_bound(tmp + 1,tmp + top + 1,q[i].i) - tmp;
            q[i].j = lower_bound(tmp + 1,tmp + top + 1,q[i].j) - tmp;
            if(q[i].e == 1)
                join(q[i].i,q[i].j);
        }
        bool check = true;
        for(int i = 1;i <= n;i++){
            if(q[i].e == 0){
                if(father(q[i].i) == father(q[i].j)){
                    puts("NO");
                    check = false;
                    break;
                }
            }
        }
        if(check)
            puts("YES");
    }
}