题目简述

有一串长度为 $n$ 的 $01$ 串，给定 $m$ 个问答，每个问答的形式为

$$l\ r\ s$$

表示 $[l,r]$ 中 $1$ 的数量的奇偶关系是 $s$ （$s$ 为 $”even”$ 或 $”odd”$）

思路

转化一下每个问答。

• 区间 $[l,r]$ 有偶数个 $1$，那么说明区间 $[1,l-1]$ 和 $[1,r]$ 的奇偶性是一致的。

• 区间 $[l,r]$ 有奇数个 $1$，那么说明区间 $[1,l-1]$ 和 $[1,r]$ 的奇偶性是不一致的。

那么 $m$ 个问答就等价于，$l-1$ 与 $r$ 奇偶的关系。和程序自动分析那题类似。

考虑使用并查集。

方法一：边带权

奇偶加减的性质和异或的性质类似。考虑用异或来表示奇偶性。

若一个区间有偶数个 $1$ 用 $0$ 表示，一个区间有奇数个 $1$ 用 $1$ 表示，那么连续区间

$$0\ 1\ 1\ 0\ 1\ 1\ 0\ 0\ 1$$

的 1 的个数的奇偶性就是

$$0\ \text{xor}\ 1\ \text{xor}\ 1\ \text{xor}\ 0\ \text{xor}\ 1\ \text{xor}\ 1\ \text{xor}\ 0\ \text{xor}\ 0\ \text{xor}\ 1 = 1$$

设 $rel_x$ 的值表示 $x$ 到祖先点这段区间中 $1$ 的数量，$1$ 表示奇数个，$0$ 表示偶数个。设 $f_x$ 记录 $x$ 在它对应集合中的祖先。

那么对于一段区间 $[l,r]$ 的奇偶性，就是 $rel_{l-1}\ \text{xor}\ rel_r$ 的值。

当两个点不在一个集合中时，${l-1}$ 的祖先要与 $r$ 的祖先联结。更新 $rel_{f_{l-1}}$ 和 $f_{l-1}$ 的值。

因为联结后要满足 $rel_{l-1}\ \text{xor}\ rel_r = tmp$（$tmp$ 是 $[l,r]$ 的奇偶性，奇为 $1$，偶为 $0$）。即联结之前要满足 $rel_{l-1}\ \text{xor}\ rel_{f_{l-1}}\ \text{xor}\ rel_r = tmp$。

那么联结后，$rel_{f_{l-1}}$ 的值就是 $tmp\ \text{xor}\ rel_{l-1}\ \text{xor}\ rel_r$。

当两个点在一个集合时，需要判断两点之前得到的关系是否和现在的冲突。即判断 $rel_{l-1}\ \text{xor}\ rel_r = tmp$ 是否成立。不成立直接输出。

对于 $rel$，可以在并查集中查找的操作中更新。蓝书中的模板：

int find(int x) {
    if (x == f[x]) return x;
    int fa = find(f[x]);
    //update the things you want.
    return f[x] = fa;
}

在本题 $rel$ 的更新自然就是 rel[x] ^= rel[f[x]]; 了。

时间复杂度 $O(m\log n)$。

方法二：扩展域

对于每个数，只有奇偶两种情况。而并查集只能对一个类型的值进行操作。

那么把一个数扩展到两个域进行操作，一个奇数，一个偶数。

仔细思考每个问答，发现每个问答等价于将这两个数的两个奇偶分别并到两个集合中。

当两个数 $l$，$r$，区间 $[l,r]$ 有奇数个 1，那么 $[1,l-1]$ 和 $[1,r]$ 的奇偶性不同，意味着 $l-1$ 和 $r$ 的奇偶关系不同。

那么把 $r_{oven}$ 和 $l-1_{odd}$、 $r_{odd}$ 和 $l-1_{even}$ 分别进行合并。

偶数同理。

合并前需要判断 $l-1$ 和 $r$ 是否符合当前的问答。当 $l-1_{oven}$ 和 $r_{even}$ 在同一集合，但 $l-1$ 和 $r$ 的奇偶关系应该是不同时，该问答不成立。

