记录编号	584244	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]程序自动分析	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.008 s
提交时间	2023-11-04 14:28:33	内存使用	4.77 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 2e5+10;
int t,n,tot;
int f[N],a[N];//a为离散数组 
struct made{
    int l,r,op;
}e[N];//离线操作 
int find(int x){
    if(x == f[x])return x;
    return f[x] = find(f[x]);
}
int main(){
    freopen("prog.in","r",stdin);
    freopen("prog.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        tot = 0;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++){
           scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].op); 
           a[++tot] = e[i].l;
           a[++tot] = e[i].r;
        }
        sort(a+1,a+1+tot);
        int m = unique(a+1,a+1+tot) - (a+1);
        for(int i = 1;i <= m;i++)f[i] = i;
        for(int i = 1;i <= n;i++){
            if(e[i].op == 1){
                int x = lower_bound(a+1,a+1+m,e[i].l) - a;
                int y = lower_bound(a+1,a+1+m,e[i].r) - a;
                f[find(x)] = find(y);
            }
        }//把相等的放到一个并查集里 
        int f = 1;
        for(int i = 1;i <= n;i++){
            if(e[i].op == 0){
                int x = lower_bound(a+1,a+1+m,e[i].l) - a;
                int y = lower_bound(a+1,a+1+m,e[i].r) - a;
                if(find(x) == find(y)){
                    printf("NO\n");
                    f = 0;break;
                }//不等矛盾 
            }
        }
        if(f)printf("YES\n");
    }
    
    return 0;
    
}