題目

小?A?和小?B?在玩一個游戲。

首先，小?A?寫了一個由?0?和?1?組成的序列?S，長度為?N。

然后，小?B?向小?A?提出了?M?個問題。

在每個問題中，小?B?指定兩個數?l?和?r，小?A?回答?S[l～r]?中有奇數個?1?還是偶數個?1。

機智的小?B?發現小?A?有可能在撒謊。

例如，小?A?曾經回答過?S[1～3]?中有奇數個?1，S[4～6]?中有偶數個?1，現在又回答?S[1～6]?中有偶數個?1，顯然這是自相矛盾的。

請你幫助小?B?檢查這?M?個答案，并指出在至少多少個回答之后可以確定小?A?一定在撒謊。

即求出一個最小的?k，使得?01?序列?S?滿足第?1～k?個回答，但不滿足第?1～k+1?個回答。

輸入格式

第一行包含一個整數?N，表示?0101?序列長度。

第二行包含一個整數?M，表示問題數量。

接下來?M?行，每行包含一組問答：兩個整數?l?和?r，以及回答?even?或?odd，用以描述?S[l～r] 中有偶數個?1?還是奇數個?1。

輸出格式

輸出一個整數?k，表示?01 序列滿足第?1～k 個回答，但不滿足第?1～k+1 個回答，如果?01 序列滿足所有回答，則輸出問題總數量。

數據范圍

N≤10^9,M≤5000

思路

這道題與銀河英雄傳說思路是相似的。

我們可以想象為L到R的距離是奇數還是偶數（R為根節點）。

兩個集合合并的時候，使得其中一個集合S1的祖先節點排到另一個集合S2的末尾，S1中所有的點到根節點的距離加上S1祖先節點到S2祖先節點的距離%2。

代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
int n,m;
int p[N],d[N];
unordered_map<int,int> S;int get(int x)
{if(S.count(x) == 0) S[x] = ++n;return S[x];
}int find(int x)
{if(p[x] != x){int root = find(p[x]);d[x] ^= d[p[x]];p[x] = root;}return p[x];
}int main()
{cin >> n >> m;n = 0;for(int i = 0; i < N; i ++) p[i] = i;int res = m;for(int i = 1; i <= m; i ++){int a,b;string type;cin >> a >> b >> type;a = get(a - 1), b = get(b);int t = 0;if(type == "odd") t = 1;int pa = find(a),pb = find(b);if(pa == pb){if((d[a] ^ d[b] != t)){res = i - 1;break;}}else{p[pa] = pb;d[pa] = d[a] ^ d[b] ^ t;}}cout << res << endl;return 0;
}