題目

https://www.nowcoder.com/acm/contest/119/A

題目大意

每次查詢告訴你[l,r]之間的數(shù)的異或和，如果遇到不正確的查詢，輸出查詢編號。

算法思路

• 因為異或和前綴是不影響他的值，所以我們只需要將l和r連線，以異或值為權(quán)值，帶權(quán)并查集即可。
• 每次查詢?nèi)绻鹟和r在同一集合中，檢查與其值是否相符即可。若不在，直接相連即可。
• 帶權(quán)并查集的操作

int Find(int x)
{
    if(x==fa[x])return x;
    int temp=fa[x];
    fa[x]=Find(fa[x]);//路徑壓縮
    rnk[x]=rnk[x]^rnk[temp];//更新rnk值
    return fa[x];
}

合并操作

 int ru=Find(u);
        int rv=Find(v);
        if(ru!=rv) {
            fa[ru]=rv;
            rnk[ru]=k^rnk[u]^rnk[v];
/*這里需要想一想；然后只更新了根節(jié)點的值，
子節(jié)點的值可以在后續(xù)查詢find的時候更新*/
        }

• 為了方便操作，采用左開右閉（常規(guī)操作）

代碼

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+5;
int fa[N];
ll rnk[N];
void Init(int n)
{
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;
        rnk[i]=0;
    }
}
int Find(int x)
{
    if(x==fa[x])return x;
    int temp=fa[x];
    fa[x]=Find(fa[x]);
    rnk[x]=rnk[x]^rnk[temp];
    return fa[x];
}

int main()
{
    int n,m;
    while(cin>>n>>m){
        Init(n+1);
        int flag=0;
    for(int i=1;i<=m;i++){
         int u,v;
         ll k;
        scanf("%d%d%lld",&u,&v,&k);
        v++;
        int ru=Find(u);
        int rv=Find(v);
        if(ru!=rv) {
            fa[ru]=rv;
            rnk[ru]=k^rnk[u]^rnk[v];
        }
        else
        {
            if((rnk[v]^rnk[u])!=k) {flag=1;cout<<i<<endl;}
        }
    }
    if(!flag) cout<<-1<<endl;
    }
    return 0;
}