扩展域并不是把祖先数组扩展到二维，这样会错误（笔者试过了）。应该是把一个 $x$ 奇数看作 $x$，偶数则看作 $x+n$。

这样祖先数组空间要开到 $n\times 2$。

时间复杂度 $O(m\log n)$。

注意

数据比较大，要先进行离散化。

码子不易，给个支持再走吧。

代码

边带权

#include<bits/stdc++.h>

#define ll long long
#define y1 caibictq
#define P pair<int, int>
#define fi first
#define se second

using namespace std;

const int MAXN = 200010;
const int MAXM = 100010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n, m, k;
int tot, cnt, ans;

int read() {
    int f = 1, s = 0;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 1) + (s << 3) + ((int)ch ^ 48); ch = getchar();}
    return s * f;
}

int l[MAXN], r[MAXN];
int f[MAXN], rel[MAXN];

int find(int x) {
    if (x == f[x]) return x;
    int fa = find(f[x]);
    rel[x] ^= rel[f[x]];
    return f[x] = fa;
}

string s[MAXN];

vector<int> num;

int main() {
    int T;
    scanf("%d%d", &n, &m);
    num.push_back(0);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &l[i], &r[i]);
        cin >> s[i];
        num.push_back(l[i]);
        num.push_back(r[i]);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    n = num.size() - 1;
    for (int i = 0; i <= n; i++) {
        f[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        l[i] = lower_bound(num.begin(), num.end(), l[i]) - num.begin();
        r[i] = lower_bound(num.begin(), num.end(), r[i]) - num.begin();
    }
    for (int i = 1; i <= m; i++) {
        int fl = find(l[i] - 1), fr = find(r[i]);
        int tmp = s[i] == "odd"; 
        if (fl == fr) {
            if (rel[l[i] - 1] ^ rel[r[i]] != tmp) {
                printf("%d\n", i - 1);
                return 0;
            }
        }
        else {
            f[fl] = fr;
            rel[fl] = tmp ^ rel[l[i] - 1] ^ rel[r[i]];
        }
    }
    printf("%d\n", m);
    return 0;
}

扩展域

#include<bits/stdc++.h>

#define ll long long
#define y1 caibictq
#define P pair<int, int>
#define fi first
#define se second

using namespace std;

const int MAXN = 200010;
const int MAXM = 100010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n, m, k;
int tot, cnt, ans;

int read() {
    int f = 1, s = 0;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 1) + (s << 3) + ((int)ch ^ 48); ch = getchar();}
    return s * f;
}

int l[MAXN], r[MAXN];
int f[MAXN];

int find(int x) {
    while (x != f[x]) x = f[x] = f[f[x]];
    return x;
}

string s[MAXN];

vector<int> num;

int main() {
    int T;
    scanf("%d%d", &n, &m);
    num.push_back(0);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &l[i], &r[i]);
        cin >> s[i];
        num.push_back(l[i]);
        num.push_back(r[i]);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    for (int i = 1; i <= m; i++) {
        l[i] = lower_bound(num.begin(), num.end(), l[i]) - num.begin();
        r[i] = lower_bound(num.begin(), num.end(), r[i]) - num.begin();
    }
    n = num.size() - 1;
    for (int i = 0; i <= 2 * n + 1; i++) {
        f[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int fl0 = find(l[i] - 1), fr0 = find(r[i]);
        int fl1 = find(l[i] + n), fr1 = find(r[i] + n + 1);
        if (s[i] == "even") {
            if (fl0 == fr1 || fl1 == fr0) {
                printf("%d\n", i - 1);
                return 0;
            }
            f[fl0] = fr0;
            f[fl1] = fr1;
        }
        if (s[i] == "odd") {
            if (fl0 == fr0 || fl1 == fr1) {
                printf("%d\n", i - 1);
                return 0;
            }
            f[fl0] = fr1;
            f[fl1] = fr0;
        }
    }
    printf("%d\n", m);
    return 0;
}