【传送门：BZOJ4195】
简要题意：
有T组数据，每组数据有n个约束条件i,j,e，如果e=1，说明a[i]=a[j]，如果e=1，说明a[i]!=a[j]
如果这组数据的约束条件有矛盾，则输出NO，不然输出YES
题解：
肯定要先离散化，不然i，j太大了
然后先把所有相等的条件进行，用并查集维护，如果相等，则合并到一个集合里
然后枚举每一个不相等的条件，如果当前枚举的i，j属于一个集合，那么就说明有矛盾
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct LSnode { int x,p,z; }A[2100000],B[2100000]; int cmp(const void *x1,const void *x2) { LSnode n1=*(LSnode *)x1; LSnode n2=*(LSnode *)x2; return n1.x-n2.x; } int e[1100000]; int fa[2100000]; int findfa(int x) { if(fa[x]!=x) fa[x]=findfa(fa[x]); return fa[x]; } int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&A[2*i-1].x,&A[2*i].x,&e[i]); A[2*i-1].p=2*i-1; A[2*i].p=2*i; } for(int i=1;i<=2*n;i++) { B[i].x=A[i].x; B[i].p=A[i].p; } qsort(B+1,2*n,sizeof(LSnode),cmp); B[1].z=1; for(int i=2;i<=2*n;i++) { if(B[i].x==B[i-1].x) B[i].z=B[i-1].z; else B[i].z=B[i-1].z+1; } for(int i=1;i<=2*n;i++) A[B[i].p].z=B[i].z; for(int i=1;i<=2*n;i++) fa[i]=i; bool bk=true; for(int i=1;i<=n;i++) { int x=A[2*i-1].z,y=A[2*i].z; int fx=findfa(x),fy=findfa(y); if(e[i]==1) { if(fx!=fy) fa[fy]=fx; } } for(int i=1;i<=n;i++) { int x=A[2*i-1].z,y=A[2*i].z; int fx=findfa(x),fy=findfa(y); if(e[i]==0) { if(fx==fy) { bk=false; break; } } } if(bk==false) printf("NO "); else printf("YES "); } return 0; }