lyd 大佬给予蒟蒻们的人口普查题……
由于题目并没有问第一个不满足的约束条件，所以可以根据“相等”条件的传递性，先扫描所有相等的条件并把两个操作数并入一个集合。
然后扫描不等的条件，看是否已经属于同一个集合。
不过如果要求第一个不满足的可以加个二分答案。
注意离散化。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
const int N = 1e6;
int t;
int n;
vector<int> q[3],s[2];
int ind[(N << 1) + 10],tot,len;
int fa[(N << 1) + 10];
bool flag;
int get(int x)
{
return fa[x] == x ? fa[x] : fa[x] = get(fa[x]);
}
int main()
{
scanf("%d",&t);
while(t--)
{
flag = 1,tot = 0;
q[0].clear(),q[1].clear(),q[2].clear(),s[0].clear(),s[1].clear();
scanf("%d",&n);
for(register int i = 1;i <= (n << 1);++i)
fa[i] = i;
int x,y,z;
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",&x,&y,&z),q[0].push_back(x),q[1].push_back(y),q[2].push_back(z),ind[++tot] = x,ind[++tot] = y;
sort(ind + 1,ind + tot + 1);
len = unique(ind + 1,ind + tot + 1) - ind - 1;
for(register int i = 0;i < q[0].size();++i)
{
x = lower_bound(ind + 1,ind + len + 1,q[0][i]) - ind;
y = lower_bound(ind + 1,ind + len + 1,q[1][i]) - ind;
z = q[2][i];
if(z)
fa[get(x)] = get(y);
else
s[0].push_back(x),s[1].push_back(y);
}
for(register int i = 0;i < s[0].size();++i)
if(get(s[0][i]) == get(s[1][i]))
{
puts("NO");
flag = 0;
break;
}
if(flag)
puts("YES");
}
}