[51nod1515]明辨是非

Description

给$n$组操作,每组操作形式为$x;y;p$.

当$p=1$时,如果第$x$变量和第$y$个变量可以相等,则输出$YES$,并限制他们相等;否则输出$NO$,并忽略此次操作.

当$p=0$时,如果第$x$变量和第$y$个变量可以不相等,则输出$YES$,并限制他们不相等;否则输出$NO$,并忽略此次操作.

Input

输入一个数$n$表示操作的次数.接下来$n$行每行三个数$x,y,p$.

Output

对于$n$行操作，分别输出$n$行$YES$或者$NO$.

Sample Input

3

1 2 1

1 3 1

2 3 0

Sample Output

YES

YES

NO

HINT

$n;leq;10^5,x,y;leq;10^8,p=0;or;1$.

Solution

离散化所有的变量.

可以用并查集维护相等的关系,$set$维护不等的关系.

当$p=1$时,如果$x,y$都不在对方的$set$中,则可行,按$set$大小合并它们的父亲和$set$;

当$p=0$时,如果$f[x] ot=f[y]$,把$f[x],f[y]$分别插入对方的$set$中.

#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 200005
using namespace std;
int a[N],f[N],x[N],y[N],p[N],n,m;
set<int> s[N];
set<int>::iterator l;
inline int gf(int k){
    if(f[k]==k) return k;
    return f[k]=gf(f[k]);
}
inline int search(int k){
    int l=1,r=m,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(a[mid]<k) l=mid+1;
        else r=mid;
    }
    return l;
}
inline void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&x[i],&y[i],&p[i]);
        a[++m]=x[i];a[++m]=y[i];
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=n;++i){
        x[i]=search(x[i]);
        y[i]=search(y[i]);
    }
    for(int i=1;i<=m;++i) f[i]=i;
    for(int i=1,j,k,q;i<=n;++i){
        j=gf(f[x[i]]);k=gf(f[y[i]]);
        if(!p[i]){
            if(j==k) puts("NO");
            else{
                puts("YES");
                s[j].insert(k);
                s[k].insert(j);
            }
        }
        else{
            if(j==k) puts("YES");
            else if(s[j].count(k)||s[k].count(j)) puts("NO");
            else{
                puts("YES");
                if(s[j].size()>s[k].size()){
                    q=j;j=k;k=q;
                }
                f[j]=k;
                for(l=s[j].begin();l!=s[j].end();++l){
                    q=gf(*l);
                    s[*l].erase(j);
                    s[q].insert(k);
                    s[k].insert(q);
                }
                s[j].clear();
            }
        }
    }
}
int main(){
    freopen("judge.in","r",stdin);
    freopen("judge.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}