题目链接：http://poj.org/problem?id=1733

题意：给出一个01串然后给出一系列问题，问最多到哪位置问题出错了

这题和hdu3038类似思路也是差不多的 

 #include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#include <cmath>using namespace std;struct TnT {    int l , r;    char cp[10];}T[10010];int l , q , m[10010] , c[10010] , f[10010] , root[10010];void init() {    for(int i = 0 ; i <= q * 2 ; i++) {        f[i] = i , root[i] = 0;    }}int find(int x) {    if(x == f[x])        return x;    int tmp = find(f[x]);    root[x] = (root[x] + root[f[x]] + 2) % 2;    return f[x] = tmp;}int main() {    while(scanf("%d" , &l) != EOF) {        scanf("%d" , &q);        int count = 0 , cnt = 0 , flag;        for(int i = 1 ; i <= q ; i++) {            scanf("%d%d%s" , &T[i].l , &T[i].r , T[i].cp);            m[count++] = T[i].l , m[count++] = T[i].r;        }        sort(m , m + count);        for(int i = 0 ; i < count ; i++) {            if(i == 0) {                c[cnt++] = m[i];            }            else {                if(m[i] != m[i - 1]) {                    c[cnt++] = m[i];                }            }        }        int ans = q;        init();        for(int i = 1 ; i <= q ; i++) {            int x = upper_bound(c , c + cnt , T[i].l) - c , y = upper_bound(c , c + cnt , T[i].r) - c;            x--;            int a = find(x) , b = find(y);            if(T[i].cp[0] == ‘e‘)                flag = 0;            else {                flag = 1;            }            if(a == b) {                if(abs(root[x] - root[y]) != flag) {                    ans = i - 1;                    break;                }            }            else {                f[a] = b;                root[a] = (root[y] - root[x] + flag + 2) % 2;            }        }        printf("%d\n" , ans);    }    return 0;}

poj 1733 Parity game（带权并查集）