离散化+带权并查集
题意：长度为n的0和1组成的字符串，然后问第L和R位置之间有奇数个1还是偶数个1. 根据这些回答， 判断第几个是错误（和之前有矛盾）的。
思路：此题同HDU 3038 差不多，询问L~R之间的1的奇偶性，相当于HDU 3038 的L~R之间的和。所以合并的时候，合并L-1和R(L-1为父亲)。 则R相对L-1的权值(不包括L-1)即为L~R之间1的个数(0代表有偶数个1,1代表有奇数个1).
之所以为什么合并的是L-1和R，举个例子： 1 2 even 3 4 odd 首先合并0、2，2相对0的权值为0，接着合并2、4,4相对2的权值为1。 那么之后在查找4的根节点时，会更新4与根节点的关系，则4相对0的权值为：（4相对2的权值+2相对0的权值）%2，也可以用异或来更新。 因为权值不包括父节点在内(即4相对2的不包括2,2相对0的不包括0)，所以结果就是1、2、3、4中1的个数的奇偶性。
每次读取数据时，先查找L-1和R的根节点。
1：如果相等，均为f，则判断L~R的1的奇偶是否与数据c相同，即(val[L-1]-val[R]+2)%2是否等于c，也可以用异或val[L-1]^val[R];
2：如果不同，则合并。L-1的根节点为fx，R的根节点为fy，则fy相对fx的权值val[fy]=(c+val[L-1]-val[R]+2)%2, 或者val[fy]=c^val[L-1]^val[R].
当找到矛盾时，直接退出即可，接下来的数据不需要管它。
由于n的数据很大，10亿，但查询只有5000次，也就是最多出现1万个数，因此采用离散化，不影响结果。
附两种离散的方法：
1：用map建立映射
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map> /*
125ms
*/
using namespace std;
const int maxn=;
int father[maxn];
int val[maxn]; //val[i]表示i相对根节点的权值
int n,m;
map<int,int> hash_idx; void init(){
for(int i=;i<maxn;i++){
father[i]=i;
val[i]=;
}
} int find_root(int x){
if(father[x]==x)
return x;
int tmp=father[x];
father[x]=find_root(father[x]);
val[x]=val[x]^val[tmp];
return father[x];
}
void Union(int x,int y){
father[y]=x;
}
int main()
{
int a,b,c,add,x,y,fx,fy,i;
char str[];
scanf("%d",&n);
scanf("%d",&m);
init();
add=;
for(i=;i<=m;i++){
scanf("%d%d%s",&a,&b,str);
if(str[]=='o')
c=;
else
c=;
a--;
//用map来离散化，如果map中还不存在关于a、b的映射，则新建映射
if(hash_idx.find(a)==hash_idx.end()){
hash_idx[a]=add++;
}
if(hash_idx.find(b)==hash_idx.end()){
hash_idx[b]=add++;
}
x=hash_idx[a];
y=hash_idx[b];
fx=find_root(x);
fy=find_root(y);
if(fx==fy){
if((val[x]^val[y])!=c){
break;
}
}
else{
Union(fx,fy);
val[fy]=val[x]^val[y]^c;
}
}
printf("%d\n",i-);
return ;
}
2.用邻接表离散
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map> /*
47ms
*/
using namespace std;
const int maxn=;
const int mod=;
int father[maxn];
int val[maxn]; //val[i]表示i相对根节点的权值
int n,m,cnt;
int head[maxn]; struct Node{
int u; //即点的编号
int next;
}e[maxn]; //用邻接表来离散化，x的映射即为边的编号cnt。
int get_hash(int x){
int h=x%mod,i;
for(i=head[h];i!=-;i=e[i].next){
if(e[i].u==x)
return i;
}
e[cnt].next=head[h];
e[cnt].u=x;
head[h]=cnt++;
return cnt-;
} void init(){
cnt=;
memset(head,-,sizeof(head));
for(int i=;i<maxn;i++){
father[i]=i;
val[i]=;
}
} int find_root(int x){
if(father[x]==x)
return x;
int tmp=father[x];
father[x]=find_root(father[x]);
val[x]=val[x]^val[tmp];
return father[x];
}
void Union(int x,int y){
father[y]=x;
}
int main()
{
int a,b,c,x,y,fx,fy,i;
char str[];
scanf("%d",&n);
scanf("%d",&m);
init();
for(i=;i<=m;i++){
scanf("%d%d%s",&a,&b,str);
if(str[]=='o')
c=;
else
c=;
a--;
//获取相应的映射，即离散的值
x=get_hash(a);
y=get_hash(b);
fx=find_root(x);
fy=find_root(y);
if(fx==fy){
if((val[x]^val[y])!=c){
break;
}
}
else{
Union(fx,fy);
val[fy]=val[x]^val[y]^c;
}
}
printf("%d\n",i-);
return ;
}