POJ 1733 Parity game (路径压缩并查集+离散化)

Description

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

   有一个由0或1组成的长度为N的串，现在给你K条该串的信息如：

 表示连续字符区间[1，2]之间的字符有偶数个1。

        3 4 odd 表示连续字符区间[3，4]之间的字符有奇数个1。

        现在问你给的K条信息是否存在矛盾。假设存在矛盾且第一条矛盾信息为第i+1条，那么请输出i(即输出最大的前i条不矛盾的信息的这个最大i)。

分析:

        首先对于每个输入的区间[u,v]，我们把他改成(u-1，v]这个半开半闭的区间。然后令u-1和v做为并查集中的两个个节点。并查集每个节点维护下列信息：

        F[i]：表示i节点的父节点编号(父节点编号>i)。

        S[i]：表示i节点到其父节点的这个半开半闭区间(i，F[i]]内的1的个数(0表偶数个，1表奇数个)。

        通过findset(u)我们可以让u直接连在根节点下面，并且更新S[u]值表示(u，根]这个区间1的属性。

        如果u-1与v此时不在同一个分量中，那么我们可以知道(u-1，F[u-1]]区间和(v，F[v]]区间1的属性且我们知道(u-1，v]区间的1属性，那么我们可以推算出(F[u-1]，F[v]](假设F[u-1]<F[v])区间的属性，进而合并F[u-1]与F[v]的连通分量。注意：合并两个连通分量的时候，我们始终保持编号大的节点作为父亲，编号小的节点作为儿子(虽然下面的代码并没有遵照这个约定，因为就算随便合并也可以，但是需要验证较多情况)。

        至此，本题的并查集部分就完成了。

        由于只有5000条语句，但是却有最大a为10亿，我们并查集没必要去申请10亿的数组。所以我们将预先读入所有输入数据对(u，v，type)且存储(u-1，v，type)这种三元组，然后将所有的u-1和v排序重新从1到X编号(即用map重新映射到数轴上)。然后用上面分析的并查集处理即可。

        举例如下：

        原始输出为：[2 8] even [2 7] odd

        转换之后为：(1,8] even (1,7] odd

        重新映射之后为：(1,3] even (1,2] odd

        原来区间(7,8]之间为odd，现在同样区间(2,3]之间为odd。(2,3]区间不是指整数2到整数3之间而是代值第2个端点(值7)到到第3个端点(值8)之间为odd。 

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
const int INF = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
const int MAXN=10000+100;
int F[MAXN];
int S[MAXN];

int findset(int i)
{
    if(F[i]==-1)return i;
    int temp = findset(F[i]);
    S[i] =S[i]^S[F[i]];
    return F[i]=temp;
}
map<int ,int>mp;
int tot=0;
int insert(int x)
{
    if(mp.find(x)==mp.end())mp[x]=tot++;
    return mp[x];
}
int main()
{
    int n,m,k;
    while(scanf("%d",&n)==1)
    {
        memset(F,-1,sizeof(F));
        memset(S,0,sizeof(S));
        scanf("%d",&m);
        k=m;
        for(int i=0; i<m; i++)
        {
            int u,v;
            char str[10];
            scanf("%d%d%s",&u,&v,str);
            if(k<m)continue;
            u=insert(u-1);
            v=insert(v);
            int temp;
            if(str[0]=='e')//获取(u,v]之间的奇偶性
                temp=0;
            else if(str[0]=='o')
                temp=1;

            int fu=findset(u);
            int fv=findset(v);
            if(fu==fv)
            {
                int t = S[u]^S[v];
                if(t!=temp)
                    k=min(k,i);
            }
            else if(fu!=fv)
            {
                F[fu]=fv;
                S[fu]=S[u]^S[v]^temp;
            }
        }
        printf("%d\n",k);
    }
    return 0;
}