手机程序开发_网络代理服务器出现问题_百度seo费用_成都互联网公司排名

题意

动物王国中有三类动物 $A,B,C$，存在 $A$ 吃 $B$、$B$ 吃 $C$、$C$ 吃 $A$ 的关系。

现有 $N$ 个动物，以 $1\sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

• 第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
• 第二种说法是2 X Y，表示 $X$ 吃 $Y$。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真话冲突，就是假话；
• 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
• 当前的话表示 $X$ 吃 $X$，就是假话。

你的任务计算是 $K$ 句话中假话的总数。

$1\le N\le 5\times 10^4$，$1\le K\le 10^5$。

思路

如果有 $4$ 句话：

1 1 2
1 2 3
1 3 4
1 4 1

那么 $1$ 和 $4$ 是同类。但是使 $1$ 和 $4$ 是同类的还有一组特殊的 $4$ 句话：

2 1 2
2 2 3
2 3 4
2 4 1

此时 $1$ 和 $4$ 同为一类。那这就是一道有趣的题目了。

不妨大胆想象，因为只有三类，形成三角有向关系，那就可以尝试类别扩展：

• 把 $A$、作为猎物的 $B$、作为猎食者的 $C$ 归为 $A$ 类；
• 把 $B$、作为猎物的 $C$、作为猎食者的 $A$ 归为一类；
• 把 $C$、作为猎物的 $A$、作为猎食者的 $B$ 归为一类。

那么在一句真话中，一个 $X$ 可以有三重身份：$X$ 自己、$X$ 作为猎食者、$X$ 作为猎物。那不妨用分层图思想：$X,X+n,X+2n$ 分别代表三种身份。这样就很方便判断条件真假了。

那么对于种类为 $op$ 的语句，两只动物 $u,v$：

$op=1$，“$u,v$ 是同类”

• $u$ 和猎物 $v+n$ 同类，或者 $v$ 和猎物 $u$ 同类，就是假话；
• 否则就是真话，$u$ 和 $v$ 同类，猎食者 $u+n$ 和猎食者 $v+n$ 同类，猎物 $u+2n$ 和猎物 $v+2n$ 同类。

$op=2$，“ $u$ 吃 $v$ ”

• $u$ 和 $v$ 同类，或者猎物 $u$ 和 $v$ 同类，就是假话；
• 否则就是真话，猎食者 $u+n$ 和 $v$ 同类，猎食者的猎物的猎物（思考一下，是猎食者的“猎食者”）$u+2n$ 和猎食者 $v+n$ 同类，$u$ 和猎物 $v+2n$ 同类。

分析完毕，码量较小，具体细节见代码：

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=3e5+9;
ll n,k;
ll fa[N];
//A:1~n B:n+1~2n C:2n+1~3n 
ll fz(ll x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;
}
void join(ll u,ll v)
{u=fz(u),v=fz(v);if(u==v)return;fa[v]=u;
}
int main()
{scanf("%lld%lld",&n,&k);for(int i=1;i<=3*n;i++)fa[i]=i;ll ans=0;for(int i=1;i<=k;i++){ll op,u,v,ha,fp;scanf("%lld%lld%lld",&op,&u,&v); if(u>n||v>n){ans++;continue;}//假话2if(op==1){if(fz(u)==fz(v+n)||fz(v)==fz(u+n)){ans++;continue;}//v吃u 或 u吃v join(u,v);join(u+n,v+n);join(u+2*n,v+2*n);}else //u吃v {if(fz(u)==fz(v)||fz(u)==fz(v+n)){ans++;continue;}//同类 或 v吃ujoin(u+n,v);join(u+2*n,v+n);join(u,v+2*n);}}printf("%lld",ans);return 0;
}