题解 P1955 【[NOI2015]程序自动分析】

· · 题解

离散化+并查集。

还算是比较好写的。

首先观察题目，我们发现i,j的值过大，我们可以离散化一下。

其次，我们发现每组条件改变顺序不会影响结果，我们可以离线进行操作。

如果是在线的话，需要用到种类并查集，而离线的话，我们可以先处理所有相等的情况，把他们连到一个集合里面，然后再判断所有不等的情况，一旦发生矛盾立即停止输出。

对于离散化，我们可以开结构体记录下每个i,j，离散化后再按照编号排序回来，然后对于每个编号为q询问，它对应的离散化数组a中的i,j为a[2p-1],a[2p].

还有，要记得开两倍空间，因为每一个问题对应的是两个需要离散化的值，(因为这个我被坑了一次提交。)

代码的话写的应该是很清楚的，分组处理，注意初始化！

Code: 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
int cnt;

struct Node {
    int num , val , w;
}a[N];

bool cmp1(Node a , Node b) {return a.val < b.val;}
bool cmp2(Node a , Node b) {return a.num < b.num;}

struct Qus {
    int x , y , num;
    bool flag;
    bool operator < (const Qus &a) const {
        return flag > a.flag;
    }
}q[N];

int bin[N];

int find(int x) {
    if(bin[x] == x) return x;
    return bin[x] = find(bin[x]);
}

void add(int x , int y) {
    int fx = find(x) , fy = find(y);
    if(fx != fy) bin[fx] = fy;
}

void Solve() {
    int n;
    cnt = 0;
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; ++ i) {
        bin[i] = i; bin[i + n] = i + n;
        scanf("%d %d %d" ,&q[i].x , &q[i].y , &q[i].flag);
        q[i].num = i;
        a[++ cnt].num = i , a[cnt].val = q[i].x;
        a[++ cnt].num = i , a[cnt].val = q[i].y;
    }
    sort(a + 1 , a + 1 + cnt , cmp1);
    int cur = 0;
    for(int i = 1 ; i <= cnt ; ++ i) {
        if(a[i].val != a[i - 1].val) a[i].w = ++ cur;
        else a[i].w = cur; 
    }
    sort(a + 1 , a + 1 + cnt , cmp2);
    sort(q + 1 , q + 1 + n);
    for(int i = 1 ; i <= n ; ++ i) {
        int num = q[i].num;
        if(q[i].flag == 1) {
            add(a[num * 2].w , a[num * 2 - 1].w);
        } else {
            if(find(a[num * 2].w) == find(a[num * 2 - 1].w)) {
                puts("NO"); return;
            }
        }
    }
    puts("YES");
}

int main () {
    int T;
    scanf("%d" , &T);
    while(T -- ) Solve(); 
    return 0;
}