poj 1733 Parity game （带权并查集）（离散化）

这道题大致题意是给你一个字符串，由0和1组成，给出子串的范围，并且告诉你子串里面1的个数，假设前面的话都是对的，问你到哪一句和前面的话矛盾。

1、离散化：

离散化主要是解决字符串的区间是从1到1000000000，这样的话用数组就存不下，但是他最多会给出5000个区间，这样的话就可以用离散化来解决了~

也就是说有用的数字也就有5000*2个，那么我们只需要定义一个5000*2的数组来存区间，排序并且去重，这样在找一个数字的时候就可以用二分快速找到，查找复杂度为logn。

但是如何记录数字的顺序呢？只需要开始的时候定义一个结构体数组，再离散化，最后再按顺序遍历结构体的元素就行了；

2、带权并查集

还有一个知识点是题目要我们分析给出区间的1的个数奇偶性，其实一个数不是奇数就是偶数，也就是说只有两种状态，这样和之前几道带权并查集的性质就类似了，定义一个Rank数组，路径压缩的时候只要Rank[x] = (Rank[x]+Rank[per])%2一下就下了

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

const int maxn = 5e4+5;
int father[maxn],Rank[maxn],num[maxn],N,M,cnt,n; //Rank数组表示x到father[x]的奇偶性
struct Edge { //结构体存区间顺序，va表示奇数还是偶数
    int x,y,va;
} edge[maxn];

int search(int x) { //二分快速查找x在num数组的顺序
    int left = 0,right = n;
    while(left+1 < right) {
        int mid = (left+right)>>1;
        if(num[mid] == x)
            return mid;
        if(num[mid] < x)
            left = mid;
        else 
            right = mid;
    }
    if(num[left] == x)
        return left;
    else 
        return right;
}

int query(int x) { //路径压缩
    if(x != father[x]) {
        int per = father[x];
        father[x] = query(father[x]);
        Rank[x] = (Rank[x] + Rank[per]) % 2;
    }
    return father[x];
}

int main() {
    scanf("%d%d",&N,&M);
    char str[20]; //字符数组最好开大一些，以免出现错误
    cnt = 0;
    for(int i = 0;i < M;i++) {
        scanf("%d%d%s",&edge[i].x,&edge[i].y,str);
        edge[i].x--;
        if(str[0] == 'e') //千万别把= 写成==，编译器也不会报错

            edge[i].va = 0;
        else 
            edge[i].va = 1;
        num[cnt++] = edge[i].x; //存入num数组离散化
        num[cnt++] = edge[i].y;
    }
    for(int i = 0;i <= cnt;i++) {
        father[i] = i;
        Rank[i] = 0;
    }
    sort(num,num+cnt);
    n = unique(num,num+cnt) - num; //unique函数的作用是去重，并且返回数组的迭代器，再减去数组num的地址就是新数组的长度
    /*for(int i = 0;i < n;i++)
        printf("%d ",num[i]);
    printf("\n");*/
    int i;
    for(i = 0;i < M;i++) {
        int nx = search(edge[i].x);
        int ny = search(edge[i].y);
        //printf("%d-%d %d-%d\n",edge[i].x,edge[i].y,nx,ny);
        int X = query(nx);
        int Y = query(ny);
        if(X == Y) {
           if((Rank[nx] + Rank[ny] + 2) % 2 != edge[i].va) { 
               printf("%d\n",i);
               break;
           }
        }
        else {
            father[Y] = X;
            Rank[Y] = (Rank[nx] - Rank[ny] + 2 + edge[i].va) % 2;
        }
        //printf("%d-%d ",edge[i].va,Rank[Y]);
    }
    if(i >= M)
        printf("%d\n",M);
}