POJ-1733 Parity game（带权并查集区间合并）

题目描述

　　你和你的朋友玩一个游戏。你的朋友写下来一连串的0或者1。你选择一个连续的子序列然后问他，这个子序列包含1的个数是奇数还是偶数。你的朋友回答完你的问题，接着你问下一个问题。

　　你怀疑你朋友的一些答案可能是错误的，你决定写一个程序来帮忙。程序将接受一系列你的问题及你朋友的回答，程序的目的是找到第一个错误的回答i，也就是存在一个序列满足前i-1个问题的答案，但是不满足前i个问题。

输入

　　第一行有一个整数L（L<=1000000000）,是这个01序列的长度。第二行是一个整数N(N<=5000),是问题及其答案的数目,接下来N行描述问题和答案。每一行包含一个问题和这个问题的答案：两个整数（子序列的起始位置和结束位置）和一个单词‘even’或者‘odd’,‘even’表示这个子序列中的‘1’的个数是偶数，‘odd’则表示是奇数。

输出

　　输出一行一个整数X。表示存在一个01序列满足前面的X个问题，但是不存在一个01序列满足前X+1个问题，如果存在一个序列满足所有问题，则输出N。

样例输入

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

样例输出

数据范围：

序列长度L<=1000000000,询问及回答数N<=5000

给你几个区间的范围以及里面1的个数是奇数还是偶数，然后让你求前多少个描述是对的。

还是区间问题，找和之前的有矛盾的，想到了带权并查集

若[a,b]中出现了偶数个1，则表示[0,a-1]和[0,b]的1的奇偶性相同。
若[a,b]中出现了奇数个1，则表示[0,a-1]和[0,b]的1的奇偶性不同。

因为题目给的数的范围特别大，不得不离散化，这里采用map的方式来离散化。

map离散化是指，比如1~10000，如果采用传统方式，明显是1和10000合并，但是离散化之后，用1代表1，2代表10000，1和2的合并便取代了1和10000的合并。

采用map离散化，将原始值作为key，便能实现快速查找判断是否出现过。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18 
19 int fa[10010];
20 int sum[10010];//sum[i]表示[fa[i],i]区间1的个数的奇偶性，0表示偶数，1表示奇数
21 map<int,int> mp;
22 
23 void init()
24 {
25     mp.clear();
26     memset(sum,0,sizeof(sum));
27     for(int i=1;i<=10005;i++) //注意这里因为是离散过后的，故不是<=n 
28         fa[i]=i;
29 }
30 int Find(int x)
31 {
32     if(x!=fa[x])
33     {
34         int t=fa[x];
35         fa[x]=Find(fa[x]);
36         sum[x]^=sum[t];
37     }
38     return fa[x];
39 }
40 
41 int main()
42 {
43     #ifdef DEBUG
44     freopen("sample.txt","r",stdin);
45     #endif
46 //    ios_base::sync_with_stdio(false);
47 //    cin.tie(NULL);
48     
49     int n,k;
50     scanf("%d %d",&n,&k);
51     init();
52     int ans=k;
53     int cnt=0;//离散化的新序号 
54     int l,r;
55     char op[5];
56     for(int i=1;i<=k;i++)
57     {
58         scanf("%d %d %s",&l,&r,op);
59         if(!mp.count(l-1))//离散化 
60         {
61             mp[l-1]=++cnt;
62         }
63         if(!mp.count(r))//离散化 
64         {
65             mp[r]=++cnt;
66         }
67         int flag;
68         if(op[0]=='e') flag=0;
69         else flag=1;
70         int x=Find(mp[l-1]);
71         int y=Find(mp[r]);
72         if(x!=y) 
73         {
74             fa[y]=x;
75             sum[y]=sum[mp[l-1]]^sum[mp[r]]^flag;
76         }
77         else if(sum[mp[l-1]]^flag!=sum[mp[r]])
78         {
79             ans=i-1;
80             break;
81         }
82     }
83     printf("%d
",ans);
84     
85     return 0;
86 }