題意是這樣，有一個(gè)01構(gòu)成的字符串，給出這樣一些論斷：[s,t]區(qū)間內(nèi)有奇數(shù)/偶數(shù)個(gè)1，問(wèn)第一個(gè)不合法的論斷是什么。
首先如果某個(gè)論斷不合法肯定是這樣的情況
[i,k]^[k,j] != [i,j]，也就是說(shuō)若干個(gè)區(qū)間二進(jìn)制+的結(jié)果不滿足區(qū)間和的結(jié)果。
由于連接是在區(qū)間的端點(diǎn)，就可以用并查集，如原區(qū)間是[i,j]，處理為[i,j+1)，目的是為了和下個(gè)區(qū)間能夠接上。
接著用并查集維護(hù)路徑，路徑記錄的是從該節(jié)點(diǎn)到根節(jié)點(diǎn)區(qū)間有奇數(shù)/偶數(shù)個(gè)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