(\)
Description
有三类动物 (A,B,C)，满足(A) 吃 (B)，(B)吃 (C)，(C) 吃 (A)。
现有 (N) 个动物，以 (1 － N) 编号。每个动物都是 (A,B,C) 中的一种。
有人用两种说法对这 (N) 个动物所构成的食物链关系进行描述：
第一种说法是“1 X Y”，表示 X 和 Y 是同类。
第二种说法是“2 X Y”，表示 X 吃 Y 。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真
的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
-
当前的话与前面的某些真的话冲突，就是假话
-
当前的话中 X 或 Y 比 N 大，就是假话
-
当前的话表示 X 吃 X，就是假话
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
- (nle 5 imes 10^4,Kle 10^5)
(\)
Solution
扩展域的并查集。
建立三个域，分别为 (x,x+n,x+2n)。
如果 (x,y) 在一个集合里，代表 (x,y) 是同类。
如果 (x+n,y) 在一个集合里，代表 (y) 为 (x) 的捕食对象。
如果 (x+2n,y) 在一个集合里，代表 (y) 为 (x) 的天敌。
注意这里以 (x) 为中心构建的集合，具有代表意义。
即 (x+n,x+2n) 只作为中转点，所在的集合中所有 (n) 范围内的点含义相同。
(\)
对于同类语句：
如果某一个是另一个的天敌或捕食对象 (GG) 。
否则合并两者的三个集合。
(\)
对于捕食语句 ((x) 捕食 (y))：
如果两者是同类 (GG) 。
如果 (y) 是 (x) 的天敌 (GG) 。
因为只有三个集合，所以合并：
-
(x) 和 (y+2n)： (x) 是 (y) 的天敌。
-
(x+n) 和 (y) ： (y) 是 (x) 的捕食对象。
-
(x+2n) 和 (y+n) ：第三类关系，(x) 的天敌一定是 (y) 的捕食对象。
(\)
在这个过程中应该有一些思考。
合并的有效对象其实一直是 ([1,n]) 范围内的点，而我们只是通过等价关系借用了两个扩展域合并。
所有的查询也是借用定义，实则查的其实还是 ([1,n]) 范围内的点。
(\)
Code
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 150010
#define R register
#define gc getchar
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
int n,m,ans,f[N];
inline void reset(){for(R int i=1;i<N;++i) f[i]=i;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline void merge(int x,int y){f[find(x)]=find(y);}
int main(){
n=rd(); m=rd(); reset();
for(R int i=1,op,x,y;i<=m;++i){
op=rd(); x=rd(); y=rd();
if(x>n||y>n){++ans;continue;}
if(op==1){
if(find(x)==find(y+n)||find(x)==find(y+2*n)){++ans;continue;}
merge(x,y); merge(x+n,y+n); merge(x+n*2,y+n*2);
}
else{
if(x==y){++ans;continue;}
if(find(x)==find(y)||find(x+2*n)==find(y)){++ans;continue;}
merge(x,y+n*2); merge(x+n,y); merge(x+n*2,y+n);
}
}
printf("%d
",ans);
return 0;
}