题意是这样，有一个01构成的字符串，给出这样一些论断：[s,t]区间内有奇数/偶数个1，问第一个不合法的论断是什么。
首先如果某个论断不合法肯定是这样的情况
[i,k]^[k,j] != [i,j]，也就是说若干个区间二进制+的结果不满足区间和的结果。
由于连接是在区间的端点，就可以用并查集，如原区间是[i,j]，处理为[i,j+1)，目的是为了和下个区间能够接上。
接着用并查集维护路径，路径记录的是从该节点到根节点区间有奇数/偶数个1。
1 # include <cstdio>
2 # include <map>
3 using namespace std;
4 int arr[10001];
5 bool type[10001];
6 bool find(int pos,int &ans)
7 {
8 if(arr[pos]==pos)
9 {
10 ans=pos;
11 return 0;
12 }
13 else
14 {
15 bool t=find(arr[pos],ans);
16 type[pos]=(t^type[pos]);
17 arr[pos]=ans;
18 return type[pos];
19 }
20 }
21 int find(int pos)
22 {
23 int ans=0;
24 find(pos,ans);
25 return ans;
26 }
27 struct node
28 {
29 int a,b;
30 bool type;
31 }data[10001];
32 int main()
33 {
34 int len,num;
35 map<int,int>refer;
36 scanf("%d",&len);
37 scanf("%d",&num);
38 for(int i=0;i<num;i++)
39 {
40 char t[10];
41 scanf("%d%d%s",&data[i].a,&data[i].b,t);
42 if(data[i].a>data[i].b)
43 {
44 int tmp=data[i].a;
45 data[i].a=data[i].b;
46 data[i].b=tmp;
47 }
48 data[i].type=(t[0]=='o');
49 refer[data[i].a]=0;
50 refer[data[i].b+1]=0;
51 }
52 for(int i=0;i<refer.size();i++)
53 arr[i]=i,type[i]=0;
54 int c=0;
55 for(map<int,int>::iterator it=refer.begin();it!=refer.end();it++)
56 it->second=c++;
57 for(int i=0;i<num;i++)
58 {
59 data[i].a=refer[data[i].a];
60 data[i].b=refer[data[i].b+1];
61 if(find(data[i].a)==find(data[i].b))
62 {
63 if(data[i].type==(type[data[i].a]^type[data[i].b])) continue;
64 else
65 {
66 printf("%d\n",i);
67 goto exit;
68 }
69 }
70 else
71 {
72 data[i].type=(data[i].type^type[data[i].a]^type[data[i].b]);
73 type[find(data[i].a)]=data[i].type;
74 arr[find(data[i].a)]=find(data[i].b);
75 }
76 }
77 printf("%d\n",num);
78 exit:;
79 return 0;
80 }
81