学步园

题意：

有一个长度为n，由0和1组成的序列，我们不清楚序列内容。现在给定m个描述，说明区间内1的个数的奇偶性；现在要求找出哪里出现第一个矛盾，输出这个矛盾之前的不矛盾描述个数。描述如下 a ,b,str，[a,b]表示区间，str表示奇偶性。

题解：

我们通过分析发现，出现矛盾的区间一定是区间描述出现两次以上的区间，例如样例中的[1,2],[3,4],[5,6]和[1,6]，使得[1,6]这个区间被描述两次。若没有描述两次以上那么必定不存在矛盾（why？因为没有描述两次以上，那么必定存在至少一个位置我们可以自由改变1或者0使得条件成立）。

之后就是将上述问题转换，我们用f[i]表示1~i段的奇偶性（0表示偶，1表示奇），那么[a,b]段的奇偶性可以表示为f[a-1]^f[b]，而由根据上述描述，我们可以将a-1和b加入并查集，之后只有在出现环的情况下才可能出现矛盾。

由于a和b的值可能很大，但种类至多10000种，所以可以用map离散化。之后我们用c[i]表示i到根这个区间的奇偶性（i为离散化后的值），之后我们就可以通过路径压缩使得求各点到根的奇偶性消耗时间大幅度降低。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;

const int maxn=1e4+10;
int f[maxn],c[maxn];
map<int,int>mm;
int findset(int x)
{
    if(f[x]!=x)
    {
        int t=findset(f[x]);
        c[x]=c[x]^c[f[x]];
        f[x]=t;
    }
    return f[x];
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i,j,k,m,t=0,a,b,x,y,xx,yy,flag=0,ans,num;
        char str[10];
        scanf("%d",&m);
        mm.clear();
        for(i=0;i<=2*m;i++)f[i]=i,c[i]=0;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%s",&a,&b,str);
            a--;
            if(flag)continue;

            if(strcmp(str,"even")==0)num=0;else num=1;

            if(mm[a]==0)x=mm[a]=++t;
            else x=mm[a];
            if(mm[b]==0)y=mm[b]=++t;
            else y=mm[b];
            xx=findset(x);
            yy=findset(y);
            if(xx==yy)
            {
                if((c[x]^c[y])!=num){flag=1;ans=i;}
            }
            else
            {
                f[xx]=yy;
                c[xx]=c[x]^c[y]^num;
            }
        }
        if(flag)printf("%d\n",ans);
        else printf("%d\n",m);
    }
    return 0;
}