题目: http://poj.org/problem?id=1733
题意: 输入n表示有一个长度为n的0,1字符串, m表示接下来有m行输入, 接下来的m行输入中x, y, even表示第x到第y个字符中间1的个数为偶数个, x, y, odd表示第x到第y个字符中间1的个数为奇数个, 若m句话中第k+1是第一次与前面的话矛盾, 输出k;
Sample Input
10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd
Sample Output
3
解题参考：https://www.cnblogs.com/geloutingyu/p/6129590.html
思路: 若x, y之间（ [ x ，y ] ）1的个数为偶数个,
那么1~(x-1) 与1~y 中1的个数同奇偶性, 反之则异奇偶性, 我们可以将其理解为若输入x, y, even, 即(x-1), y属于同种, 反之则属于不同种,
种类并查集 + 离散化
注意点：
1. x-1 与 y
2. 数据范围：n ≤ 1e9 ， 故查的时候不能直接就用数组下标。 下面用c语言代码+hash 写出， 不直接用c++的map。
以下为c语言代码：
1 #include <stdio.h> 2 #include <string.h> 3 #define maxn 5010 4 #define Mod 149993 5 int hash[Mod], Map[Mod], Rank[2*maxn], prev[2*maxn]; 6 // Rank[i] = ? (两种情况, 要么 1~i 中有奇数个1(Rank[i]=1表示), 要么 1~i 中为偶数个1(Rank[i]=0表示)) 7 8 // hash一个数据x的位置 9 int locate(int x) { 10 int i = 0, w = x % Mod; 11 while (i < Mod && hash[(w+i) % Mod] != 0 && hash[(w+i) % Mod] != x) { 12 i++; 13 } 14 return (w+i) % Mod; 15 } 16 17 // 初始化 18 void init() { 19 memset(hash, 0, sizeof(hash)); 20 for (int i = 0; i < maxn; i++) { 21 Rank[i] = 0; 22 prev[i] = i; 23 } 24 } 25 26 int join(int x, int y, int judge) { 27 int fx = find(x); 28 int fy = find(y); 29 if (fx == fy) { 30 if (Rank[x] ^ Rank[y] == judge) return 0; // if((Rank[x] + Rank[y]) % 2 == judge) 31 else return 1; 32 } 33 else { 34 prev[fy] = fx; 35 Rank[fy] = (Rank[x] + Rank[y] + judge) % 2; // Rank[fy]=(Rank[x]+Rank[y]+d+Rank[fx]+Rank[fy])%2;这里 Rank[fx]=0, Rank[fy]=0, 故可省去 36 } 37 return 0; 38 } 39 40 int find(int x) { 41 if (x != prev[x]) { 42 int px = find(prev[x]); 43 Rank[x] = Rank[x] ^ Rank[prev[x]]; // Rank[x] = (Rank[x] + Rank[prev[x]]) % 2; 44 prev[x] = px; 45 } 46 return prev[x]; 47 } 48 49 int main() { 50 int n, m, gg = 0, count = 1; 51 scanf("%d%d", &n, &m); 52 init(); 53 for (int i = 1; i <= m; i++) { 54 int x, y, judge; 55 char str[10]; 56 scanf("%d%d%s", &x, &y, str); 57 x--; // x-1; 58 int px = locate(x), py = locate(y); 59 if (hash[px] != x) { 60 hash[px] = x; 61 Map[px] = count++; 62 } 63 if (hash[py] != y) { 64 hash[py] = y; 65 Map[py] = count++; 66 } 67 if (!strcmp("even", str)) { 68 judge = 0; 69 } 70 else { 71 judge = 1; 72 } 73 if (join(Map[px], Map[py], judge) && !gg) { 74 gg = i; 75 } 76 } 77 if (!gg) { 78 gg = m+1; 79 } 80 printf("%d\n", gg-1); 81 return 0; 82 }
原文：https://www.cnblogs.com/y2ek/p/12650803.html