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 ;
}
05-11 13:14