HDU1733 Parity game(带权并查集)

描述

传送门：我是传送门

有一个长度为n的序列
给出Q条限制 $l, r, s t r s t r == o d d$

输入

第一行一个 $n (n <= 10^{9})$

输出

输出一个数表示答案

样例

输入

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

输出

3

思路

这道题跟HDU3030差不太多，区别就是这道题的范围有些大，需要进行离散化。

照着HDU3038写了大半天，但是却一直WA，看了focus_best大佬的题解发现要用编号大的结点作为父亲···另外是使用map来辅助离散化

用map来离散化我是学到了，也找到了自己WA的原因，但是我还是不懂为什么要用编号大的结点来作为父亲。。。

具体题解还是看上边的博客吧，写的特别好

代码

  1 /*
  2  * =============================================
  3  *
  4  *       Filename:  H.cpp
  5  *
  6  *           Link:  http://poj.org/problem?id=1733
  7  *
  8  *        Version:  1.0
  9  *        Created:  2018/09/23 23时40分47秒
 10  *       Revision:  none
 11  *       Compiler:  g++
 12  *
 13  *         Author:  杜宁元 (https://duny31030.top/), duny31030@126.com
 14  *   Organization:  QLU_浪在ACM
 15  *
 16  * ==============================================
 17  */
 18 #include<cstdio>
 19 #include<iostream>
 20 #include<cstring>
 21 #include<algorithm>
 22 #include <map>
 23 using namespace std;
 24 #define clr(a, x) memset(a, x, sizeof(a))
 25 #define rep(i,a,n) for(int i=a;i<=n;i++)
 26 #define pre(i,a,n) for(int i=n;i>=a;i--)
 27 #define ll long long
 28 #define max3(a,b,c) fmax(a,fmax(b,c))
 29 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 30 const double eps = 1e-6;
 31 const int INF = 0x3f3f3f3f;
 32 const int mod = 1e9 + 7;
 33 const int MAXN = 5e4+10;
 34 
 35 map<int,int> f;
 36 map<int,int> pp;
 37 
 38 int find(int x)
 39 {
 40     int t = f[x];
 41     if(x != f[x])
 42     {
 43         f[x] = find(f[x]);
 44         pp[x] = (pp[x]+pp[t])%2;
 45     }
 46     return f[x];
 47 }
 48 
 49 int main()
 50 {
 51     ios
 52 #ifdef ONLINE_JUDGE 
 53 #else 
 54         freopen("in.txt","r",stdin);
 55     // freopen("out.txt","w",stdout); 
 56 #endif
 57     int n,q,x,y;
 58     char op[10];
 59     int pr = -1;
 60     scanf("%d %d",&n,&q);
 61     rep(i,1,q)
 62     {
 63         scanf("%d %d %s",&x,&y,op);
 64         if(pr != -1)
 65             continue;
 66         x--;
 67         if(!f.count(x))
 68         {
 69             f[x] = x;
 70             pp[x] = 0;
 71         }
 72         if(!f.count(y))
 73         {
 74             f[y] = y;
 75             pp[y] = 0;
 76         }
 77         int fx = find(x);
 78         int fy = find(y);
 79         // printf("fx = %d fy = %d
",fx,fy);
 80         if(fx == fy)
 81         {
 82             if(pp[x] == pp[y] && op[0] == 'e')
 83                 continue;
 84             else 
 85                 if(pp[x] != pp[y] && op[0] == 'o')
 86                     continue;
 87                 else 
 88                     pr = i-1;
 89         }
 90         else 
 91         {
 92             // printf("f[%d] = %d
",fx,fy);
 93             f[fx] = fy;
 94             if(op[0] == 'o')
 95                 pp[fx] = (pp[x]+pp[y]+1)%2;
 96             else 
 97                 pp[fx] = (pp[x]+pp[y])%2;
 98         }
 99     }
100     if(pr == -1)
101         printf("%d
",q);
102     else 
103         printf("%d
",pr);
104     fclose(stdin);
105     // fclose(stdout);
106     return 0;
107 }