题目大意：有10E位数，每位上的数不是1就是0。现在给出第n位到第m位的1的数量的奇偶性，判断所给出的话有几句是对的
解题思路：有10E位数，，肯定要离散化处理 因为有可能给出的区间是左端点等于右端点的，所以每次都把左端点的值减去1再进行处理 给出了区间的奇偶性，就要找一下是否和前面的矛盾，如果该区间的左端点的根节点和右端点的根节点是相同的，那么就可以判断是否正确了 如果根节点不同，就进行合并，合并时要注意判断是谁的根节点比较大
using namespace std;#define maxn 10010int p[maxn], r[maxn], u[maxn], v[maxn], q[maxn], ans, n, M;map<int,int> m;int find(int x) {if(x == p[x])return x;int t = find(p[x]);r[x] = (r[x] + r[p[x]]) % 2;return p[x] = t;}void init() {scanf(“%d”, &M);char str[100];for(int i = 0; i < M; i++) {scanf(“, &u[i], &v[i], str);if(strcmp(str, “even”) == 0)q[i] = 0;elseq[i] = 1;}m.clear();int cnt = 1;for(int i = 0; i < M; i++) {if(!m[u[i] – 1])m[u[i] – 1] = cnt++;if(!m[v[i]])m[v[i]] = cnt++;}for(int i = 0; i < M; i++) {p[m[u[i] – 1]] = m[u[i] – 1];p[m[v[i]]] = m[v[i]];r[m[u[i] – 1]] = r[m[v[i]]] = 0;}}void solve() {ans = -1;for(int i = 0; i < M; i++) {int x = m[u[i] – 1];int y = m[v[i]];int xx = find(m[u[i] – 1]);int yy = find(m[v[i]]);if(xx == yy) {if((r[x] – r[y] + 2) % 2 != q[i]) {ans = i;return ;}}else if(xx < yy){p[xx] = yy;r[xx] = (r[y] + q[i] – r[x] + 2) % 2;}else {p[yy] = xx;r[yy] = (r[x] – r[y] – q[i] + 4) % 2;}}}int main() {while(scanf(“%d”, &n) == 1) {init();solve();if(ans == -1)printf(“%d\n”, M);elseprintf(“%d\n”, ans);}return 0;}
战胜困难，走出困境，成功就会属于你。
