POJ 1733 离散化 + 并查集

发表于 分类于 阅读次数：

将数据离散化后，就是经典的判断区间和是否正确的带权并查集。

题意

现在告诉你很多段区间的和的奇偶情况， 问到哪一句就不正确了。

思路

由于区间长度很大，但是区间段数很少，所以需要先离散化一下，然后维护每个端点到他所在根节点的权值，也就是到根节点所在端点的奇偶情况，当询问L，R时， 我们就判断val[L - 1] - val[R] 的奇偶情况是不是与输入的相符即可。

注意输入字符串用char，不要用string，不是一般的超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)

using namespace std;
//#define inf 0x3f3f3f3f
typedef long long ll;
const int maxn= 300005;
const int inf = 0x3f3f3f3f;
int f[maxn], val[maxn];
int a[maxn],b[maxn], l[maxn],r[maxn];

int find(int x)
{
    if(x != f[x])
    {
        int t = f[x];
        f[x] = find(f[x]);
        val[x] = (val[t] + val[x]) % 2;
    }
    return f[x];

}

char s[10005][8];

int vis[2005];
int main()
{
   int num,m;
   scanf("%d",&num);
   scanf("%d",&m);
   int tot = 0;
   for(int i = 1; i <= m; ++i)
   {
       scanf("%d %d",&l[i],&r[i]);
       b[++tot] = l[i];
       b[++tot] = r[i];
       scanf("%s",s[i]);
   }
   sort(b + 1, b + tot + 1);
   int N = unique(b + 1, b + tot + 1) -b -1;
   int t = N;
   for(int i = 1;  i < t; ++i)
   {
       if(b[i + 1] - b[i] > 1)
        b[++N] = b[i] + 1;
   }
    for(int i = 0; i <= N; ++i)
   {
       f[i] = i;
       val[i] = 0;
   }
   int aa, bb;
   sort(b + 1, b + N + 1);
   int index = inf;
   for(int i = 1; i <= m; ++i)
    {
        int ll = lower_bound(b + 1, b + N + 1, l[i]) - b;
        int rr = lower_bound(b + 1, b + N + 1, r[i]) - b;
        ll--;
        aa = ll;
        bb = rr;
        int fa = find(aa);
        int fb = find(bb);
           if(s[i][0] == 'e') num = 0;
            else num = 1;
        if(fa != fb)
        {
            f[fa] = fb;
            val[fa] = (num + val[bb] - val[aa] + 2) % 2;
        }
        else{
            if((val[aa] - val[bb] + 2) % 2 != num)
            {
                index = i;
                break;
            }
        }
    }
    if(index == inf)
        cout << m << '\n';
    else
        cout << index - 1 << '\n';

}