学步园

题意：给出一个01串的长度n,(1~10000000)，和m对二元组，每个二元组后面跟even或者odd，表示该二元组里面的1的个数为奇数或者偶数，问最早出现错误的二元组的下标，错误即为，满足前面条件的，但不满足当前的条件的。

很明显看出是并查集，而且n的范围远大于m，可以先离散化处理每个二元组的下标，然后在按照普通并查集那样处理就行了。我遇到一个坑自己的地方，即开始初始化father数组是用for（1～n）fa[i] = i;，但是很明显因为超出fa数组的大小，re掉了。解决方法是memset（fa, -1, sizeof(fa) ）;（个人写法问题- -）

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 20010;

int rk[N], t[N], fa[N];
int n, m;
struct node{
	int l, r;
	int x;
}a[N];
int tot;

int bch( int x )
{
	int l = 1, r = tot;
	int mid;
	while( l <= r )
	{
		int mid = ( l + r ) >> 1;
		if( t[mid] == x )
			return mid;
		else if( t[mid] > x )
			r = mid - 1;
		else
			l = mid + 1;
	}
}

int dfs( int x )
{
	if( fa[x] == -1 )
		return x;
	int xx = fa[x];
	fa[x] = dfs( xx );
	rk[x] ^= rk[xx];
	return fa[x];
}

int main()
{
	while( ~scanf("%d%d", &n, &m) )
	{
		memset( fa, -1, sizeof( fa ) );
		char op[10];
		tot = 0;
		for( int i = 1; i <= m; ++i )
		{
			scanf("%d%d%s", &a[i].l, &a[i].r, op);
			--a[i].l;
			if( op[0] == 'e' )
				a[i].x = 0;
			else
				a[i].x = 1;
			t[++tot] = a[i].l;
			t[++tot] = a[i].r;
		}
		sort( t+1, t+1+tot );
		tot = unique( t+1, t+1+tot ) - t - 1;
		int ans = 0;
		for( int i = 1; i <= m; ++i )
		{
			int l = bch( a[i].l );
			int r = bch( a[i].r );
			int z = dfs( l );
			int x = dfs( r );
			if( z == x )
			{
				if( (rk[l] ^ rk[r]) != a[i].x )
					break;
				ans++;
			}
			else
			{
				if( z < x )
				{
					fa[x] = z;
					rk[x] = rk[r] ^ a[i].x ^ rk[l];
				}
				else
				{
					fa[z] = x;
					rk[z] = rk[l] ^ a[i].x ^ rk[r];
				}
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}