看篇国家论文
《从《parity》的解法谈程序优化》
对于区间i,j 如果用sum[i],sum[j]来表示到i的1的个数的奇偶性 那么仔细想下 sum[i-1] 若与区间i,j相等 则sum[j]为偶 否则为奇
那么就可以把性质相同的合并在一个集合里 性质相同为朋友 不同为敌人 可以把一个端点分成两个 一个是自己一个是他的敌人 当与别的点合并时根据朋友的朋友是朋友 朋友的敌人是敌人 敌人的敌人 是朋友 这些原则 来进行合并 ，并判断是不是有矛盾
端点比较大 用map离散化下 map相对其它离散化方法操作还是比较简单点
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<map>
using namespace std;
#define N 10010
map<int,int>q;//map进行离散化
int que[N];
struct node
{
int l,r,d;
}p[N];
int father[N<<];
int find(int x)
{
if(father[x]!=x)
{
father[x] = find(father[x]);
}
return father[x];
}
void union1(int x,int y)
{
int tx = find(x);
int ty = find(y);
if(tx!=ty)
father[tx] = ty;
}
int main()
{
int i,k,n,g=;
char cc[];
while(scanf("%d",&n)!=EOF)
{
if(n==-)
break;
q.clear();
g = ;
scanf("%d",&k);
for(i = ; i <= k ; i++)
{
scanf("%d%d%s",&p[i].l,&p[i].r,cc);
if(strcmp(cc,"even")==)
p[i].d = ;
else
p[i].d = ;
que[g++] = p[i].l;
que[g++] = p[i].r;
}
sort(que,que+g);
int o = ;
q[que[]] = o;
for(i = ; i < g ; i++)
{
if(que[i]!=que[i-])
{
o++;
q[que[i]] = o;
}
}
for(i = ; i <= o+N ; i++)
father[i] = i;
for(i = ; i <= k ; i++)
{
int tx = q[p[i].l]-;
int ty = q[p[i].r];
if(p[i].d)
{
if(find(tx)==find(ty))
{
printf("%d\n",i-);
break;
}
else
{
union1(tx,ty+N);//敌人的敌人是朋友
union1(tx+N,ty);
}
}
else
{
if(find(tx)==find(ty+N))
{
printf("%d\n",i-);
break;
}
else
{
union1(tx,ty);//朋友的朋友是朋友
union1(tx+N,ty+N);
}
}
}
if(i==k+)
printf("%d\n",k);
}
return ;
}