POJ 1733 Parity game（种类并查集）

http://poj.org/problem?id=1733

题意：

给出一个01串，有多次询问，每次回答[l,r]这个区间内1的个数的奇偶性，但是其中有一些回答是错误的，问到第几个回答时与前面的回答是有矛盾的。

思路：

任意一个区间要么是奇要么就是偶。所有就可以用种类并查集来解决。

因为是区间，所以如果要连起来的话，每个区间的左端点需要减1。

因为n很大但是询问少，所有需要离散化处理。

下面的代码中，1表示奇，0表示偶。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int maxn = *;

 int n,q,tot;

 int p[maxn],re[maxn],a[maxn];  //0表示偶，1表示奇

 struct node

 {

     int l, r;

     char s[];

 }query[maxn];

 int finds(int x)

 {

     if(p[x]==x)  return x;

     int tmp = p[x];

     p[x] = finds(p[x]);

     re[x] = (re[x]+re[tmp])%;

     return p[x];

 }

 void unions(int l,int r,int x, int y,int tmp)

 {

     if(x<y)

     {

         p[x] = y;

         re[x] = (re[r]-re[l]+tmp+)%;

     }

     else

     {

         p[y] = x;

         re[y] = (re[l] - re[r]-tmp+)%;

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     tot = ;

     scanf("%d%d",&n,&q);

     for(int i=;i<=maxn;i++)  {p[i] = i;re[i]=;}

     for(int i=;i<=q;i++)

     {

         scanf("%d%d%s",&query[i].l,&query[i].r,query[i].s);

         query[i].l--;

         a[++tot] = query[i].l;

         a[++tot] = query[i].r;

     }

     sort(a+,a+tot+);

     int num = unique(a+,a+tot+)-(a+);

     int i;

     for(i=;i<=q;i++)

     {

         int l = lower_bound(a+,a+num+,query[i].l)-(a+);

         int r = lower_bound(a+,a+num+,query[i].r)-(a+);

         int x = finds(l);

         int y = finds(r);

         int tmp = ;

         if(query[i].s[]=='o')   tmp = ;

         if(x==y)

         {

             if((re[l]-re[r]+)%!=tmp)  break;

         }

         else

         {

             unions(l,r,x,y,tmp);

         }

     }

     printf("%d\n",i-);

     return ;

 }