\(\\\)
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 句话，输出假话的总数。
- \(n\le 5\times 10^4,K\le 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\n",ans);
return 0;
}