poj 1733 Parity game

思路: 帶權並查集
分析:
1 題目給定n個條件，要我們找到第一個不滿足條件的編號
2 每一個條件給的是區間[l,r]的1的奇偶數，很明顯[l,r]這個區間的1的個數可以由[0,r]-[0,l-1]得來
3 那麼我們利用並查集的思想，rank[x]表示的是x到跟節點這個區間即[x,father[x]]這個區間的1的個數，那麼奇偶性可以由1和0來表示
4 題目還有一個難點就是要離散化，一般的離散化的步驟是排序+去重，然後找的時候利用二分即可

代碼:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 50010;

struct Node{
    int x;
    int y;
    int mark; 
};
Node node[MAXN];
int arr[MAXN] , pos;
int father[MAXN] , rank[MAXN] , num;

void init(){
    sort(arr , arr+pos);
    num = unique(arr , arr+pos)-arr;
    memset(rank , 0 , sizeof(rank));
    for(int i = 0 ; i <= num ; i++)
        father[i] = i;
}

int find(int x){
    if(father[x] != x){
        int fa = father[x];
        father[x] = find(father[x]);
        rank[x] = (rank[x]+rank[fa])%2;
    }
    return father[x];
}

int search(int x){
    int left = 0;
    int right = num-1;
    while(left <= right){
        int mid = (left+right)>>1;
        if(arr[mid] == x)
            return mid; 
        else if(arr[mid] < x)
            left = mid+1;
        else 
            right = mid-1;
    }
}

int solve(int n){
    for(int i = 0 ; i < n ; i++){
        int x = search(node[i].x)+1;    
        int y = search(node[i].y)+1;    
        int fx = find(x); 
        int fy = find(y);
        int val = node[i].mark;
        if(fx == fy){
            if((rank[y]-rank[x]+2)%2 != val) 
                return i;
        }
        else{
            father[fx] = fy;
            rank[fx] = (val+rank[y]-rank[x]+2)%2;
        }
    }
    return n;
}

int main(){
    int len , n;
    char str[10];
    while(scanf("%d%d" , &len , &n) != EOF){
        pos = 0;
        for(int i = 0 ; i < n ; i++){ 
            scanf("%d %d %s" , &node[i].x , &node[i].y , str);
            node[i].x--;
            arr[pos++] = node[i].x;
            arr[pos++] = node[i].y;
            if(str[0] == 'e')
                node[i].mark = 0;
            else
                node[i].mark = 1;
        }
        init();
        printf("%d\n" , solve(n));
    }
    return 0;
}