【CEOI 1999】奇偶性游戏

Description

你偶尔和朋友玩如下的游戏。你的朋友写下一个由01组成的序列。你选择连续的一段子序列（例如，从第3到第5个数的子序列），问他这一段中1的个数是偶数还是奇数。你的朋友会回答你的问题，然后你可以问他另外一段子序列，等等。你的任务是猜出整个序列。
你怀疑你朋友的一些回答可能是错误的，并且你希望证明他说了假话。因此你决定写一个程序来帮助你。这个程序将会收到你的一系列问题以及你朋友给出的答案。程序的目标是找到第一个被证明是错误的回答，即，存在一个序列能满足之前所有回答，但加上这个回答后就不存在相应的序列。

Input

第一行有一个整数，代表01序列的长度。长度不超过1000000000。
第二行有一个正整数，代表询问和回答的数量。数量不超过5000.
接下来的若干行描述了所有的了询问和回答。每一行包含了一个询问和对此询问的回答：两个整数（所选择的子序列的起止点），一个单词“even”或“odd”（答案，即该子序列中1的个数的奇偶性），其中“even”代表有偶数个，“odd”代表有奇数个。

Output

输出一个整数X。它意味着：存在一个01序列满足前X个奇偶性询问，但不存在满足前X+1个奇偶性询问的序列。如果存在满足所有询问的序列，X就应该是询问的总数。

Sample Input

输入样例1：  


2 even  
4 odd  
6 even  
6 even  
10 odd 

输入样例2：  


2 even  
4 even  
4 odd  
10 even  
10 even  
2 even  

Sample Output

输出样例1：  
3  
输出样例2：  
5  

Hint

Source

CEOI 1999 Parity game
并查集

思路{

　　此题乃并查集大好题！！！！！！！！！！！！！！

　　数据有1000000000，肯定离散化。离散化后，顺着离散化的思路，就连边。

　　又要保证点的连通性，把区间左端点-1或右端点+1

　　随后，用并查集维护，合并2个端点，连双向边(由于之后要统计更大的区间)。

　　如果两个端点在一个集合内，爆搜判断即可(正确性显然！)

}

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<ctime>
 8 #include<cmath>
 9 #include<list>
10 #include<deque>
11 #include<stack>
12 #include<map>
13 #include<set>
14 #define RG register
15 #define LL long long
16 #define dd double
17 #define maxx 10001
18 using namespace std;
19 int fa[maxx],tong[maxx],tot;
20 map<int,int>m;
21 struct ed{
22 int nxt,to,c;
23 }e[maxx*10];int head[maxx];
24 int find(int x){if(fa[x]!=x)return fa[x]=find(fa[x]);return fa[x];}
25 void Insert(int x,int y){fa[find(x)]=fa[find(y)];}
26 LL L[(maxx/2)+1],R[(maxx/2)+1];int ww[(maxx/2)+1];
27 void add(int u,int v,int c){
28   e[tot].nxt=head[u];
29   e[tot].to=v;
30   e[tot].c=c;
31   head[u]=tot++;
32 }
33 int dfs(int s,int t,int faa,int num){
34   if(s==t)return num&1;
35   for(int i=head[s];i!=-1;i=e[i].nxt)if(e[i].to!=faa){
36       int kk=dfs(e[i].to,t,s,num^e[i].c);
37       if(kk!=-1)return kk;
38     }return -1;
39 }
40 int main(){
41   memset(head,-1,sizeof(head));
42   int n,mm;scanf("%d%d",&n,&mm);
43   for(int i=1;i<=mm;++i){
44     scanf("%lld%lld",&L[i],&R[i]);L[i]--;
45     char ch[12];scanf("%s",ch);
46     ww[i]=(ch[0]=='o');
47     tong[(i<<1)-1]=L[i],tong[(i<<1)]=R[i];
48   }sort(tong+1,tong+mm*2+1);int s=0;
49   for(int i=1;i<=2*mm;++i)if(tong[i]!=tong[i-1])m[tong[i]]=++s;
50   for(int i=1;i<=s;++i)fa[i]=i;
51   for(int i=1;i<=mm;++i){
52     int a=m[L[i]],b=m[R[i]],c=ww[i];
53     if(find(a)!=find(b))fa[find(a)]=fa[find(b)],add(a,b,c),add(b,a,c);
54     else if(dfs(a,b,a,0)!=c){cout<<i-1,exit(0);}
55   }cout<<mm;
56   return 0;
57 }