思路: 带权并查集

分析:

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
    
     #include
     
      #include
      
       #include
       
        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;}