[TIOJ 1672]分子碰撞實驗

我們先假設$N*M$足夠小，可以用$O(NM)$的做法
怎麼做呢？

假設$S[i]=(第1\sim i瓶的分子數總和\mod 2)$
當作了實驗$(l,r,c)$之後，我們可以得到$S[r]-S[l-1]=c\ (\mod 2)$

實作上可以建圖，點$i$的狀態就是$S[i]$，一開始邊數0，每個點的狀態都被假設為0
每做一次實驗$(l,r,c)$相當於在$l-1$和$r$之間連一條權重$c$的邊
我們必須維護$S[r]-S[l-1]=c\ (\mod 2)$，因此視情況，連邊前可能會需要反轉$r$或$l-1$所在的這個連通塊裡面全部的點

特別的，如果$r$和$l-1$在同一個連通塊裡面 (可以用並查集判斷)，直接檢查他們的狀態有沒有合法即可

這樣的話時間複雜度是$O(NM)$，若套用啟發式合併可以達到$O(N\log N +M)$

現在$N$位於$int$範圍
可以發現，上述做法可以允許$l-1$和$r$被離散化

離散化+啟發式合併的時間複雜度為$O(M\log M+M)$

相信細心的同學可以觀察到，主要的時間花費在「反轉整個連通塊」這個操作上
那麼，我們可以不要反轉嗎？

可以的！

像平行世界一樣，同一個點可以同時處於多個狀態，但不允許不同的狀態間有聯繫，在本題，一個點的狀態有可能是「這個點是0」或「這個點是1」
每做一個實驗，就像是把兩個點纏結起來
如果$c=0$，就變成：「$l-1$是0」$\Leftrightarrow $「$r$是0」、「$l-1$是1」$\Leftrightarrow $「$r$是1」
如果$c=1$，就變成：「$l-1$是0」$\Leftrightarrow $「$r$是1」、「$l-1$是1」$\Leftrightarrow $「$r$是0」
雙箭頭代表兩邊的平行世界被打通了！(好啦學術上來講就是可以互推XD)

看出端倪了嗎？當錯誤的實驗數據進來時，會讓同一個點的兩個不同狀態被打通，這樣這個平行世界就悲劇了QAQ (你會發現，當你打開家門，你正坐在客廳看電視)

咦？相信大家已經了解這個想法了
可以把每個點都變成兩個狀態 (拆成兩個點)，用並查集維護哪些平行世界是相通的

為了避免你下次回家發現你已經在家，在平行世界相撞前 (發現錯誤的實驗數據)，你必須馬上向judge回報這次實驗是錯誤的

時間複雜度：$O(M+M\log M+M\alpha(M))$ (初始化並查集+離散化+$M$次查詢合併)

Warning: 注意本題不保證$l\leq r$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
struct Djset
{
    int s[40000];
    void clear(const int n){assert(n<=40000);for(int i=0;i<n;i++)s[i]=i;}
    int find(const int a){return s[a]==a?a:(s[a]=find(s[a]));}
    bool merge(int a,int b){if((a=find(a))==(b=find(b)))return false;s[a]=b;return true;}
    int operator[](const int i){return find(i);}
}DJ;
struct Experiment
{
    int l,r,c;
    Experiment(){}
    Experiment(const int _l,const int _r,const int _c):l(_l),r(_r),c(_c){}
};
vector<Experiment>EXP;
int N,M;
void Discretize()
{
    vector<int>v;
    for(const Experiment &e:EXP)v.push_back(e.l),v.push_back(e.r);
    sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
    M=v.size();
    for(Experiment &e:EXP)e.l=lower_bound(v.begin(),v.end(),e.l)-v.begin(),e.r=lower_bound(v.begin(),v.end(),e.r)-v.begin();
    v.clear(),vector<int>().swap(v);
}
int Solve()
{
    DJ.clear(M*2);
    for(int i=0;i<(int)EXP.size();i++)
    {
        const Experiment &e=EXP[i];
        if(e.c==0)
        {
            DJ.merge(e.l,e.r);//打通平行世界！
            DJ.merge(M+e.l,M+e.r);//打通平行世界！
        }
        else if(e.c==1)
        {
            DJ.merge(e.l,M+e.r);//打通平行世界！
            DJ.merge(M+e.l,e.r);//打通平行世界！
        }
        else assert(0);
        if(DJ[e.l]==DJ[M+e.l])return i;//平行世界相撞惹QAQ
    }
    return EXP.size();
}
int main()
{
//    freopen("in.txt","r",stdin);
    for(;;)
    {
        assert(scanf("%d%d",&N,&M)==2);
        if(N==0&&M==0)break;
        EXP.clear();
        for(int i=0,l,r,c;i<M;i++)
        {
            assert(scanf("%d%d%d",&l,&r,&c)==3);
            if(l>r)swap(l,r);
            EXP.push_back(Experiment(l-1,r,c));
        }
        Discretize();
        const int ans=Solve();
        if(ans==(int)EXP.size())puts("He didn't lie.");
        else printf("%d\n",ans+1);
    }
    assert(scanf("%d",&N)==-1);
    return 0;
}