经典的并查集+数据离散化如果不懂离散化的可以看看笔者的博客https://blog.csdn.net/nuoyanli/article/details/86551295希望对读者有帮助

Now and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) and ask him, whether this subsequence contains even or odd number of ones. Your friend answers your question and you can ask him about another subsequence and so on. Your task is to guess the entire sequence of numbers. 

You suspect some of your friend's answers may not be correct and you want to convict him of falsehood. Thus you have decided to write a program to help you in this matter. The program will receive a series of your questions together with the answers you have received from your friend. The aim of this program is to find the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer.

Input

The first line of input contains one number, which is the length of the sequence of zeroes and ones. This length is less or equal to 1000000000. In the second line, there is one positive integer which is the number of questions asked and answers to them. The number of questions and answers is less or equal to 5000. The remaining lines specify questions and answers. Each line contains one question and the answer to this question: two integers (the position of the first and last digit in the chosen subsequence) and one word which is either `even' or `odd' (the answer, i.e. the parity of the number of ones in the chosen subsequence, where `even' means an even number of ones and `odd' means an odd number).

Output

There is only one line in output containing one integer X. Number X says that there exists a sequence of zeroes and ones satisfying first X parity conditions, but there exists none satisfying X+1 conditions. If there exists a sequence of zeroes and ones satisfying all the given conditions, then number X should be the number of all the questions asked.

Sample Input

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

Sample Output

3

首先这题的区间长度1e9，但是整个询问只有5000个，所以可以对坐标进行离散化，用一个temp数组存下坐标，最后排序去重。剩下的就是对这些坐标进行并查集操作。

由于题目只给了区间1个数的奇偶性，我们可以用一个rel数组代表从这个结点到它的根结点这个区间中1个数的奇偶性，那么当左右端点的根节点相同时，我们就可以开始进行判断，rel[r]^rel[l]就会等于整个区间的奇偶性(0为偶，1为奇）。由于是给出整个闭区间l，r的1奇偶性，所以让l--。那么最终结果rel[r]^rel[l]就可以代表整个闭区间的奇偶性。其它细节看图&&看代码注释。

（字有点丑，逃.......）

 详细请结合代码理解：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define mm(a,n) memset(a,n,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define erp(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
#define N 10010
int pre[N],rel[N],temp[N],l[N],r[N],cnt;//pre:根节点; rel:到根节点的奇偶关系
bool oe[N];
int Find_ls(int x)// 查询坐标在离散后的位置
{
    return lower_bound(temp,temp+cnt,x)-temp;
}
int Find(int x)
{
    if (pre[x]==x)
        return x;
    int tmp=pre[x];
    pre[x]=Find(pre[x]);// 更新x和根结点的关系
    rel[x]^=rel[tmp];// 例如原本是A->B，现在是A->B->C
    return pre[x];// rel[A](A->C) = rel[A](A->B)^rel[B](B->C) 奇偶性相同就是0，不同就是1.用异或刚好满足这个条件
}
void init()
{
    rep(i,0,cnt)pre[i] = i, rel[i] = 0;
}
int main()
{
    int m,n,a,b;
//    freopen("C:\\Users\\nuoyanli\\Desktop\\acminput.txt","r",stdin);
    while (~scanf("%d",&m))
    {
        cnt=0;
        char s[5];
        scanf("%d",&n);
        rep(i,0,n-1)// l、r数组存查询区间
        {
            scanf("%d%d%s",&a,&b,s);
            l[i]=--a;
            r[i]=b;
            oe[i] = (s[0]=='o');
            temp[cnt++]=a;
            temp[cnt++]=b;
        }
        sort(temp,temp+cnt);
        cnt = unique(temp,temp+cnt)-temp;// 坐标离散化(去重)
        init();
        int ans = 0;
        rep(i,0,n-1)
        {
            int a=Find_ls(l[i]),b=Find_ls(r[i]);
            int fa=Find(a),fb=Find(b);
            if (fa==fb)
            {
                if ((rel[a]^rel[b])!= oe[i])// 如果根结点相同，进入判断
                    break;
                ans++;
            }
            else
            {
                if (oe[i])// 如果区间是奇数
                {
                    pre[fa]=fb;
                    rel[fa]=rel[a]^rel[b]^1;// 这里的更新可以具体假设rel的关系，按我上图推发现就是这样
                }
                else
                {
                    pre[fa]=fb;
                    rel[fa]=rel[a]^rel[b];// 理由同上
                }
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

由于笔者能力有限，如有问题欢迎评论区指出。