带权并查集处理线段

例题：Parity (POJ 1733)

题目大意：给你一个01序列，并且给你$m$个信息，每个信息包含三个数字$(l,r,parity)$，意为区间$[l,r]$中有奇数/偶数个1。（序列长度不超过$10^9$，且$m\le5000$）

现在有一个数字$p$，使得存在数列满足前$p$条信息，求$p$的最大值。

解题思路

思路：设$seg[i]$代表$i$的根节点，$val[i]$代表$i$到其根节点（不含$i$）的奇偶性。

带权并查集即可。

AC代码

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const int maxn = 5e3 + 100;
const ll mod = 1e9 + 7;

ll n, m;
int l[maxn], r[maxn], ans[maxn];
int unq[2 * maxn], unqlen;
char buffer[50];

int seg[maxn], val[maxn];

int lookup(int rt){
    if(rt == seg[rt]) return rt;
    int tmp = seg[rt];
    seg[rt] = lookup(tmp);
    val[rt] ^= val[tmp];
    return seg[rt];
}

void solve(){
    unqlen = 0;

    cin >> m;
    for(int i=0; i<m; i++){
        cin >> l[i] >> r[i] >> buffer;
        r[i]++;
        unq[unqlen++] = l[i];
        unq[unqlen++] = r[i];
        if(buffer[0] == 'e') ans[i] = 0;
        else ans[i] = 1;
    }

    sort(unq, unq + unqlen);
    unqlen = unique(unq, unq + unqlen) - unq;
    for(int i=0; i<m; i++){
        l[i] = lower_bound(unq, unq + unqlen, l[i]) - unq;
        r[i] = lower_bound(unq, unq + unqlen, r[i]) - unq;
    }

    for(int i=0; i<=unqlen; i++){
        seg[i] = i;
        val[i] = 0;
    }

    for(int i=0; i<m; i++){
        int p1 = lookup(l[i]), p2 = lookup(r[i]);
        if(p1 == p2){
            int parity = (val[l[i]] ^ val[r[i]]) & 1;
            if(parity != ans[i]){
                cout << i << '\n';
                return;
            }
        }else{
            val[p2] = val[p2] ^ val[r[i]] ^ val[l[i]] ^ ans[i];
            seg[p2] = p1;
        }
    }
    cout << m << '\n';
}

signed main(){
    Android;
    while(cin >> n){
        if(n == -1) break;
        solve();
    }
}