记录编号	465609	评测结果	AAAAAAAAAA
题目名称	[CEOI 1999] 奇偶性游戏	最终得分	100
用户昵称	hzoi_xx	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2017-10-27 15:36:05	内存使用	0.58 MiB

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <map>
# define N 10005
using namespace std;
struct qst{
	int l,r,op;
}Q[N];
int n,q,idx,Hash[N<<1],ans,f[N],bf[N];
map<int,int> mp;
char ch[5];
# define read(x){\
	x=0;char ch=getchar();\
	while(ch<'0'|ch>'9') ch=getchar();\
	while(ch>='0'&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}\
}
inline int find(int x,int &k){
	if(f[x]==-1){k=0;return x;}
	f[x]=find(f[x],k);
	k=(bf[x]^=k);//统计一的个数;
	return f[x];
}//并查集路径压缩;
void work(){
	int fa,fb,ka,kb;
	for(int i=1;i<=q;++i){
		fa=find(Q[i].l,ka);
		fb=find(Q[i].r,kb);
		if(fa!=fb){
			f[fa]=fb;
			bf[fa]=Q[i].op^ka^kb;
		}
		else{
			if(ka^kb!=Q[i].op){
				printf("%d\n",i-1);
				return;
			}
		}//并查集;
	}
	printf("%d\n",q);
}
int main(){
	freopen("parity.in","r",stdin);
	freopen("parity.out","w",stdout);
	read(n);read(q);
	for(int i=1;i<=q;++i){
		read(Q[i].l);read(Q[i].r);
		scanf("%s",ch+1);
		Q[i].op=(ch[1]=='e'?0:1);
		Hash[i<<1]=Q[i].l-1,Hash[(i<<1)-1]=Q[i].r;
	}
	sort(Hash+1,Hash+(q<<1)+1);
	int sz=unique(Hash+1,Hash+(q<<1)+1)-Hash-1;
	for(int i=1;i<=sz;++i) mp[Hash[i]]=++idx,f[i]=-1;
	for(int i=1;i<=q;++i){
		Q[i].l=mp[Q[i].l-1],Q[i].r=mp[Q[i].r];
	}//Hash散列;
	work();
	return 0;
}